HashMap知识点汇集

1、HashMap实现的是Map接口，与ArrayList不一样，与Hashtable、LinkedHashMap一样

2、HashMap只允许一个key为null，如果有两个和正常的key冲突一样处理，HashMap非线程安全，可能会出现死锁等，多线程里使用的话可以用ConcurrentHashMap代替。

3、HashMap类似，不同的是它承自Dictionary类，线程安全，但是项目里面不会用，非多线程环境不如HashMap,多线程环境可以使用ConcurrentHashMap，因为ConcurrentHashMap使用分段锁，所以性能比HashTable好，ConcurrentHashMap后面会详细说。

4、HashMap的构成是数组+链表（链地址法），新增一个Entry是通过一个Entry的key的hashcode再通过HashMap的hash算法（高位运算）和取模得到数组的位置，添加到链表的尾部。当然Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高，当然数组的长度越大，Hash碰撞的概率就小，反之即使Hash很均匀，也会出现大量的Hash碰撞，解决方案就是好的Hash算法，以及扩容机制。

HashMap默认初始大小16（一般来说hash表的大小最好为素数，一般来说素数导致冲突的概率要小于合数，而hashmap中的hash表大小为2的N次方，是一个合数（这个是计算过后的，不是你传值多少初始大小就是多少）。HashMap采用这种非常规的设计，主要是为了在取模和扩容的时候做优化，同时为了减少冲突，HashMap定位hash桶索引的时候，也加入了高位参与运算的过程），负载因子0.75，0.75为综合考虑空间和时间的因素，建议不要改，如果想提高查询速度，可减小该值，如果想节省空间，可增大该值，负载因子可大于1，不过越大后期出现的hash碰撞会更多。在0.75的负载因子下，一般size <= threshold = table.length * loadFactor,也就是说元素数量肯定会小于哈希桶的长度，牺牲了空间提高时间效率。jdk1.8里新增了红黑树部分，当链表长度大于8时转化为红黑树，查询效率更高，时间复杂度有O(n)到O(logn)。简单数据类型的封装类hash散列还是均匀分布的，对于自定义Object，如果hashcode的方法不好的话容易造成分布不均匀。

HashMap是通过key的hashcode方法进行hash算法那后取模计算key对应的数组位置，找到对应的链表，再通过==或者equal()来判定二个key是否相等 。

参考一下美团团队的图：

5、HashMap线程不安全，会产生死锁的原因简单点就是resize的时候一个线程里扩容后一个keya的next为另一个keyb，而另一个keyb在扩容的时候由于发现自己的next就是那一个keya,这时候陷入死循环。jdk1.7里resize的时候会导致链表顺序倒过来，而1.8不会。1.8虽然不会因为顺序倒置而有死循环的问题，但是在并发的情况还是有可能有数据丢失的问题，这时候还是要用ConcurrentHashMap。

图文介绍可参考

<a href="http://www.importnew.com/22011.html">HashMap死锁图文解释</a>

6、HashSet是基于HashMap来实现的，HashSet里元素也是无序的

7、ArrayList集合是初始化容量为10，每次扩容后为1.5倍

8、Hashmap为什么大小是2的幂次。因为HashMap的采用高位运算

9、有序HashMap:LinkedHashMap,实现原理是HashMap+LinkedList,HashMap的数组链表+Entry之间的双向链表。