HashMap重点知识点整理

HashMap的内部结构1.8 版本有哪些变化HashMap 容量的初始化HashMap 的数据插入当两个对象的 hashcode 相同会如何 哈希函数的实现为什么用异或运算符 HashMap 是否线程安全解决线程不安全方法HashMap 和 HashTable 的区别ConcurrentHashMap 的分段锁原理 HashMap，TreeMap，LinkedHashMap 使用场景HashMap内部节点是无序的，根据 hash 值随机插入 链表转红黑树为什么长度阈值是8为什么当链表长度达到阈值转用红黑树，而不是二叉查找树？Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同为什么 ConcurrentHashMap 比 HashTable 效率要高ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLockConcurrentHashMap 的并发度是什么？

HashMap的内部结构

JDK1.8 版本 HashMap 内部使用数组 + 链表或红黑树。结合数组和链表的优点。当链表长度超过 8 时，链表转换为红黑树。

1.8 版本有哪些变化

1.数组+链表改成了数组+链表或红黑树；

防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)

2.链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；

1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环

3.扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；

4.在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容。

HashMap 容量的初始化

如果new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

HashMap 的数据插入

1.判断数组是否为空，为空进行初始化;

2.不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;

3.查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；

4.存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；

5.如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)

6.如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64， 大于的话链表转换为红黑树；

7.插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

当两个对象的 hashcode 相同会如何

因为 hashCode 相同，不一定就是相等的（equals 方法比较），所以两个对象所在数组的下标相同，"碰撞"就此发生。又因为 HashMap 使用链表存储对象，这个 Node 会存储到链表中。

哈希函数的实现

JDK 1.8 中，是通过 hashCode() 的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效和质量来考虑的，减少系统的开销，也不会造成因为高位没有参 与下标的计算，从而引起的碰撞。

一定要尽可能降低hash碰撞，越分散越好；算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

为什么用异或运算符

保证了对象的 hashCode 的 32 位值只要有一位发生改变，整个 hash() 返回值就会改变。 尽可能的减少碰撞

HashMap 是否线程安全

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。

解决线程不安全方法

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。

HashMap 和 HashTable 的区别

HashMap 是线程不安全的，HashTable 是线程安全的；由于线程安全，所以 HashTable 的效率比不上 HashMap；HashMap 最多只允许一条记录的键为 null，允许多条记录的值为 null，而 HashTable 不 允许；HashMap 默认初始化数组的大小为 16，HashTable 为 11，前者扩容时，扩大两倍， 后者扩大两倍+1HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

ConcurrentHashMap 的分段锁原理

1.7 采取 分段锁 原理；1.8采取 CAS + Synchronized 实现1.7 与 1.8 中 size() 方法 实现不同

JDK1.7 和 JDK1.8 对 size 的计算是不一样的。 1.7 中是先不加锁计算三次，如果三次结果不一样在加锁。

JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算，最终通过 baseCount 和 遍历 CounterCell 数组得出 size。

JDK 8 推荐使用 mappingCount(） 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值。

参考1

参考2

ConcurrentHashMap成员变量使用volatile 修饰，免除了指令重排序，同时保证内存可见性，另外使用CAS操作和synchronized结合实现赋值操作，多线程操作只会锁住当前操作索引的节点。

HashMap，TreeMap，LinkedHashMap 使用场景

一般情况下，使用最多的是 HashMap。

HashMap：在 Map 中插入、删除和定位元素时；TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。

HashMap内部节点是无序的，根据 hash 值随机插入

有序的 Map：LinkedHashMap 和 TreeMap

LinkHashMap 如何实现有序？ LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。 TreeMap 如何实现有序？ TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。

链表转红黑树为什么长度阈值是8

红黑树转链表阈值是6

经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，概率说话。。因为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生。

为什么当链表长度达到阈值转用红黑树，而不是二叉查找树？

选择红黑树是为了解决二叉查找树的缺陷，二叉查找树在特殊情况下会变成一条线性 结构（这就跟原来使用链表结构一样了，造成很深的问题），遍历查找会非常慢。红黑树在插入新数据后可能需要通过左旋，右旋、变色这些操作来保持平衡，引入红黑树 就是为了查找数据快，解决链表查询深度的问题，我们知道红黑树属于平衡二叉树，但是为 了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少，所以当 长度大于 8 的时候，会使用红黑树，如果链表长度很短的话，根本不需要引入红黑树，引入 反而会慢。

Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同

ConcurrentHashMap 类（是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效 的 HashMap 实现）。 HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）； 而针对 ConcurrentHashMap，在 JDK 1.7 中采用 分段锁的方式；JDK 1.8 中直接采用了 CAS （无锁算法）+ synchronized。

为什么 ConcurrentHashMap 比 HashTable 效率要高

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻 塞； ConcurrentHashMap JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分 成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。

JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry）。锁粒度降低了。

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock

①、粒度降低了； ②、JVM 开发团队没有放弃 synchronized，而且基于 JVM 的 synchronized 优化空间更大， 更加自然。 ③、在大量的数据操作下，对于 JVM 的内存压力，基于 API 的 ReentrantLock 会开销更 多的内存。

ConcurrentHashMap 的并发度是什么？

程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16， 且可以在构造函数中设置。 当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小 2 幂指数作为实际并 发度（假如用户设置并发度为 17，实际并发度则为 32）