HashMap和ConcurrentHashMap 源码关键点解

第一部分：关键源码讲解

1.HashMap  是如何存储的？

a.底层是一个数组 tab

b. hash=hash(key) ，然后根据数组长度n和hash值，决定当前需要put的元素对应的数组下标，

hash算法见红框。

2.数组长度是固定的，HashMap 可以无限put(k,v) ,为什么？

HashMap  的元素个数大于threshold的时候，会进行resize() 扩容

3.如何实现扩容的？

扩容就是通过 resize() , 重新创建一个新数组，对所有元素rehash,放到新数组相应位置。

扩容代价是很大的，所以很多公司编码规范都有一条，合理设置hashMap的InitialCapicity,

禁止直接用HashMap()

4.Hash 冲突是什么？怎么解决这个问题？

Hash 冲突： 假如一个学校有366个同学，一年365天，那么至少有两个同学是同一天生日，这就是hash冲突。用代码来说，不同的key 经过计算p = tab[i = (n - 1) & hash] 对应同一个p

如何解决:

p在有的翻译文档中叫桶，一个桶可以装多个，怎么装? 链表或者红黑树。

以上代码中 else if 部分是红黑树

else 部分是链表 ，链表中如果冲突元素个>=TREEIFY_THRESHOLD-1,会将链表转换成红黑树。

因为元素个数很多时，红黑树比链表性能更好。

5.HashMap 是不是线程安全的，如何解决线程安全问题？

答案是NO，如何解决：

a.对整个map加锁。

b.直接用ConcurrentHashMap

对f加锁了，就是对桶加锁，就是传说中的分段锁机制。

在保证安全的前提下，加锁的范围越小，则程序性能越高，自己写代码时切记胡乱在方法上加synchronized

6.HashMap 和 hash()  equals() 方法的关系

面试中面试官会问重写equals()方法要注意是什么，答案是hash()也要重写。

不重写会引起HashMap 等集合类使用的混乱。

比如类Person(id,name)，重写了 equals(Object obj){... reutrn this.id==obj.id}，没有重写hash(), 那么从类定义上来说，只要id相等就是同一个人，当我们Person作为key，放入两个Person对象(id相等)到HashMap的时候，那么就翻车了，HashMap 会有两个元素，而我们期望的只保留一个。

第二部分：实验验证

1.验证ConcurrentHashMap 线程安全。

2.重写equals()不重写hash() 翻车问题验证。

http://skycity.today/?thread-38.htm