java.util.HashSet,java.util.LinkedHashMap,java.util.IdentityHashMap源码阅读(JDK1.8.0_111)

1     private transient HashMap map;
2 
3     // Dummy value to associate with an Object in the backing Map
4     private static final Object PRESENT = new Object();

1     public Iterator iterator() {
2         return map.keySet().iterator();
3     }

 1     static class Entry extends HashMap.Node {
 2         // 包含前一节点和后一节点的引用，是个双向链表
 3         Entry before, after;
 4         Entry(int hash, K key, V value, Node next) {
 5             super(hash, key, value, next);
 6         }
 7     }
 8     // 链表头节点，也是最老的节点
 9     transient LinkedHashMap.Entry head;
10     // 链表尾节点，也是最年轻的节点
11     transient LinkedHashMap.Entry tail;
12     // 访问顺序，true为访问顺序，false为插入顺序
13     final boolean accessOrder;

1     public LinkedHashMap(int initialCapacity,
2                          float loadFactor,
3                          boolean accessOrder) {
4         super(initialCapacity, loadFactor);
5         this.accessOrder = accessOrder;
6     }

 1     // 将src的相关引用全部复制给dst节点
 2     private void transferLinks(LinkedHashMap.Entry src,
 3                                LinkedHashMap.Entry dst) {
 4         // 修改节点自身的before和after引用
 5         LinkedHashMap.Entry b = dst.before = src.before;
 6         LinkedHashMap.Entry a = dst.after = src.after;
 7         // 修改前后节点的引用
 8         if (b == null)
 9             head = dst;
10         else
11             b.after = dst;
12         if (a == null)
13             tail = dst;
14         else
15             a.before = dst;
16     }

 1     // 删除节点操作
 2     void afterNodeRemoval(Node e) { // unlink
 3         // 保存当前节点及其前后节点
 4         LinkedHashMap.Entry p =
 5             (LinkedHashMap.Entry)e, b = p.before, a = p.after;
 6         // 从链表中去除掉该节点，主要是去除对该节点的引用
 7         // 将该节点对链表其它节点的引用也去掉
 8         p.before = p.after = null;
 9         if (b == null)
10             head = a;
11         else
12             b.after = a;
13         if (a == null)
14             tail = b;
15         else
16             a.before = b;
17     }
18 
19     void afterNodeAccess(Node e) { // move node to last
20         LinkedHashMap.Entry last;
21         // 如果按照访问顺序，则需要将被访问节点至于链表最结尾处
22         if (accessOrder && (last = tail) != e) {
23             LinkedHashMap.Entry p =
24                 (LinkedHashMap.Entry)e, b = p.before, a = p.after;
25             p.after = null;
26             if (b == null)
27                 head = a;
28             else
29                 b.after = a;
30             if (a != null)
31                 a.before = b;
32             else
33                 last = b;
34             if (last == null)
35                 head = p;
36             else {
37                 p.before = last;
38                 last.after = p;
39             }
40             tail = p;
41             ++modCount;
42         }
43     }
44 
45     void afterNodeInsertion(boolean evict) { // possibly remove eldest
46         LinkedHashMap.Entry first;
47         // removeEldestEntry(first) 默认返回false，如果需要可以继承LinkedHashMap，覆盖该函数。
48         // removeEldestEntry(first) 如果返回true,则在put的时候会删除链表头结点
49         if (evict && (first = head) != null && removeEldestEntry(first)) {
50             K key = first.key;
51             removeNode(hash(key), key, null, false, true);
52         }
53     }

1     transient Object[] table; // non-private to simplify nested class access
2     int size;
3     transient int modCount;
4     static final Object NULL_KEY = new Object();

1     private static Object maskNull(Object key) {
2         return (key == null ? NULL_KEY : key);
3     }
4 
5     static final Object unmaskNull(Object key) {
6         return (key == NULL_KEY ? null : key);
7     }

1     private static int nextKeyIndex(int i, int len) {
2         return (i + 2 );
3     }

1     private static int hash(Object x, int length) {
2         int h = System.identityHashCode(x);
3         // Multiply by -127, and left-shift to use least bit as part of hash
4         return ((h <<1) - (h <<8)) & (length - 1);
5     }

 1     public V put(K key, V value) {
 2         final Object k = maskNull(key);
 3 
 4         retryAfterResize: for (;;) {
 5             final Object[] tab = table;
 6             final int len = tab.length;
 7             // 计算下标
 8             int i = hash(k, len);
 9             
10             // 遍历所有可能的位置，直到找到一个空位
11             for (Object item; (item = tab[i]) != null;
12                  i = nextKeyIndex(i, len)) {
13                 // 待插入的key已经存在，替换value
14                 if (item == k) {
15                     @SuppressWarnings("unchecked")
16                         V oldValue = (V) tab[i + 1];
17                     tab[i + 1] = value;
18                     return oldValue;
19                 }
20             }
21 
22             // 新加一个节点如果size > len/3则需要扩容
23             final int s = size + 1;
24             // Use optimized form of 3 * s.
25             // Next capacity is len, 2 * current capacity.
26             if (s + (s <<1) > len && resize(len))
27                 // 扩容后待插入的节点需要重新查找位置
28                 continue retryAfterResize;
29 
30             // 修改次数加一
31             modCount++;
32             // 在下标i存放key，在i+1下标存放value
33             tab[i] = k;
34             tab[i + 1] = value;
35             size = s;
36             return null;
37         }
38     }    

 1     private boolean resize(int newCapacity) {
 2         // assert (newCapacity & -newCapacity) == newCapacity; // power of 2
 3         // 直接扩容为之前的2倍
 4         int newLength = newCapacity * 2;
 5 
 6         Object[] oldTable = table;
 7         int oldLength = oldTable.length;
 8         if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
 9             if (size == MAXIMUM_CAPACITY - 1)
10                 throw new IllegalStateException("Capacity exhausted.");
11             return false;
12         }
13         if (oldLength >= newLength)
14             return false;
15         // 重新new一个新的数组出来，简单粗暴！
16         Object[] newTable = new Object[newLength];
17 
18         for (int j = 0; j ) {
19             Object key = oldTable[j];
20             if (key != null) {
21                 Object value = oldTable[j+1];
22                 // 将原数组上的key value清空，不清空将会导致内存无法被释放
23                 oldTable[j] = null;
24                 oldTable[j+1] = null;
25                 // key重新hash
26                 int i = hash(key, newLength);
27                 while (newTable[i] != null)
28                     // hash冲突了就查找下一个位置
29                     i = nextKeyIndex(i, newLength);
30                 newTable[i] = key;
31                 newTable[i + 1] = value;
32             }
33         }
34         table = newTable;
35         return true;
36     }

 1     public V get(Object key) {
 2         Object k = maskNull(key);
 3         Object[] tab = table;
 4         int len = tab.length;
 5         // 根据key计算下标
 6         int i = hash(k, len);
 7         while (true) {
 8             Object item = tab[i];
 9             if (item == k)
10                 return (V) tab[i + 1];
11             if (item == null)
12                 return null;
13             // 查找下一个位置
14             i = nextKeyIndex(i, len);
15         }
16     }

 1     public V remove(Object key) {
 2         Object k = maskNull(key);
 3         Object[] tab = table;
 4         int len = tab.length;
 5         int i = hash(k, len);
 6 
 7         while (true) {
 8             Object item = tab[i];
 9             // 查找到该key
10             if (item == k) {
11                 modCount++;
12                 size--;
13                 @SuppressWarnings("unchecked")
14                     V oldValue = (V) tab[i + 1];
15                 // 相应位置置空
16                 tab[i + 1] = null;
17                 tab[i] = null;
18                 // 直接置空会导致查找出现问题
19                 closeDeletion(i);
20                 return oldValue;
21             }
22             // 没有找到该key
23             if (item == null)
24                 return null;
25             i = nextKeyIndex(i, len);
26         }
27     }

 1     private void closeDeletion(int d) {
 2         // Adapted from Knuth Section 6.4 Algorithm R
 3         Object[] tab = table;
 4         int len = tab.length;
 5 
 6         Object item;
 7         for (int i = nextKeyIndex(d, len); (item = tab[i]) != null;
 8              i = nextKeyIndex(i, len) ) {
 9             int r = hash(item, len);
10             // 将后面的因为hash碰撞而存放的元素往前移
11             if ((i  i)) {
12                 // 将后面的元素往前移位
13                 tab[d] = item;
14                 tab[d + 1] = tab[i + 1];
15                 tab[i] = null;
16                 tab[i + 1] = null;
17                 d = i;
18             }
19         }
20     }