您的位置: 首页  >  文章  >  集合

集合

分类: 文章 • 2024-04-30 21:49:10

集合的表示方式

Java集合的实现是采用接口的方式。不同的具体实现类实际上是实现了多个接口。因此我们在选用集合结构时，应该从接口的角度考虑。比如要进行快速存取，就应该考虑实现了RandomAccess随机访问接口的实现类，比如ArrayList。如果想采用队列的数据结构，就应该考虑实现了Queue接口的实现类，如ArrayDeque或LinkedList。
Java在定义好接口后，并没有直接就通过实现具体接口来产生实际的类，而是先构建了几个抽象集合类，再通过对抽象集合类的继承来设计具体的集合类。这么做的好处是当我们新设计一个集合类时，不用去一次覆盖接口的每个方法，对于不常用方法可以直接从抽象类中继承过来。
先贴一张关系图：转自Java集合框架–昨夜星辰
集合
集合的接口可以抽象出两个父类接口，Collection接口和Map接口。以及一个用以遍历集合的Iterator接口。并且，由于各种集合的基础是由数组和链表两种方式构成，因此引入一个RandomAccess接口来标识该集合的适用方式（有时候可以看成该集合的基础为数组）。

Collection接口

Collection接口，作为集合的父类接口，他内部主要的方法都是对集合具有普遍性的。
举个比较代表性的方法：Iterator<E> iterator();该方法会用于产生一个迭代器类，该类实现了Iterator接口，主要是用于对集合的遍历。
注意：实现了Iterator<E> iterator();方法也意味着Collection接口实现了Iterable接口。

Iterator接口

迭代器的出现使得我们可以将遍历集合的操作抽象出来，而不用针对不同的集合编写单一的遍历方式，现在我们只用编写迭代器类就可以了。迭代器类主要由4个方法构成，分别是：

  • hasNext()
  • next()
  • remove()
  • checkForComodification()。

值得说明的是，迭代器的指针可以理解为指向两个元素之间，每次使用next()都会返回迭代器越过的元素。并且，每调用一次remove()之前都要调用一次next()，否则会出错。
不同的集合还扩展出了不同的迭代器，会在具体集合类中介绍。

Map接口

Map接口指的是映射形式，即含有Key和Value，Key作为索引，Value作为索引所对应的值。他的添加和获取方法名称同Collection不同，分别为V get​(Object key)和V put​(K key, V value)，具体的类后面再展开。

具体接口

还是这张图
集合
从上图可以看出，集合分为两大类，Collection和Map。其实还有Iterator和RandomAccess接口，在这里先不展开。

List接口

作为一个有序集合接口，其主要特点是允许数据的重复性，支持更改顺序，并且支持随机访问（性能依据具体实现类），具体的实现可以由数组或者链表去实现，因此产生了不同的具体类。
该接口值得注意的一个地方，是他有一个 产生ListIterator接口的迭代器方法。 ListIterator接口的特点是可以实现正向和逆向遍历操作。逆向操作方法为E previous()和boolean hasPrevious()。

Set接口

该接口有两个特点，一个是不允许含有重复元素，另一个是不能使用Set<Set<Integer>>这样的包含结构（这是由不重复性确定的）。

Queue接口

队列接口的特点是先进先出FIFO或者后进先出LIFO，也就是队列和栈的功能。同List一样，依据具体的实现基础，可分为数组实现的ArrayDeque类和链表实现的LinkedList类。

具体集合类分析

ArrayList

参考：
Java 容器源码分析之 ArrayList–JR’s Blog
ArrayList继承了AbstractList抽象类，并实现了List，RandomAccess，Cloneable以及Serializable接口。ArrayList的内部储存采用了数组的形式，因此才有RandomAccess的功能。
要注意的地方有以下几点：

  • ArrayList初始默认容量是10，扩容时，采用的是当前容量的1.5倍容量，即原来容量加0.5倍。而考虑到数组扩容会产生大量的数据移动，因此对于较大的数据录入最好采用一次性分配较多的空间，避免重复扩容。
  • ArrayList会维护一个modCount变量用来记录容器发生结构化修改的次数，这么做的目的，主要是为了进行fast-fail判断。

HashMap

参考：
Java 容器源码分析之 HashMap–JR’s Blog
Java HashMap工作原理及实现–YiKun
Java 8系列之重新认识HashMap–美团点评技术团队
Java HashMap工作原理–ImportNew

内部结构

HashMap使用了一个内部类Entry<K, V>来作为Node存储数据。该内部类主要有四个域，分别是K，V，K的hashcode，以及一个指向下一个Entry<K, V>的指针变量。
HashMap使用Entry<K, V>作为最小的储存单元，然后以数组table（长度始终保持为2的幂次方）为集合的基本结构，并且以该数组table的一个元素为一个桶（bin），对具有相同散列值的Entry<K, V>都放入同一个桶中，桶内采用的是链表(8个Entry<K, V>以下)和红黑树（8个以上）的结构进行保存。具体结构如图：
集合
由此可以看出，对于Key值类，如果K是Comparable的（在红黑树内查找时候），就会对HashMap的查询有一定的加速作用。

哈希计算

HashMap的散列化原理有三步：

  • 调用Key的hashCode（）得到初步哈希值h；
  • 对h调用自己的hash（）方法再次散列化（主要是位操作）得到哈希值hash
  • 将hash值对数组table长度取模，得到该Key在数组中的下标。要注意的是由于数组table长度为2的幂次方，所以取模操作也可以用位操作代替

因此，如果我们能随意改动Key的hashCode（）产生的Hash值，那么将在HashMap中产生影响，造成键值丢失。

扩容

HashMap的扩容是指对数组table的长度加倍，也就是将原table的长度乘以2去建立一个新数组，然后把原来的每个Entry再散列化进新数组中。值得注意的是，数组扩容为2的幂次方的一个原因是为了提高再散列化的效率，因为Java的本质储存方式为二进制的。
>

参考：YiKun’s Blog
怎么理解呢？例如我们从16扩展为32时，具体的变化如下所示：
集合
因此元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
集合
因此，我们在扩充HashMap的时候，不需要重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。可以看看下图为16扩充为32的resize示意图：
集合
这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。

HashMap的视图View–用于遍历

HashMap 提供了三种方式来遍历其中的 Entry、Key 及Value，分别是 Set<Map.Entry<K,V>> entrySet()，Set<K> keySet()和 Collection<V> values()。这三个方法的基本用法返回的都是视图View集合，即一种遍历方式（迭代器），而不是真的返回了一个复制出来的新的Entry数组table。要弄清楚这三个方法的内部实现机制，首先要来看一下内部抽象类 HashIterator。
1. HashMap构建了一个迭代器类 HashIterator，利用该类就可以对HashMap的集合进行遍历操作。
2. KeyIterator、ValueIterator 和 EntryIterator 都继承了 HashIterator，区别只在于next() 方法返回的是 Key、Value 还是 Entry。
3. 利用KeyIterator、ValueIterator 和 EntryIterator，可以构成Set<Map.Entry<K,V>> entrySet()，Set<K> keySet()和 Collection<V> values()方法，以返回三种不同的View视图。

线程安全性

HashMap的是线程不安全的，因此可以采用ConcurrentHashMap类。

相关推荐