集合总结
HashMap
HashMap是一个键值存储的集合，它根据键的hashCode值存储数据。大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
存储结构
从结构实现来讲，HashMap是数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下如所示。
HashMap的存储结构
首先，源码可以看出来一个很重要的字段就是Node[] table，在这里我就叫hash数组，Node实现Map.Entry接口，并且重写其中的方法，这个Node结构是真正存储一个HashMap元素的结构，并且在其中保存着这个节点的hash
HashMap是通过哈希表来存储的，并且使用数组+链表的形式解决hash冲突，有的时候两个key会定位到一个位置，表示发生了Hash碰撞，如果能够直接定位到Node节点忽略hash冲突的话，这样的HashMap的存取效率是最快的
如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node[] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。
在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段
int threshold; // 所能容纳的key-value对极限
final float loadFactor; // 负载因子
int modCount;
int size;
首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。
结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。
size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败，这个modCound字段主要用于重写迭代器的next方法中 ，每次遍历下一个元素的时候都会判断一下modCount是否变成expectedmodCount。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数
Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。
一旦链表过长，就会转换为红黑树，利用红黑树的快速增删改查的特点提高HashMap性能，当链表长度超过8的时候，将链表转换为红黑树
实现
HashMap实现的hash算法，需要保证能够直接定位到Node数组的节点上，尽量减少hash冲突，最好是能够直接通过key的hash值定位到对应的数组位置，不需要遍历链表以便于优化效率
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {
//jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
return h & (length-1); //第三步 取模运算
}
这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。
对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。
这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。
在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。
[图片上传失败...(image-33c990-1542350990492)]
put()
put方法流程
①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
②.根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
扩容机制
当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
1.7resize()采用的是头插法，1.8采用的是尾插法
我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，
图（a）表示扩容前的key1和key2两种key确定索引位置的示例，
图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。
扩容
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：
可以看到多了一位参加运算，同时也正是因为数组长度为2的n次幂，这个时候会出现这样的变化
resize
可以观察到，扩容之后多一位高位参与运算之后的结果，正好是之前的旧table的index加上远table的长度
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”
e.hash & oldCap
重新省去了计算hash的时间，因为最高位2进制出现的数值只可能为0/1，这个时候就能够将原始链上的hash冲突的Node节点均匀分开，如果这个结果为0的话，则分支出来的这条链还是在原index，只不过另一条链就需要使用原index + oldTable的长度
jdk1.7下，使用HashMap可能会出现死循环的情况
ArrayList
扩容grow
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
add(E e)增加
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add主要的执行逻辑如下：
- 确保数组已使用长度（size）加1之后足够存下 下一个数据
- 修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
- 确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
- 返回添加成功布尔值。
add(int index, E element)
这个方法其实和上面的add类似，该方法可以按照元素的位置，指定位置插入元素，具体的执行逻辑如下：
- 确保数插入的位置小于等于当前数组长度，并且不小于0，否则抛出异常
- 确保数组已使用长度（size）加1之后足够存下 下一个数据
- 修改次数（modCount）标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组
- grow方法会将当前数组的长度变为原来容量的1.5倍。
- 确保有足够的容量之后，使用System.arraycopy 将需要插入的位置（index）后面的元素统统往后移动一位。
- 将新的数据内容存放到数组的指定位置（index）上
ArrayList
grow()扩容
数组扩容至原来的1.5倍
其中许多需要直接对下标访问的操作都需要对下标的范围检查
System.copyarray;
Arrays.copyOf;
快速失败
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
创建迭代器的时候，会获取当前的modCount，每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
LinkedList
LinkedList继承了AbstractSequentialList并且实现List，Deque，Cloneable, Serializable接口。 其中，AbstractSequentialList相较于AbstractList(ArrayList的父类),只支持次序访问，而不支持随机访问，因为它的 get(int index) ,set(int index, E element), add(int index, E element), remove(int index) 都是基于迭代器实现的。所以在LinkedList使用迭代器遍历更快，而ArrayList使用get (i)更快。 接口方面，LinkedList多继承了一个Deque接口，所以实现了双端队列的一系列方法。
随机访问
ArrayList 使用 for 循环遍历优于迭代器遍历
LinkedList 使用 迭代器遍历优于 for 循环遍历
根据以上结论便可利用 RandomAccess 在遍历前进行判断，根据 List 的不同子类选择不同的遍历方式， 提升算法性能。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { //判断index是在链表偏左侧还是偏右侧
Node<E> x = first;
for (int i = 0; i < index; i++) //从左边往右next
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--) //从右往左prev
x = x.prev;
return x;
}
}
遍历寻找节点进行查找
双端队列
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
private void linkFirst(E e) {
final Node<E> f = first; //现将原有的first节点保存在f中
final Node<E> newNode = new Node<>(null, e, f); //将新增节点包装成一个Node节点，同时该节点的next指向之前的first
first = newNode; //将新增的节点设成first
if (f == null)
last = newNode; //如果原来的first就是空，那么新增的newNode同时也是last节点
else
f.prev = newNode; //如果不是空，则原来的first节点的前置节点就是现在新增的节点
size++; //插入元素后，节点个数加1
modCount++; //还记得上一篇讲述的快速失败吗？这边依然是这个作用
}
-
将原有头节点保存到f
-
将插入元素包装成新节点，并且该新节点的next指向原来的头节点，即f
-
如果原来的头节点f为空的话，那么新插的头节点也是last节点，否则，还要设置f的前置节点为-NewNode，即NewNode现在是first节点了
-
记得增加size，记录修改次数modCount
尾插
void linkLast(E e) {
final Node<E> l = last; //将尾节点保存到l中
final Node<E> newNode = new Node<>(l, e, null); //把e包装成Node节点，同时把该节节点设置为l
last = newNode; //把新插的节点设置为last节点
if (l == null)
first = newNode; //如果原来的last节点为空，那么新增的节点在意义上也是first节点
else
l.next = newNode; //否则的话还要将newNode设为原有last节点的后继节点，所以newNode现在是新的Last节点
size++;
modCount++;
}
add
添加方法默认使用尾插法
addAll(Collection<? extends E> c)指的是在list尾部插入一个集合，具体实现又依赖于addAll(size，c)，指的是在指定位置插入一个集合：
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 检查index位置是否超出范围
Object[] a = c.toArray(); //将集合c转变成Object数组 同时计算数组长度
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { //如果插入位置为尾部，succ则为null，原来链表的last设置为此刻的pred节点
succ = null;
pred = last;
} else {
succ = node(index); //否则，index所在节点设置为succ，succ的前置节点设为pred
pred = succ.prev;
}
for (Object o : a) { //循环遍历数组a
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); //以a为element元素构造Node节点
if (pred == null)
first = newNode;� //如果pred为空，此Node就为first节点
else
pred.next = newNode; //否则就往pred后插入该Node
pred = newNode; //newNode此刻成为新的pred, 这样不断循环遍历，把这个数组插入到链表中
}
if (succ == null) { //如果succ为空，就把插入的最后一个节点设为last
last = pred;
} else {
pred.next = succ; //否则，把之前保存的succ接到pred后面
succ.prev = pred; //并且把succ的前向指针指向插入的最后一个元素
}
size += numNew; //记录增长的尺寸
modCount++; //记录修改次数
return true;
}
add方法
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // 检查index位置是否超出范围
Object[] a = c.toArray(); //将集合c转变成Object数组 同时计算数组长度
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) { //如果插入位置为尾部，succ则为null，原来链表的last设置为此刻的pred节点
succ = null;
pred = last;
} else {
succ = node(index); //否则，index所在节点设置为succ，succ的前置节点设为pred
pred = succ.prev;
}
for (Object o : a) { //循环遍历数组a
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null); //以a为element元素构造Node节点
if (pred == null)
first = newNode; //如果pred为空，此Node就为first节点
else
pred.next = newNode; //否则就往pred后插入该Node
pred = newNode; //newNode此刻成为新的pred, 这样不断循环遍历，把这个数组插入到链表中
}
if (succ == null) { //如果succ为空，就把插入的最后一个节点设为last
last = pred;
} else {
pred.next = succ; //否则，把之前保存的succ接到pred后面
succ.prev = pred; //并且把succ的前向指针指向插入的最后一个元素
}
size += numNew; //记录增长的尺寸
modCount++; //记录修改次数
return true;
}
Set
HashSet
对于 HashSet 而言，它是基于 HashMap 实现的，底层采用 HashMap 来保存元素
对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，我们应该为保存到 HashSet 中的对象覆盖 hashCode() 和 equals()
/**
* 默认的无参构造器，构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 构造一个包含指定collection中的元素的新set。
*
* 实际底层使用默认的加载因子0.75和足以包含指定collection中所有元素的初始容量来创建一个HashMap。
* @param c 其中的元素将存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity和loadFactor构造一个空的HashSet。
*
* 实际底层以相应的参数构造一个空的HashMap。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 以指定的initialCapacity构造一个空的HashSet。
*
* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。此构造函数为包访问权限，不对外公开，
* 实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
add
/**
* @param e 将添加到此set中的元素。
* @return 如果此set尚未包含指定元素，则返回true。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
由于 HashMap 的 put() 方法添加 key-value 对时，当新放入 HashMap 的 Entry 中 key 与集合中原有 Entry 的 key 相同（hashCode()返回值相等，通过 equals 比较也返回 true），新添加的 Entry 的 value 会将覆盖原来 Entry 的 value（HashSet 中的 value 都是PRESENT），但 key 不会有任何改变，因此如果向 HashSet 中添加一个已经存在的元素时，新添加的集合元素将不会被放入 HashMap中，原来的元素也不会有任何改变，这也就满足了 Set 中元素不重复的特性。
该方法如果添加的是在 HashSet 中不存在的，则返回 true；如果添加的元素已经存在，返回 false。其原因在于我们之前提到的关于 HashMap 的 put 方法。该方法在添加 key 不重复的键值对的时候，会返回 null。
/**
* 如果此set包含指定元素，则返回true。
* 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))的e元素时，返回true。
*
* 底层实际调用HashMap的containsKey判断是否包含指定key。
* @param o 在此set中的存在已得到测试的元素。
* @return 如果此set包含指定元素，则返回true。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 如果指定元素存在于此set中，则将其移除。更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，
* 则将其移除。如果此set已包含该元素，则返回true
*
* 底层实际调用HashMap的remove方法删除指定Entry。
* @param o 如果存在于此set中则需要将其移除的对象。
* @return 如果set包含指定元素，则返回true。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 返回此HashSet实例的浅表副本：并没有复制这些元素本身。
*
* 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}
LinkedList
与ArrayList不同的是，LinkedList继承了AbstractSequentialList，从Sequential这个单词可以看出，该抽象类实现的是顺序访问的结构，因为可以推测可能和链表有关。
另外值得注意的是Deque这个接口，这个类名字的由来是“double ended queue”，也就是双向队列，即从头部和尾部都可以进行队列的操作。
LinkedList数据结构
// list中的元素个数
transient int size = 0;
// 链表的头节点
transient Node<E> first;
// 链表的尾节点
transient Node<E> last;
实际存储节点是用Node
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检查index是否在正确，即在0-size之间
checkPositionIndex(index);
// 将collection转为数组
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// pred为前置元素， succ为后继元素
Node<E> pred, succ;
// 对pred，succ进行初始化。
if (index == size) {
// index == size，说明要插入元素的位置就在链表的末尾，后置元素为null，前一个元素就是last
succ = null;
pred = last;
// index != size， 说明在链表的中间插入，这是pred为原来index的prev，succ为原来的元素
} else {
succ = node(index);
pred = succ.prev;
}
// 搞清了前后元素的关系，就是遍历数组，逐个添加
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// 如果后继元素为空，那么插入完后的最后一个元素，就prev就是last
if (succ == null) {
last = pred;
// 否则就维护最后一个元素和之前的元素之间的关系
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
对于遍历Collection插入链表的逻辑应该是挺清晰的：
- 按照前-自己-后的关系调用Node的构造方法，进行初始化。
- 由于可能存在前一个元素pred为空的可能（构造函数调用），判断pred为空，则初始化的元素就是头节点
- 否则就维护pred与新节点newNode直接的关系。
- 将新节点作为pred，为下一个元素插入做准备
Node<E> node(int index) {
// 如果index在链表的前半部分，则从头部节点开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
// 如果index在链表的后半部分，则从尾部节点开始遍历
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
网友评论