HashMap实现原理

0:当key相同时，底层的实现是新值替换旧值，不是覆盖。

1:HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干

2:HashMap数组每一个元素的初始值都是Null

3:Put方法的原理

调用Put方法的时候发生了什么呢？

比如调用 hashMap.put("apple", 0) ，插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）：

index = Hash（“apple”）

假定最后计算出的index是2，那么结果如下：

4:但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样

5:利用链表来解决

个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可

新来的Entry节点插入链表时，使用的是“头插法

6:Get方法的原理

首先会把输入的Key做一次Hash映射，得到对应的index

index = Hash（“apple”）

第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果

第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。

之所以把Entry6放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大

7:HashMap初始化长度是16，并且每次扩展或手动初始化时,长度必须是2的幂

8:为什么是16?这样设计有什么意义？

是为了服务于从key映射到index的Hash算法

从Key映射到HashMap数组的对应位置，会用到一个Hash函数：

index = Hash（“apple”）

如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。(位运算)

9:java8中如果 hash 值相同的 key 数量大于指定值(默认是8)时使用平衡二叉树来代替链表

这会将get()方法的性能从O(n)提高到O(logn)

1 HashMap为什么线程不安全?

1:个人认为:在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个 put 的 key 发生了碰撞(根据 hash 值计算的 bucket 一样)，那么根据 HashMap 的实现，这两个 key 会添加到数组的同一个位置，这样最终就会发生其中一个线程的 put 的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小* loadFactor ，这样就会发生多个线程同时对 Node 数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给 table，也就是说其他线程的都会丢失，并且各自线程 put 的数据也丢失

2:HashMap 线程不安全这一点，《Java并发编程的艺术》一书中是这样说的：

HashMap 在并发执行 put 操作时会引起死循环，导致 CPU 利用率接近100%。因为多线程会导致 HashMap 的 Node 链表形成环形数据结构，一旦形成环形数据结构，Node 的 next 节点永远不为空，就会在获取 Node 时产生死循环。

3:目前，只有ConcurrentHashMap,LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树

4:情况下使用平衡树什么时候会产生冲突?

由于在Java中两个不同的对象可能有一样的hashCode,所以不同的键可能有一样hashCode，从而导致冲突的产生。

5:HashMap在处理冲突时使用链表存储相同索引的元素。

从Java 8开始，HashMap，ConcurrentHashMap和LinkedHashMap在处理频繁冲突时将使用平衡树来代替链表，当同一hash桶中的元素数量超过特定的值便会由链表切换到平衡树，这会将get()方法的性能从O(n)提高到O(logn)。

当从链表切换到平衡树时，HashMap迭代的顺序将会改变。不过这并不会造成什么问题，因为HashMap并没有对迭代的顺序提供任何保证。

从Java 1中就存在的Hashtable类为了保证迭代顺序不变，即便在频繁冲突的情况下也不会使用平衡树。这一决定是为了不破坏某些较老的需要依赖于Hashtable迭代顺序的Java应用。

除了Hashtable之外，WeakHashMap和IdentityHashMap也不会在频繁冲突的情况下使用平衡树。

使用HashMap之所以会产生冲突是因为使用了键对象的hashCode()方法，而equals()和hashCode()方法不保证不同对象的hashCode是不同的。需要记住的是，相同对象的hashCode一定是相同的，但相同的hashCode不一定是相同的对象。

在HashTable和HashMap中，冲突的产生是由于不同对象的hashCode()方法返回了一样的值。

以上就是Java中HashMap如何处理冲突。这种方法被称为链地址法，因为使用链表存储同一桶内的元素。通常情况HashMap，HashSet，LinkedHashSet，LinkedHashMap，ConcurrentHashMap，HashTable，IdentityHashMap和WeakHashMap均采用这种方法处理冲突。

从JDK 8开始，HashMap，LinkedHashMap和ConcurrentHashMap为了提升性能，在频繁冲突的时候使用平衡树来替代链表。因为HashSet内部使用了HashMap，LinkedHashSet内部使用了LinkedHashMap，所以他们的性能也会得到提升。