介绍

hashmap 实现Map<K,V> 接口，是一种key,value存储结构。在 哈希表 中进行添加，删除，查找等操作，性能十分之高，在不考虑哈希冲突的情况下，仅需一次定位即可完成， 时间复杂度 为O(1)。

HashMap的数据结构（jdk1.8版本）

在jdk1.8 中，HashMap采用数组+链表+ 红黑树 的实现。

Node类型的table存储。

而Node存储了key，value，hash值，以及指向下一个Node的引用，这就是 hash Map在哈希冲突时采用的链表结构

HashMap链表长度大于8时采用的TreeNode结构。

一个方法看明白HashMap的工作原理，由于方法太长，我将拆分进行解释。

1.准备一个key，和value然后,计算hash值。

2.如果table数组为null，则通过resize初始化数组table。通过hash值与数组长度（n-1）与得到该hash值所在数组中的位置i，如果计算出来table[i]==null 说明该hash值没有产生哈希冲突，于是创建一个Node对象保存hash值，key值，value值。然后将该Node对象放入table[i]中，并将table[i] 赋值给Node p。

3.发生hash冲突则将传入的key和table[i]（table[i]是赋值给p了的）上的key进行比较，如果传入的key和table[i]上的key完全相等或者equal方法相等，则进行值替换，然后结束方法如下：

值替换

4.如果发生hash冲突，且传入的key和Node p中的key不相同，则判断Node 是不是TreeNode，如果是TreeNode则按照红黑树的 算法 插入到TreeNode链表中，否则执行5.

5.如上图，先判断Node p的next有没有指向下一个节点，如果为null，则直接将p.next指向新创建Node对象上。否则遍历table[i]链表，查找链表中是否有key和该key相等，如果有则进行值替换，否则将创建Node加入到链表的尾部。然后判断当前链表大小是不是大于TREEIFY_THRESHOLD，

如果大于等于8 则进行treeifyBean操作，在该方法中，如果table数组的大小小于64，则进行先进行table数组扩容操作，否则将链表转换为红黑树链表的数据结构。

至此，hashMap的添加过程结束了，由于红黑树的添加过程十分复杂，暂时不介绍，大家知道就可以了。

一张图说明白HashMap 的工作原理。

总结：

1. HashMap 通过hash算法实现key，value的快速存取。

2.hashmap 添加新值的过程总结

计算hash值与数组长度(n-1)相与得到该hash值映射到数组中的位置i，node p=table[i]。

如果该p为null直接将新的key，value构造一个Node对象放到table[i]中。

如果table[i]不为null，则发生了hash冲突，然后比较table[i] 的key和新的key是否相等，如果相等则将table[i] 的value替换为传入的value。

如果上述方法还没解决好冲突，则判断table[i]是不是红黑树的结构（TreeNode），如果是红黑树的结构则使用红黑树的算法进行插入。

否则table[i]就是普通链表的结构，然后遍历该链表，逐一比较该key和链表中的key是否相同，如果相同则将链表中相等key的那个Node的value替换为新的value值，否则构建一个新的Node加入到链表的尾部，然后再判断链表大小是否大于8，如果大于8则进行红黑树的转换。

3.HashMap 在添加新元素的过程中可能触发生table大小自动扩展，这时候会将所有的值重新计算hash值，然后放入到新的table数组中，这个过程是十分消耗性能的，所以我们在初始化HashMap时要根据数据场景合理的指定HashMap初始化的大小，可以降低hash冲突和resize发生的概率，提升HashMap的性能。

4.HashMap不是线程安全的，在多线程环境下使用可能导致严重的错误，在多线程环境下请使用ConcurrentHashMap,性能也是极好的。

5.jdk1.7 实现采用哈希算法+数组+普通链表实现，jdk1.8采用hash算法+数组+链表+红黑树实现。

6.数组长必须是2的n次幂。因为2的n幂减一转换成二进制就是全为1的码，能高效的计算key映射到数组中的位置。

7.红黑树执行查找、插入、删除等操作，的时间复杂度为O(lgn)，高度至多为2lg(n+1),链表节点很多的时候红黑树性能比普通链表高很多。

8.看到这里你也应该明白了如果key是一个对象的话，那么一般应该重写hashcode和equals方法。