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: 下一次扩容的键值对数量, (即当前容量*负载因子)
主要方法
-
put(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)put(...) 方法最终都调用这个方法, 操作如下:
- 获取容器(table)大小, 如果容器未初始化, 则调用(
resize())初始化 - 如果table中(
hash&(n-1))值所在的桶是空, 则table[hash&(n-1)]直接指向当前对象(结束) - 否则, 如果找到 key 相同的键值对, 则直接将键值对的值设置为当前值, 返回旧值
- 如果当前对象是一个 TreeNode, 则直接插入到这个二叉树中, 如果值已存在, 替换并返回旧值, 否则插入到尾部返回 null
- 如果当前是链表, 则遍历, 有相同的key就替换, 没有就插入到尾部, 如果链表长度大于等于 TREEIFY_THRESHOLD 则转成二叉树(TreeNode)
- 获取容器(table)大小, 如果容器未初始化, 则调用(
-
removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)- 如果table 为空, 或者table[hash&(n-1)] 为空, 直接返回 null (结束)
- 查找 key 值相同的对象(从链表或者TreeNode中查找)
- 查找到, 则再匹配 value, 如果有需要的话, 匹配成功则删除这个键值对
数据结构
Paste_Image.png
TreeNode 是一个红黑树, 查找删除的复杂度都是 Log(n), 上图的树画的不对
总结
- HashMap 全部方法都没有进行同步处理的, 因此尽量不要在多线程中使用
- Java8 的 HashMap 跟以前的版本不一样了, 代码有了更多的优化
- 现在的版本使用二叉树(TreeNode)解决 key 冲突时的查找效率问题
- 现在的要求容器大小必须是2的幂次, 计算键值对所在的桶因此页不需要使用取余符号了(位运算效率高)
- 以前的版本为了解决某个 key 冲突比较多, 在 rehash() 时会将容器扩大1倍+1, 这样原来冲突的key现在极有可能不冲突了. 而现在的版本, 当容器扩大时, 原来冲突的现在很有可能继续冲突, 使用二叉树优化, 可以达到更好的效果
