登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›8.Java SDK源码分析系列笔记-JDK1.7 HashMap

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

叟减 2025-6-30 10:41:02
目录

  • 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

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

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
叟减
2025-6-30 10:41:02

0

粉丝关注

9

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫