8.Java SDK源码分析系列笔记-JDK1.7 HashMap

目录

• 1. 问题
  
  
  
  • 1.1. 手写HashMap
    
    
    
    • 1.1.1. Entry
      
    • 1.1.2. put操作
      
    • 1.1.3. get操作
      
    • 1.1.4. remove操作
      
    
    
  • 1.2. 为什么构造函数中需要把capacity转成2的power
    
  • 1.3. 扩容操作
    
    
    
    • 1.3.1. 扩容的逻辑
      
    
    
  • 1.4. 如何解决Hash冲突的？
    
  • 1.5. 发生Hash冲突的时候是头插入还是尾插入？
    
  • 1.6. 并发put的后get发生死循环？
    
    
    
    • 1.6.1. 参考
      
    
    
  • 1.7. key可以为NULL么
    
  • 1.8. ConcurrentModificationException
    
  
  
• 2. 参考
  

1. 问题

1.1. 手写HashMap

1.1.1. Entry

1. class Entry<K,V> implements Map.Entry<K,V> {
2.     final K key;
3.     V value;
4.     Entry<K,V> next;//链地址法
5.     }

复制代码

1.1.2. put操作

1. public V put(K key, V value) {
2.         //计算Hash并计算数组中的下标
3.     int hash = hash(key);
4.     int i = indexFor(hash, table.length);
5.         //先遍历链表查看是否有相等的key，有替换value
6.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
7.         Object k;
8.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9.             V oldValue = e.value;
10.             e.value = value;
11.             e.recordAccess(this);
12.             return oldValue;
13.         }
14.     }
15.         //没有则使用头插法
16.     addEntry(hash, key, value, i);
17.     return null;
18. }

复制代码

1.1.3. get操作

1. final Entry<K,V> getEntry(Object key) {
2.                                 //计算hash值
3.     int hash = (key == null) ? 0 : hash(key);
4.                     //计算数组下标
5.                     //遍历链表中的每个元素判断key相等
6.     for (Entry<K,V> e = table[indexFor(hash, table.length)];
7.          e != null;
8.          e = e.next) {
9.         Object k;
10.         if (e.hash == hash &&
11.             ((k = e.key) == key || (key != null && key.equals(k))))
12.             return e;
13.     }
14.     return null;
15. }

复制代码

1.1.4. remove操作

1. final Entry<K,V> removeEntryForKey(Object key) {
2.                         //找到相应的链表
3.     int hash = (key == null) ? 0 : hash(key);
4.     int i = indexFor(hash, table.length);
5.     Entry<K,V> prev = table[i];
6.     Entry<K,V> e = prev;
8.                         //遍历链表删除（其实就是链表的删除操作，需要一个prev和一个current）
9.     while (e != null) {
10.         Entry<K,V> next = e.next;
11.         Object k;
12.         if (e.hash == hash &&
13.             ((k = e.key) == key || (key != null && key.equals(k)))) {
14.             modCount++;
15.             size--;
16.             if (prev == e)
17.                 table[i] = next;
18.             else
19.                 prev.next = next;
20.             e.recordRemoval(this);
21.             return e;
22.         }
23.         prev = e;
24.         e = next;
25.     }
27.     return e;
28. }

复制代码

1.2. 为什么构造函数中需要把capacity转成2的power

跟indexFor计算数组下标有关

1. static int indexFor(int h, int length) {
2.     return h & (length-1);
3. }

复制代码

不是计算Hash后对table.length取余，而是与操作。

1. h:                        1001 1001
2. length:                0001 0000
3. length-1:        0000 1111
4. &:                        0000 1001

复制代码

如上&的结果保留的是h的最后4bit。
1.3. 扩容操作

什么时候发生扩容

1. //当前hashmap中的数量（包括链表中的）已经超过阈值时扩容
2. if ((size >= threshold) && (null != table[bucketIndex])) {
3.         resize(2 * table.length);//两倍的数组长度
4.     }

复制代码

1.3.1. 扩容的逻辑

参考

并发put的后get发生死循环

1.4. 如何解决Hash冲突的？

链地址法。即数组+链表
1.5. 发生Hash冲突的时候是头插入还是尾插入？

头插入。这样效率是最高的。

1. void createEntry(int hash, K key, V value, int bucketIndex) {
2.                         //保存旧的链表头部
3.     Entry<K,V> e = table[bucketIndex];
4.                     //创建一个新的entry，并把next指向旧的链表头部。
5.                     //新的链表头部指向这个新的entry
6.     table[bucketIndex] = new Entry<>(hash, key, value, e);
7.     size++;
8. }

复制代码

1.6. 并发put的后get发生死循环？

1.7的put操作是头插入的。两个线程同时put并且resize的时候会出现环形链表的情况，所以get操作会出现死循环
resize中有个transfer，需要把旧数组中的所有元素转移到新的数组中

1. void transfer(Entry[] newTable, boolean rehash) {
2.     int newCapacity = newTable.length;
3.                             //遍历数组中的每个元素（链表）
4.     for (Entry<K,V> e : table) {
5.                                             //遍历链表中的每个元素
6.         while(null != e) {
7.             Entry<K,V> next = e.next;
8.                                                 //重新计算hash
9.             if (rehash) {
10.                 e.hash = null == e.key ? 0 : hash(e.key);
11.             }
12.                                                     //计算新的下标
13.             int i = indexFor(e.hash, newCapacity);
14.                                                     //头插法
15.             e.next = newTable[i];
16.             newTable[i] = e;
17.             
18.             e = next;
19.         }
20.     }
21. }

复制代码

1.6.1. 参考

https://blog.csdn.net/zhuqiuhui/article/details/51849692
1.7. key可以为NULL么

可以。        1.7中为table中的第一个元素。
put操作中判断key为NULL的时候，会调用putForNullKey

1. private V putForNullKey(V value) {
2.                         //在数组第一个元素的链表上遍历，找到key为null的则替换value并返回旧value
3.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {
4.         if (e.key == null) {
5.             V oldValue = e.value;
6.             e.value = value;
7.             e.recordAccess(this);
8.             return oldValue;
9.         }
10.     }
11.     modCount++;
12.                     //没有则插入到数组第一个位置
13.     addEntry(0, null, value, 0);
14.     return null;
15. }

复制代码

1.8. ConcurrentModificationException

参考：fail-fast.md
遍历时（get）执行删除操作（remove）会抛出这个异常，这叫做fast-fail机制
这是modCount和expectedCount不相等导致的
2. 参考

• java - Why is a ConcurrentModificationException thrown and how to debug it - Stack Overflow
  
• Avoiding the ConcurrentModificationException in Java | Baeldung
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！