本文快速回顾了Java中容器的知识点，用作面试复习，事半功倍。
上篇：主要为容器概览，容器中用到的设计模式，List源码
中篇：Map源码
下篇：Set源码，容器总结
http://wiki.jikexueyuan.com/project/java-collection/hashmap.html
源码分析：
https://segmentfault.com/a/1190000014293372
hashMap的一个内部类Node：
1static class Node<K,V> implements Map.Entry<K,V> {
2 final int hash;
3 final K key;
4 V value;
5 Node<K,V> next; //链表结构，存储下一个元素
在这里插入图片描述
Node内部包含了一个 Entry 类型的数组table，数组中的每个位置被当成一个桶。
1transient Entry[] table;Entry 存储着键值对。它包含了四个字段，从 next 字段我们可以看出 Entry 是一个链表。即数组中的每个位置被当成一个桶，一个桶存放一个链表。
HashMap 使用拉链法来解决冲突，同一个链表中存放哈希值相同的 Entry。
1static class Entry<K,V> implements Map.Entry<K,V> {
2 final K key;
3 V value;
4 Entry<K,V> next;
5 int hash;
6
7 Entry(int h, K k, V v, Entry<K,V> n) {
8 value = v;
9 next = n;
10 key = k;
11 hash = h;
12 }
13
14 public final K getKey() {
15 return key;
16 }
17
18 public final V getValue() {
19 return value;
20 }
21
22 public final V setValue(V newValue) {
23 V oldValue = value;
24 value = newValue;
25 return oldValue;
26 }
27
28 public final boolean equals(Object o) {
29 if (!(o instanceof Map.Entry))
30 return false;
31 Map.Entry e = (Map.Entry)o;
32 Object k1 = getKey();
33 Object k2 = e.getKey();
34 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
35 Object v1 = getValue();
36 Object v2 = e.getValue();
37 if (v1 == v2 || (v1 != null && v1.equals(v2)))
38 return true;
39 }
40 return false;
41 }
42
43 public final int hashCode() {
44 return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
45 }
46
47 public final String toString() {
48 return getKey() + "=" + getValue();
49 }
50}
在这里插入图片描述
构造时就会调用tableSizeFor()：返回一个大于输入参数且最近的2的整数次幂。
1static final int tableSizeFor(int cap) {
2 int n = cap - 1;
3 n |= n >>> 1;
4 n |= n >>> 2;
5 n |= n >>> 4;
6 n |= n >>> 8;
7 n |= n >>> 16;
8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9}应该注意到链表的插入是以头插法方式进行的
1HashMap<String, String> map = new HashMap<>();
2map.put("K1", "V1");
3map.put("K2", "V2");
4map.put("K3", "V3");查找需要分成两步进行：
计算键值对所在的桶；
在链表上顺序查找，时间复杂度显然和链表的长度成正比。
1public V put(K key, V value) {
2 if (table == EMPTY_TABLE) {
3 inflateTable(threshold);
4 }
5 // 键为 null 单独处理
6 if (key == null)
7 return putForNullKey(value);
8 int hash = hash(key);
9 // 确定桶下标
10 int i = indexFor(hash, table.length);
11 // 先找出是否已经存在键为 key 的键值对，如果存在的话就更新这个键值对的值为 value
12 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
13 Object k;
14 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
15 V oldValue = e.value;
16 e.value = value;
17 e.recordAccess(this);
18 return oldValue;
19 }
20 }
21
22 modCount++;
23 // 插入新键值对
24 addEntry(hash, key, value, i);
25 return null;
26}HashMap 允许插入键为 null 的键值对。但是因为无法调用 null 的 hashCode() 方法，也就无法确定该键值对的桶下标，只能通过强制指定一个桶下标来存放。HashMap 使用第 0 个桶存放键为 null 的键值对。
1private V putForNullKey(V value) {
2 for (Entry<K,V> e = table[0]; e != null; e = e.next) {
3 if (e.key == null) {
4 V oldValue = e.value;
5 e.value = value;
6 e.recordAccess(this);
7 return oldValue;
8 }
9 }
10 modCount++;
11 addEntry(0, null, value, 0);
12 return null;
13}使用链表的头插法，也就是新的键值对插在链表的头部，而不是链表的尾部。
1void addEntry(int hash, K key, V value, int bucketIndex) {
2 if ((size >= threshold) && (null != table[bucketIndex])) {
3 resize(2 * table.length);
4 hash = (null != key) ? hash(key) : 0;
5 bucketIndex = indexFor(hash, table.length);
6 }
7
8 createEntry(hash, key, value, bucketIndex);
9}
10
11void createEntry(int hash, K key, V value, int bucketIndex) {
12 Entry<K,V> e = table[bucketIndex];
13 // 头插法，链表头部指向新的键值对
14 table[bucketIndex] = new Entry<>(hash, key, value, e);
15 size++;
16}
1Entry(int h, K k, V v, Entry<K,V> n) {
2 value = v;
3 next = n;
4 key = k;
5 hash = h;
6}补充：hashmap里hash方法的高位优化：
https://www.cnblogs.com/liujinhong/p/6576543.html
设计者将key的哈希值的高位也做了运算(与高16位做异或运算，使得在做&运算时，此时的低位实际上是高位与低位的结合)，这就增加了随机性，减少了碰撞冲突的可能性！
为何要这么做？
table的长度都是2的幂，因此index仅与hash值的低n位有关，hash值的高位都被与操作置为0了。
这样做很容易产生碰撞。设计者权衡了speed, utility, and quality，将高16位与低16位异或来减少这种影响。设计者考虑到现在的hashCode分布的已经很不错了，而且当发生较大碰撞时也用树形存储降低了冲突。仅仅异或一下，既减少了系统的开销，也不会造成的因为高位没有参与下标的计算(table长度比较小时)，从而引起的碰撞。
很多操作都需要先确定一个键值对所在的桶下标。
1int hash = hash(key);
2int i = indexFor(hash, table.length);4.1 计算 hash 值
1final int hash(Object k) {
2 int h = hashSeed;
3 if (0 != h && k instanceof String) {
4 return sun.misc.Hashing.stringHash32((String) k);
5 }
6
7 h ^= k.hashCode();
8
9 // This function ensures that hashCodes that differ only by
10 // constant multiples at each bit position have a bounded
11 // number of collisions (approximately 8 at default load factor).
12 h ^= (h >>> 20) ^ (h >>> 12);
13 return h ^ (h >>> 7) ^ (h >>> 4);
14}
1public final int hashCode() {
2 return Objects.hashCode(key) ^ Objects.hashCode(value);
3}4.2 取模
令 x = 1<\<\4，即 \x 为 2 的 4 次方，它具有以下性质：
1x : 00010000
2x-1 : 00001111令一个数 y 与 x-1 做与运算，可以去除 y 位级表示的第 4 位以上数：
1y : 10110010
2x-1 : 00001111
3y&(x-1) : 00000010这个性质和 y 对 x 取模效果是一样的：
1y : 10110010
2x : 00010000
3y%x : 00000010我们知道，位运算的代价比求模运算小的多，因此在进行这种计算时用位运算的话能带来更高的性能。
确定桶下标的最后一步是将 key 的 hash 值对桶个数取模：hash%capacity，如果能保证 capacity 为 2 的 n 次方，那么就可以将这个操作转换为位运算。
1static int indexFor(int h, int length) {
2 return h & (length-1);
3}当 length 总是 2 的 n 次方时，h& (length-1)运算等价于对 length 取模，也就是 h%length，但是 & 比 % 具有更高的效率。这看上去很简单，其实比较有玄机的，我们举个例子来说明：
<table>
从上面的例子中可以看出：当它们和 15-1（1110）“与”的时候，8 和 9产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8 和 9 会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。
同时，我们也可以发现，当数组长度为 15 的时候，hash 值会与 15-1（1110）进行“与”，那么最后一位永远是 0，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率。
所以说，当数组长度为 2 的 n 次幂的时候，不同的 key 算得得 index 相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小
设 HashMap 的 table 长度为 M，需要存储的键值对数量为 N，如果哈希函数满足均匀性的要求，那么每条链表的长度大约为 N/M，因此平均查找次数的复杂度为 O(N/M)。
为了让查找的成本降低，应该尽可能使得 N/M 尽可能小，因此需要保证 M 尽可能大，也就是说 table 要尽可能大。HashMap 采用动态扩容来根据当前的 N 值来调整 M 值，使得空间效率和时间效率都能得到保证。
和扩容相关的参数主要有：capacity、size、threshold 和 load_factor。
1static final int DEFAULT_INITIAL_CAPACITY = 16;
2
3static final int MAXIMUM_CAPACITY = 1 << 30;
4
5static final float DEFAULT_LOAD_FACTOR = 0.75f;
6
7transient Entry[] table;
8
9transient int size;
10
11int threshold;
12
13final float loadFactor;
14
15transient int modCount;从下面的添加元素代码中可以看出，当需要扩容时，令 capacity 为原来的两倍。
1void addEntry(int hash, K key, V value, int bucketIndex) {
2 Entry<K,V> e = table[bucketIndex];
3 table[bucketIndex] = new Entry<>(hash, key, value, e);
4 if (size++ >= threshold)
5 resize(2 * table.length);
6}扩容使用 resize() 实现，需要注意的是，扩容操作同样需要把 oldTable 的所有键值对重新插入 newTable 中，因此这一步是很费时的。
1void resize(int newCapacity) {
2 Entry[] oldTable = table;
3 int oldCapacity = oldTable.length;
4 if (oldCapacity == MAXIMUM_CAPACITY) {
5 threshold = Integer.MAX_VALUE;
6 return;
7 }
8 Entry[] newTable = new Entry[newCapacity];
9 transfer(newTable);
10 table = newTable;
11 threshold = (int)(newCapacity * loadFactor);
12}
13
14void transfer(Entry[] newTable) {
15 Entry[] src = table;
16 int newCapacity = newTable.length;
17 for (int j = 0; j < src.length; j++) {
18 Entry<K,V> e = src[j];
19 if (e != null) {
20 src[j] = null;
21 do {
22 Entry<K,V> next = e.next;
23 int i = indexFor(e.hash, newCapacity);
24 e.next = newTable[i];
25 newTable[i] = e;
26 e = next;
27 } while (e != null);
28 }
29 }
30}扩容-重新计算桶下标
Rehash优化：https://my.oschina.net/u/3568600/blog/1933764
在进行扩容时，需要把键值对重新放到对应的桶上。HashMap 使用了一个特殊的机制，可以降低重新计算桶下标的操作。
假设原数组长度 capacity 为 16，扩容之后 new capacity 为 32：
1capacity : 00010000
2new capacity : 00100000对于一个 Key，
总结：
经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：
在这里插入图片描述
HashMap 构造函数允许用户传入的容量不是 2 的 n 次方，因为它可以自动地将传入的容量转换为 2 的 n 次方。
先考虑如何求一个数的掩码，对于 10010000，它的掩码为 11111111，可以使用以下方法得到：
1mask |= mask >> 1 11011000
2mask |= mask >> 2 11111110
3mask |= mask >> 4 11111111
4mask+1 是大于原始数字的最小的 2 的 n 次方。
1num 10010000
2mask+1 100000000以下是 HashMap 中计算数组容量的代码：
1static final int tableSizeFor(int cap) {
2 int n = cap - 1;
3 n |= n >>> 1;
4 n |= n >>> 2;
5 n |= n >>> 4;
6 n |= n >>> 8;
7 n |= n >>> 16;
8 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
9}并不是桶子上有8位元素的时候它就能变成红黑树，它得同时满足我们的键值对大于64才行的
这是为了避免在哈希表建立初期，多个键值对恰好被放入了同一个链表中而导致不必要的转化。
在这里插入图片描述
谈谈ConcurrentHashMap1.7和1.8的不同实现：
http://www.importnew.com/23610.html
详细源码分析（还未细看）：
https://blog.csdn.net/yan_wenliang/article/details/51029372
https://segmentfault.com/a/1190000014380257
主要针对jdk1.7的实现来介绍
jdk1.7
jdk1.7中采用Segment + HashEntry的方式进行实现
在这里插入图片描述
Segment：其继承于 ReentrantLock 类，从而使得 Segment 对象可以充当锁的角色。
Segment 中包含HashBucket的数组，其可以守护其包含的若干个桶。
1static final class HashEntry<K,V> {
2 final int hash;
3 final K key;
4 volatile V value;
5 volatile HashEntry<K,V> next;
6}ConcurrentHashMap采用了分段锁，每个分段锁维护着几个桶，多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）。
jdk1.8
在这里插入图片描述
JDK 1.7 使用分段锁机制来实现并发更新操作，核心类为 Segment，它继承自重入锁 ReentrantLock，并发程度与 Segment 数量相等。
JDK 1.8 使用了 CAS 操作来支持更高的并发度，在 CAS 操作失败时使用内置锁 synchronized。
1.8中放弃了Segment臃肿的设计，取而代之的是采用Node数组 + CAS + Synchronized来保证并发安全进行实现
在这里插入图片描述
只让一个线程对散列表进行初始化！
从顶部注释我们可以读到，get方法是不用加锁的，是非阻塞的。
Node节点是重写的，设置了volatile关键字修饰，致使它每次获取的都是最新设置的值
每个 Segment 维护了一个 count 变量来统计该 Segment 中的键值对个数。
在执行 size 操作时，需要遍历所有 Segment 然后把 count 累计起来。
ConcurrentHashMap 在执行 size操作时先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那么可以认为这个结果是正确的。
尝试次数使用 RETRIES_BEFORE_LOCK 定义，该值为 2，retries 初始值为 -1，因此尝试次数为 3。
如果尝试的次数超过 3 次，就需要对每个 Segment 加锁。
在这里插入图片描述
为什么用这么方式删除呢，细心的同学会发现上面定义的HashEntry的key和next都是final类型的，所以不能改变next的指向，所以又复制了一份指向删除的结点的next。
Collections.synchronizedMap()与ConcurrentHashMap的区别
参考：https://blog.csdn.net/lanxiangru/article/details/53495854
ConcurrentHashMap 的高并发性主要来自于三个方面：
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap.html
https://segmentfault.com/a/1190000014319445
在这里插入图片描述
在这里插入图片描述
该 Entry 除了保存当前对象的引用外，还保存了其上一个元素 before 和下一个元素 after的引用，从而在哈希表的基础上又构成了双向链接列表。
1/**
2* LinkedHashMap的Entry元素。
3* 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。
4 */
5static class Entry<K,V> extends HashMap.Node<K,V> {
6 Entry<K,V> before, after;
7 Entry(int hash, K key, V value, Node<K,V> next) {
8 super(hash, key, value, next);
9 }
10 }
在这里插入图片描述
通过源代码可以看出，在 LinkedHashMap 的构造方法中，实际调用了父类 HashMap 的相关构造方法来构造一个底层存放的 table 数组，但额外可以增加 accessOrder 这个参数，如果不设置
LinkedHashMap 重写了父类 HashMap 的 get 方法，实际在调用父类 getEntry() 方法取得查找的元素后，再判断当排序模式 accessOrder 为 true 时，记录访问顺序，将最新访问的元素添加到双向链表的表头，并从原来的位置删除。
由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。
为啥注释说：初始容量对遍历没有影响？
因为它遍历的是LinkedHashMap内部维护的一个双向链表，而不是散列表(当然了，链表双向链表的元素都来源于散列表)
http://wiki.jikexueyuan.com/project/java-collection/linkedhashmap-lrucache.html
LRU最近最少使用（访问顺序）
用这个类有两大好处：
Java里面实现LRU缓存通常有两种选择：
以下是使用 LinkedHashMap 实现的一个 LRU 缓存：
1class LRUCache<K, V> extends LinkedHashMap<K, V> {
2 private static final int MAX_ENTRIES = 3;
3
4 protected boolean removeEldestEntry(Map.Entry eldest) {
5 return size() > MAX_ENTRIES;
6 }
7
8 LRUCache() {
9 super(MAX_ENTRIES, 0.75f, true);
10 }
11}
1public static void main(String[] args) {
2 LRUCache<Integer, String> cache = new LRUCache<>();
3 cache.put(1, "a");
4 cache.put(2, "b");
5 cache.put(3, "c");
6 cache.get(1);
7 cache.put(4, "d");
8 System.out.println(cache.keySet());
9}
1[3, 1, 4]实现详细代码请参考文章：补充知识点-缓存
FIFO（插入顺序）
还可以在插入顺序的LinkedHashMap直接重写下removeEldestEntry方法即可轻松实现一个FIFO缓存
在这里插入图片描述
详细看：
https://segmentfault.com/a/1190000014345983#articleHeader4
总结：
本人目前为后台开发工程师，主要关注Python爬虫，后台开发等相关技术。
Csdn
拥有专栏：Leetcode题解（Java/Python）、Python爬虫开发
知乎
https://www.zhihu.com/people/yang-zhen-dong-1/
拥有专栏：码农面试助攻手册
掘金
https://juejin.im/user/5b48015ce51d45191462ba55
简书
https://www.jianshu.com/u/b5f225ca2376
Java容器（List、Set、Map）知识点快速复习手册（中）
原文：https://blog.51cto.com/15047490/2561279