HashMap学习笔记

HashMap学习笔记

1. 初始容量
   在构造HashMap的时候根据预期的entry数量考虑初始容量和负载因子，这样可以尽可能的避免rehash。如果有很多kv要存在HashMap中，创建一个足够大的实例来存储要比让hashmap需要扩容时自动rehash要更加高效。

2. 负载因子
   load factor = entry.size / hashmap capacity

3. Comparable
   使用许多相同hashCode的key肯定会降低性能。为了改善冲突，当key是Comparable时，这个类会通过在key之间比较顺序来打破纽带。从java8开始，当hash 冲突的长度超过一定的阈值（8）并且map的容量超过一定的阈值（64），hashMap会把链表变成一个红黑树（一直平衡）。当HashMap实现尝试在树中查找新条目的位置时，首先检查当前值和新值是否是Comparable。如果不是的话，只能通过tieBreakOrder(Object a, Object b)来比较，这个方法会先比较class name，然后使用System.identityHashCode。如果是Comparable的，那么事情就简单了，通过compareTo接口就可以比较了。值得一提的是，根据compareTo方法（该方法返回0），当两个Comparable键结果相等时，将使用相同的tieBreakOrder方法。

4. resize（初始化table或者对table进行double 扩容）

   1. 如果没有初始化，那么此方法就是初始化table的方法，默认的capacity是16，负载因子是0.75。
   2. 已经初始化，那么要对

5. rehash过程（参考链接）

   • java7 resize过程中每一个元素都要重新通过indexFor(hash)计算位置，然后将元素插入到新数据到链表头部，形成了反序（在并发的情况下有可能形成回环）。
   • java8 采用2倍扩容，扩容后，resize过程中，每一个元素通过与oldCap取&，看看结果是1还是0，如果是0的话，分配新表的原索引位置，如果是1的话，分配到新表的（原索引位置+oldCap）位置，两者都是将元素插入到链表尾（保持了元素相对顺序没有发生变化）。这个原因是在根据hash定位数组索引位置的时候是通过hash&(n-1)来做的，2倍扩容以后hash&(n-1)的结果只有高位会发生变化，只有发生变化的才需要迁移到新的索引位置，可以通过hash&oldCap得到高位的值，通过高位的值是否为1来判断采取的动作

6. 线程安全
   HashMap是非线程安全的，如果有多个线程并发地对hashmap进行结构性变化，那么就必须额外的同步。通常是由同步持有HashMap实例的对象来完成对hashmap的同步的。如果没有这样的对象存在，这个map应该被Collections.synchronizedMap方法来包装，最好是在创建时完成，来阻止意外的非同步的对hashmap的访问。HashMap的所有视图方法都是Fail-Fast的。