HashMap 相关知识点总结

目录

HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8

HashMap 的 put 方法的执行过程？

HashMap 的 get 方法的执行过程？

HashMap 的 resize 方法的执行过程？

HashMap 的 size 为什么必须是 2 的整数次方？

HashMap 多线程死循环问题？

HashMap 的 get 方法能否判断某个元素是否在 map 中？

HashMap 与 HashTable 的区别是什么？

HashMap 与 ConcurrentHashMap 的区别是什么?

HashTable 和 ConcurrentHashMap 的区别？

HashSet 的实现原理是什么？

HashSet 怎么保证元素不重复的？

---

HashMap 的实现原理/底层数据结构？JDK1.7 和 JDK1.8

        JDK1.7：Entry数组 + 链表

        JDK1.8：Node 数组 + 链表/红⿊树，当链表上的元素个数超过 8 个并且数组⻓度 >= 64 时⾃动转化成红⿊树，节点变成树节点，以提⾼搜索效率和插⼊效率到 O(logN)。Entry 和 Node 都包含 key、value、hash、next 属性。

HashMap 的 put 方法的执行过程？

        当我们想往⼀个 HashMap 中添加⼀对 key-value 时，系统⾸先会计算 key 的 hash 值，然后根据 hash 值确认在 table 中存储的位置。若该位置没有元素，则直接插⼊。否则迭代该处元素链表并依次⽐较其 key 的 hash 值。如 果两个 hash 值相等且 key 值相等(e.hash == hash && ((k = e.key) == key || key.equals(k)))，则⽤新的 Entry 的 value 覆盖原来节点的 value。如果两个 hash 值相等但 key 值不等 ，则将该节点插⼊该链表的链头。

HashMap 的 get 方法的执行过程？

        通过 key 的 hash 值找到在 table 数组中的索引处的 Entry，然后返回该 key 对应的 value 即可。 在这⾥能够根据 key 快速的取到 value 除了和 HashMap 的数据结构密不可分外，还和 Entry 有莫⼤的关系。 HashMap 在存储过程中并没有将 key，value 分开来存储，⽽是当做⼀个整体 key-value 来处理的，这个整体就是 Entry 对象。同时 value 也只相当于 key 的附属⽽已。在存储的过程中，系统根据 key 的 HashCode 来决定 Entry 在 table 数组中的存储位置，在取的过程中同样根据 key 的 HashCode 取出相对应的 Entry 对象（value 就包含在 ⾥⾯）。

HashMap 的 resize 方法的执行过程？

有两种情况会调⽤ resize ⽅法：

1. 第⼀次调⽤ HashMap 的 put ⽅法时，会调⽤ resize ⽅法对 table 数组进⾏初始化，如果不传⼊指定值，默 认⼤⼩为 16。

2. 扩容时会调⽤ resize，即 size > threshold 时，table 数组⼤⼩翻倍。 每次扩容之后容量都是翻倍。扩容后要将原数组中的所有元素找到在新数组中合适的位置。

        当我们把 table[i] 位置的所有 Node 迁移到 newtab 中去的时候：这里面的 node 要么在 newtab 的 i 位置（不 变），要么在 newtab 的 i + n 位置。也就是我们可以这样处理：把 table[i] 这个桶中的 node 拆分为两个链表 l1 和 l2：如果 hash & n == 0，那么当前这个 node 被连接到 l1 链表；否则连接到 l2 链表。这样下来，当遍历完 table[i] 处的所有 node 的时候，我们得到两个链表 l1 和 l2，这时我们令 newtab[i] = l1，newtab[i + n] = l2，这 就完成了 table[i] 位置所有 node 的迁移（rehash），这也是 HashMap 中容量⼀定的是 2 的整数次幂带来的⽅便 之处。

HashMap 的 size 为什么必须是 2 的整数次方？

1. 这样做总是能够保证 HashMap 的底层数组⻓度为 2 的 n 次⽅。当 length 为 2 的 n 次⽅时，h & (length - 1) 就相当于对 length 取模，⽽且速度⽐直接取模快得多，这是 HashMap 在速度上的⼀个优化。⽽且每次扩容时都是翻倍。

2. 如果 length 为 2 的次幂，则 length - 1 转化为⼆进制必定是 11111……的形式，在与 h 的⼆进制进⾏与操作 时效率会⾮常的快，⽽且空间不浪费。但是，如果 length 不是 2 的次幂，⽐如：length 为 15，则 length - 1 为 14，对应的⼆进制为 1110，在于 h 与操作，最后⼀位都为 0 ，⽽ 0001，0011，0101，1001，1011， 0111，1101 这⼏个位置永远都不能存放元素了，空间浪费相当⼤，更糟的是这种情况中，数组可以使⽤的位 置⽐数组⻓度⼩了很多，这意味着进⼀步增加了碰撞的⼏率，减慢了查询的效率，这样就会造成空间的浪费。

HashMap 多线程死循环问题？

        主要是多线程同时 put 时，如果同时触发了 rehash 操作，会导致 HashMap 中的链表中出现循环节点，进⽽使得 后⾯ get 的时候，会死循环。

HashMap 的 get 方法能否判断某个元素是否在 map 中？

        HashMap 的 get 函数的返回值不能判断⼀个 key 是否包含在 map 中，因为 get 返回 null 有可能是不包含该 key，也有可能该 key 对应的 value 为 null。因为 HashMap 中允许 key 为 null，也允许 value 为 null。

HashMap 与 HashTable 的区别是什么？

        1. HashTable 基于 Dictionary 类，⽽ HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值 的类的抽象⽗类，⽽ AbstractMap 是基于 Map 接⼝的实现，它以最⼤限度地减少实现此接⼝所需的⼯作。

        2. HashMap 的 key 和 value 都允许为 null，⽽ Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调⽤ putForNullKey ⽅法进⾏处理，⽽对 value 没有处理；Hashtable 遇到 null，直接 返回 NullPointerException。

        3. Hashtable 是线程安全的，⽽ HashMap 不是线程安全的，但是我们也可以通过 Collections.synchronizedMap(hashMap)，使其实现同步。

        HashTable的补充： HashTable 和 HashMap 的实现原理⼏乎⼀样，差别⽆⾮是

        1. HashTable 不允许 key 和 value 为 null；

         2. HashTable 是线程安全的。但是 HashTable 线程安全的策略实现代价却太⼤了，简单粗暴，get/put 所有相 关操作都是 synchronized 的，这相当于给整个哈希表加了⼀把⼤锁，多线程访问时候，只要有⼀个线程访问 或操作该对象，那其他线程只能阻塞，相当于将所有的操作串⾏化，在竞争激烈的并发场景中性能就会⾮常 差。

HashMap 与 ConcurrentHashMap 的区别是什么?

        HashMap 不是线程安全的，⽽ ConcurrentHashMap 是线程安全的。 ConcurrentHashMap 采⽤锁分段技术，将整个Hash桶进⾏了分段segment，也就是将这个⼤的数组分成了⼏个 ⼩的⽚段 segment，⽽且每个⼩的⽚段 segment 上⾯都有锁存在，那么在插⼊元素的时候就需要先找到应该插⼊ 到哪⼀个⽚段 segment，然后再在这个⽚段上⾯进⾏插⼊，⽽且这⾥还需要获取 segment 锁，这样做明显减⼩了 锁的粒度。

HashTable 和 ConcurrentHashMap 的区别？

        HashTable 和 ConcurrentHashMap 相⽐，效率低。 Hashtable 之所以效率低主要是使⽤了 synchronized 关键 字对 put 等操作进⾏加锁，⽽ synchronized 关键字加锁是对整张 Hash 表的，即每次锁住整张表让线程独占，致 使效率低下，⽽ ConcurrentHashMap 在对象中保存了⼀个 Segment 数组，即将整个 Hash 表划分为多个分段； ⽽每个Segment元素，即每个分段则类似于⼀个Hashtable；这样，在执⾏ put 操作时⾸先根据 hash 算法定位到 元素属于哪个 Segment，然后对该 Segment 加锁即可，因此， ConcurrentHashMap 在多线程并发编程中可是实 现多线程 put操作。

HashSet 的实现原理是什么？

        HashSet 的实现是依赖于 HashMap 的，HashSet 的值都是存储在 HashMap 中的。在 HashSet 的构造法中会初 始化⼀个 HashMap 对象，HashSet 不允许值重复。因此，HashSet 的值是作为 HashMap 的 key 存储在 HashMap 中的，当存储的值已经存在时返回 false。

HashSet 怎么保证元素不重复的？

public boolean add(E e) {
 return map.put(e, PRESENT)==null;
 }

        元素值作为的是 map 的 key，map 的 value 则是 PRESENT 变量，这个变量只作为放⼊ map 时的⼀个占位符⽽存 在，所以没什么实际⽤处。其实，这时候答案已经出来了：HashMap 的 key 是不能重复的，⽽这⾥HashSet 的元 素⼜是作为了 map 的 key，当然也不能重复了。