HashMap相关~

HashMap相关~

Scroll Down

HashMap相关

存储结构

HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的

数组是 HashMap 的主体,链表是为了解决hash冲突而存在的,采用的是链地址法

在这里插入图片描述

​ 当数组table中某个元素的链表长度大于8的时候,开始尝试进行树化,如果此时table.length小于64,则对数组扩容,否则对链表进行树化。(重点哦~)

简单的看完了它的存储结构,接下来看看它比较重要的一些参数

Hashmap的一些默认构造参数

 int threshold;             // 所能容纳的key-value对的最大值
 final float loadFactor;    // 负载因子
 int modCount;   //记录当前集合被修改的次数
 int size; //实际存在的键值对的数量

​ table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor。当存在的键值对达到threshold后,进行扩容,扩容成员来的两倍。

索引计算

​ 了解完了存储结构的一些知识点后,我们再来看看hashmap是如何确定即将添加元素应该放在数组table的哪个节点(索引)的。

​ 首先根据node的key的值计算出hashcode的值,然后根据hashcode计算出hash值,最后通过hash&(length-1)计算得到存储的位置。看看源码的实现:

// jdk1.8
static final int hash(Object key) {   
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    /* 
     h = key.hashCode() 为第一步:取hashCode值
     h ^ (h >>> 16)  为第二步:高位参与运算
    */
}

//取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。
if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

img

为什么要 hashcode 异或其右移十六位的值?

可以在数组 table 长度比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销

为什么 hash 值要与length-1相与?

这里的计算和用hash值对数组长度取模的运算时一样的,但是取模运算比与运算慢很多。

put方法

简要流程如下:

  1. 首先根据 key 的值计算 hash 值,找到该元素在数组中存储的下标;
  2. 如果数组是空的,则调用 resize 进行初始化;(第一次put的时候进行初始化)
  3. 如果没有哈希冲突直接放在对应的数组下标里;
  4. 如果冲突了,且 key 已经存在,就覆盖掉 value;
  5. 如果冲突后,发现该节点是红黑树,就将这个节点挂在树上;
  6. 如果冲突后是链表,判断该链表是否大于 8 ,如果大于 8 并且数组容量小于 64,就对数组进行扩容(resize);如果链表节点大于 8 并且数组的容量大于 64,则将当前节点的链表转换为红黑树;

jdk1.7和1.8put方法有什么不同

①解决哈希冲突时,JDK1.7 只使用链表,JDK1.8 使用链表+红黑树,当满足一定条件,链表会转换为红黑树。

②链表插入元素时,JDK1.7 使用头插法插入元素,在多线程的环境下有可能导致环形链表的出现,扩容的时候会导致死循环。

扩容机制

JDK1.7

​ 使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里,并且需要重新计算数组的下标。

​ newTable[i] 的引用赋给了 e.next ,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话)

JDK1.8

对比JDK1.7的优化

第一点:

​ resize 之后,元素的位置在原来的位置,或者原来的位置 +oldCap (原来哈希表的长度)。不需要像 JDK1.7 的实现那样重新计算所有元素的hash 。

​ 只需要看看原来的 hash 值新增的那个bit是1还是0就好了(因为扩容是乘以2,并且是与运算,所以看新增的bit即可),如果新增的Bit是0的话索引不变,是1的话索引变成“原索引 + oldCap ”。省去了重新计算 hash 值的时间。

​ JDK1.7 中 rehash 的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置(头插法)。JDK1.8 不会倒置,使用尾插法。

相关问题

为什么用在长度为8的时候转换成红黑树呢?

红黑树需要进行左旋,右旋,变色这些操作来保持平衡,而单链表不需要。

当元素小于 8 个的时候,此时做查询操作,链表结构已经能保证查询性能,超过8了以后,红黑树查询平均时间复杂度为o(nlogn),查询效率更加快,所以转换成红黑树。

如果一开始就用红黑树结构,元素太少,新增效率又比较慢,浪费性能。

为什么要用红黑树呢,可以用二叉搜索树嘛?

二叉搜索树是一种节点值之间具有一定数量级次序的二叉树,对于树中每个节点:

  • 若其左子树存在,则其左子树中每个节点的值都不大于该节点值;
  • 若其右子树存在,则其右子树中每个节点的值都不小于该节点值。

二叉搜索树在极端情况下会变成线性结构,查找效率会退化的和链表一样o(n).

table数组扩容

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
/*  会取大于或等于这个数的 且最近的2次幂作为 table 数组的初始容量
解释:位或( | )
int n = cap - 1; 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。
*/

用可变类当 HashMap 的 key 有什么问题?

hashcode 可能发生改变,导致 put 进去的值,无法 get 到元素。

为什么hashmap的初始长度是16

为了方便通过hash算法计算key值对应的数组下标。

**Hashmap比较基础的相关知识点就是这些了,后续再补充Currenth