Java HashMap 原理分析

  • HashMap 线程不安全,其余两者可用于并发
  • Collections.synchronizedMap(HashMap) = HashTable
  • HashTable 全部上锁,ConcurrentHashMap 分段上锁,并发时后者效率更高
  • ConcurrentHashMap 扩展性更高
  • 单线程下,HashMap 效率最高

// 插入

HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

  • hash:表示 key 的 hash 值 ( key.hashCode() 与自身无符号右移 16 位后旳值求异或 )
  • key:待存储的 key 值
  • value:待存储的 value 值,从这个方法可以知道,HashMap 底层存储的是 key-value 的键值对,不只是存储了 value
  • onlyIfAbsent:这个参数表示,是否需要替换相同的 value 值,如果为 true,表示不替换已经存在的 value
  • evict:如果为 false,表示数组是新增模式

插入步骤:

  1. 判断当前 HashMap 数组是否为空,若为空 resize()
  2. 长度 - 1 和 hash 值进行按位与运算,得出对应位置
  3. 取出这个位置的值,若为 null 新增 Node;若不为空,判断节点 key 与传入的 key 是否一致,一致替换,不一致执行 链表/红黑树 插入操作
  4. 执行链表插入时,若插入前链表长度 >= 阈值(默认为8),则转成红黑树
  5. 判断当前 HashMap 长度是否即将超过阈值(默认 16 * 0.75 = 12 ),若将超过,resize()

// 扩容

HashMap.resize()

  • 条件:
  1. 若老数组为空,判断老的阈值是否大于 0,若大于 0 则新的容量 = 老的阈值,否则容量和阈值都初始化为默认值,即 16 和 12。
  2. 如果老的数组容量大于 0,首先判断是否大于等于HashMap的最大容量,如果true,将阈值设置为Integer的最大值,同时数组容量不变
  3. 正常扩容:容量和阈值均扩大到原来的两倍
  • 操作:
  1. JDK 1.7 及之前 重新计算 hash
  2. JDK 1.8 只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了,是 0 的话索引没变,是 1 的话索引变成 “原索引 + oldCap”,既可以省去重新 hash,又可以均匀的把之前的冲突的节点分散到新的 bucket  
  3. JDK 1.7 中 rehash 的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8 不会倒置

// 取值

HashMap.getNode(int hash, Object key)注意:

  • HashMap:Java 1.8 之前 单链表;1.8 单链表 + 红黑树(大于阈值时使用红黑树,阈值默认为8),查询效率更高 O(logn)。    
  • HashMap默认容量为16

部分内容来自网络