HashMap学习总结

1、HashMap是基于数组和链表的，使用数组查找效率高，链表解决的是冲突的问题，如果冲突就放到链表里。

2、为什么使用数组而不是linkedlist或者arraylist，这是因为在hashmap中定位桶的位置是使用hash值对数组长度取模，查找效率要高于linkedlist，而arraylist的扩容机制是1.5倍，hashmap的扩容是2的幂。

3.hashmap 解决冲突的办法是再哈希

4、java8和java7对HashMap的实现有很大不同，主要解决java7中hashMap线程不安全，在对链表的扩容时是不排序的，扩容的实现方式是，比如原来有16个桶，因为是2倍扩容，所以会生成一个新的32个桶的hashtable，然后把原来的通过再次hash计算放到新的hashtable里，但是在处理链表的时候忽略了顺序，经典链表的方法，摘掉一个放到新的上面，这样就反了，如果是多线程的容易形成环路（虽然java8使用了红黑树，默认链表超过8就使用红黑树，但仍然是线程不安全的）

 

红黑树是啥，就是二叉平衡树，二叉树有个问题，比如说都是左孩子，效率就太低了。但平衡二叉树就保证了没有这个问题。

那么为啥是8呐？桶中的数量，就是链表的长度，服从一个值为0.5的泊松分布，超过8的概率是百万分之一，注释里有说明。

 

java8中计算hash值还有一处改动，高位右移16位，防止冲突。

另外就是扩容后，元素要么在原来的位置，要么在原位置移动2的幂的位置。

还有就是有安全隐患，2011年爆出来说，如果恶意在网址中输入大量字符串，哈希值相同（不同的字符串是有可能hash值相同的，因为下图）

String中hashcode的计算方式。

 

那么整个hash表就成为一个链表，就会有大量的链表，因为链表的缺点。。。。消耗cpu。就成为了DoS攻击。

tomcat自己做了一个小修复，设置了最大的参数数量，但oracle也做了一点修复，（再哈希）提供了新的seed，如果传的是String会用另外一种不是String的hashcode方法计算哈希。

5、什么时候扩容？

程序里有个阈值，0.75，超过初始容量的四分之三就会扩容，且扩容为2的幂，为什么？前边提到，计算桶的位置实际就是用hash值对数组长度取模，那扩容之后要取位置也这样吗？不，因为在cpu那个层面，除法的效率是比较低的，源码里写的是hash&（length-1），2的幂 = length，-1，末位就是1111，这样就可以很快的得到数组下标。