HashMap

JDK 版本: 1.8.0_45

常量

• DEFAULT_INITIAL_CAPACITY = 16; 默认容器大小 2的整数幂
• MAXIMUM_CAPACITY = 1<<30; 最大容器大小 2的整数幂
• DEFAULT_LOAD_FACTOR = 0.75f; 负载因子, 当容器中的数据占用容器达到 75% 时, 进行扩容
• TREEIFY_THRESHOLD = 8; 当冲突的数据量到达这个值时, 转成二叉树存储
• UNTREEIFY_THRESHOLD = 6; resize 之后, 如果冲突的项小于这个值, 则转成链表形式
• MIN_TREEIFY_CAPACITY = 64; 如果容器大小小于这个值, 则不会使用二叉树, 而是先扩容,

主要成员变量

• table: 存放键值对的数组, 大小是2的整数次幂, 如果数据量超过了负载因子, 会自动扩容
• entrySet: 用于 keySet() 和 values()
• size: 键值对的数量
• modCount: 操作次数(增加/删除键值对), 处理集合全部元素时, 如果有其他线程操作集合则报错
• threshold: 下一次扩容的键值对数量, (即当前容量*负载因子)

主要方法

1. put(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

   put(...) 方法最终都调用这个方法, 操作如下:

   1. 获取容器(table)大小, 如果容器未初始化, 则调用(resize())初始化
   2. 如果table中(hash&(n-1))值所在的桶是空, 则table[hash&(n-1)]直接指向当前对象(结束)
   3. 否则, 如果找到 key 相同的键值对, 则直接将键值对的值设置为当前值, 返回旧值
   4. 如果当前对象是一个 TreeNode, 则直接插入到这个二叉树中, 如果值已存在, 替换并返回旧值, 否则插入到尾部返回 null
   5. 如果当前是链表, 则遍历, 有相同的key就替换, 没有就插入到尾部, 如果链表长度大于等于 TREEIFY_THRESHOLD 则转成二叉树(TreeNode)

2. removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

   1. 如果table 为空, 或者table[hash&(n-1)] 为空, 直接返回 null (结束)
   2. 查找 key 值相同的对象(从链表或者TreeNode中查找)
   3. 查找到, 则再匹配 value, 如果有需要的话, 匹配成功则删除这个键值对

数据结构

Paste_Image.png

TreeNode 是一个红黑树, 查找删除的复杂度都是 Log(n), 上图的树画的不对

总结

1. HashMap 全部方法都没有进行同步处理的, 因此尽量不要在多线程中使用
2. Java8 的 HashMap 跟以前的版本不一样了, 代码有了更多的优化
   1. 现在的版本使用二叉树(TreeNode)解决 key 冲突时的查找效率问题
   2. 现在的要求容器大小必须是2的幂次, 计算键值对所在的桶因此页不需要使用取余符号了(位运算效率高)
   3. 以前的版本为了解决某个 key 冲突比较多, 在 rehash() 时会将容器扩大1倍+1, 这样原来冲突的key现在极有可能不冲突了. 而现在的版本, 当容器扩大时, 原来冲突的现在很有可能继续冲突, 使用二叉树优化, 可以达到更好的效果