目录
- content
- append
- content
HashMap 的数据结构:
数组 + 链表 (Java7 之前包括 Java7)
数组 + 链表 + 红黑树 (从 Java8 开始)
PS: 这里的《红黑树》与链表都是链式结构.
HashMap 内部维护了一个数组, 数组中存放链表的链首或红黑树的树根.
当链表长度超过 8 时, 链表就转换为红黑树, 利用红黑树快速增删改查的特点提高 HashMap 的性能; 在红黑树结点数量小于 6 时, 红黑树转变为链表.
下面分别为上面两种数据结构的图示:
[定位算法]
增加, 查找, 删除等操作都需要先定位到 table 数组的某个索引处.
定位算法为三步: 取 key 的 hashCode 值, 高位运算, 取模运算得到索引位置.(代码如下)
- static final int hash(Object key) {
- int h;
- // h = key.hashCode() 第一步 取 hashCode 值
- // h ^ (h>>> 16) 第二步 高位参与运算 Java8 优化了高位算法, 优化原理忽略
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
- // java7 中这是一个单独的方法, java8 没有了这个方法但是原理依旧
- static int indexFor(int h, int length) {
- return h & (length-1); // hash(key) & (length-1) 第三步 取模
- }
取模运算 h & (length -1) 的结果最大值为 length -1, 不会出现数组下标越界的情况.
为什么要做高位运算?
如果 hashCode 值都大于 length, 而且这些 hashCode 的低位变化不大, 就会出现很多冲突, 举个例子:
假设数组的初始化容量为 16(10000), 则 length -1 位 15(1111).
假设有几个对象的 hashCode 分别为 1100 10010,1110 10010,11101 10010, 如果不做高位运算, 直接使用它们做取模运算的结果将是一致的.
如果所有元素中多数元素属于这种情况, 将会导致元素分布不均匀, 而对 hashCode 进行高位运算能解决这个问题, 使高位对低位造成影响改变低位的值, 从而变相地使高位也参与运算.
append
[Q] 负载因子与性能的关系
负载因子默认值为 0.75, 意味着当数组实际填充量占比达到 3/4 时就该扩容了.
负载因子越大, 扩容次数必然越少, 数组的长度越小, 减少了空间开销; 这就会导致 hash 碰撞越多, 增加查询成本.
默认值 0.75 在时间和空间成本上寻求一种折衷.
[Q] 为什么要扩容
因为随着元素量的增大, hash 碰撞的概率越来越大, 虽然使用链地址法能够解决存储问题, 但是长长的链表会让 HashMap 失去快速检索的优势, 而扩容能解决这个问题.
来源: https://www.cnblogs.com/xmsx/p/9750299.html