写点什么

Hashmap 的重要变量与高频面试题整理(含答案)

用户头像
Java王路飞
关注
发布于: 2021 年 03 月 27 日
Hashmap的重要变量与高频面试题整理(含答案)

hashmap 重要变量

源码中定义了很多常量,有几个是特别重要的。

  • DEFAULT_INITIAL_CAPACITY : Table 数组的初始化长度: 1 << 4,即 2^4=16(这里可能会问为什么要是 2 的 n 次方?)

  • MAXIMUM_CAPACITY :Table 数组的最大长度: 1<<30, 即 2^30=1073741824

  • DEFAULT_LOAD_FACTOR : 负载因子:默认值为 0.75。 当元素的总个数>当前数组的长度 * 负载因子。数组会进行扩容, 扩容为原来的两倍 (这里可能会问为什么是两倍?这个问题与上述 2 的 n 次方相关联)

  • TREEIFY_THRESHOLD : 链表树化的阈值,默认为 8,表示载一个 node(table)节点下的值的长度大于 8 时就会转变为红黑树

  • UNTREEIFY_THRESHOLD : 红黑树链化阈值,默认为 6,表示载一个 node(table)节点下的值的长度小于 6 时就会转变为链表

  • MIN_TREEIFY_CAPACITY = 64 :最小树化阈值,当 Table 所有元素超过该值,才会进行树化(为了防止前期阶段频繁扩容和树化过程冲突)。

构造器

public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}复制代码
复制代码

空参构造器中对属性 loadFactor(加载因子)进行了赋值操作,初始值为 16。

注意: JDK8 中创建完 HashMap 对象后并没有立即创建长度为 16 的数组。

最显而易见的区别

  • JDK 1.7 : Table 数组+ Entry 链表;

  • JDK1.8 : Table 数组+ Entry 链表 ==> 红黑树;(可能会问为什么要使用红黑树?)

为什么使用链表+数组?

因为为了避免 hash 冲突的问题。由于我们的数组的值是限制死的,我们在对 key 值进行散列取到下标以后,放入到数组中时,难免出现两个 key 值不同,但是却放入到下标相同的格子中,此时我们就可以使用链表来对其进行链式的存放。

我⽤LinkedList 代替数组结构可以吗?

可以

那既然可以使用进行替换处理,为什么又偏偏使用到数组呢?

因为用数组效率最高! 在 HashMap 中, 定位节点的位置是利用元素的 key 的哈希值对数组长度取模得到。 此时,我们已得到节点的位置。显然数组的查找效率比 LinkedList 大(底层是链表结构)。

ArrayList,底层也是数组,查找也快,为啥不⽤ArrayList?

因为采用基本数组结构,扩容机制可以自己定义,HashMap 中数组扩容刚好是 2 的次幂,在做取模运算的效率高。⽽ArrayList 的扩容机制是 1.5 倍扩容。

当两个对象的 hashCode 相同会发生什么?

因为 hashCode 相同,不一定就是相等的(equals 方法比较),所以两个对象所在数组的下标相同,"碰撞"就此发生。又因为 HashMap 使用链表存储对象,这个 Node 会存储到链表中。

你知道 hash 的实现吗?为什么要这样实现?

JDK 1.8 中,是通过 hashCode() 的高 16 位异或低 16 未实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度,功效和质量来考虑的,减少系统的开销,也不会造成因为高位没有参与下标的计算,从而引起的碰撞。

为什么要用异或运算符?

保证了对象的 hashCode 的 32 位值只要有一位发生改变,整个 hash() 返回值就会改变。尽可能的减少碰撞。

为什么是 2 的幂次?与数字 2 的关系

首先为什么长度要是 2 的 n 次方?

这依然关系到 hash 冲突。

简单来说,就是如果是 2 的幂,就能减少 hash 冲突的出现

因为这个 key 存放到数组中哪个位置,,源码中有个按位与来判断,即 hash & (length - 1) ,如果是 2 的幂,那么这个减一的操作会让最后 4 个位数都是 1111,进而保证哈希值能分布早 0-15 之间。如果不是 2 的幂的话,有可能出现某个哈希桶(可以理解为数组中某个位置)是一直为空的,不能完全利用好数组。

注意: hash 值是个 32 位的 int 型

那么如果不是容量不是 2 的幂呢?

源码中有个静态方法 private static int roundUpToPowerOf2 ,这个方法会将容量扩充为 2 的幂。

int rounded = number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (rounded = Integer.highestOneBit(number)) != 0 ?  (Integer.bitCount(number) > 1) ? rounded << 1 : rounded                                        : 1;复制代码
复制代码

流程图如下:

hashmap 为什么是二倍扩容?

容量 n 为 2 的幂次方,n-1 的二进制会全为 1,位运算时可以充分散列,避免不必要的哈希冲突。所以扩容必须 2 倍就是为了维持容量始终为 2 的幂次方。

阶段总结

Hashmap 的结构,1.7 和 1.8 有哪些区别

  1. JDK1.7 用的是头插法,而 JDK1.8 及之后使用的都是尾插法,那么他们为什么要这样做呢?因为 JDK1.7 是用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题。但是在 JDK1.8 之后是因为加入了红黑树使用尾插法,能够避免出现逆序且链表死循环的问题。

  2. 扩容后数据存储位置的计算方式也不一样:hash & (length-1

  3. JDK1.7 的时候使用的是数组+ 单链表的数据结构。但是在 JDK1.8 及之后时,使用的是数组+链表+红黑树的数据结构(当链表的深度达到 8 的时候,也就是默认阈值,就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从 O(n)变成 O(logN)提高了效率)

浓缩版:

  • jdk7 数组+单链表 jdk8 数组+(单链表+红黑树)

  • jdk7 链表头插 jdk8 链表尾插

  • 头插: resize 后 transfer 数据时不需要遍历链表到尾部再插入

  • 头插: 最近 put 的可能等下就被 get,头插遍历到链表头就匹配到了

  • 头插: resize 后链表可能倒序; 并发 resize 可能产生循环链

  • jdk7 先扩容再 put jdk8 先 put 再扩容 (why?有什么区别吗?)

  • jdk7 计算 hash 运算多 jdk8 计算 hash 运算少

  • jdk7 受 rehash 影响 jdk8 调整后是(原位置)or(原位置+旧容量)

为什么在 JDK1.8 中进行对 HashMap 优化的时候,把链表转化为红黑树的阈值是 8,而不是 7 或者不是 20 呢(面试蘑菇街问过)?

  • 如果选择 6 和 8(如果链表小于等于 6 树还原转为链表,大于等于 8 转为树),中间有个差值 7 可以有效防止链表和树频繁转换。假设一下,如果设计成链表个数超过 8 则链表转换成树结构,链表个数小于 8 则树结构转换成链表,如果一个 HashMap 不停的插入、删除元素,链表个数在 8 左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。

  • 还有一点重要的就是由于 treenodes 的大小大约是常规节点的两倍,因此我们仅在容器包含足够的节点以保证使用时才使用它们,当它们变得太小(由于移除或调整大小)时,它们会被转换回普通的 node 节点,容器中节点分布在 hash 桶中的频率遵循泊松分布,桶的长度超过 8 的概率非常非常小。所以作者应该是根据概率统计而选择了 8 作为阀值

哈希表如何解决 Hash 冲突?

总结一些特点

为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

讲讲 HashMap 的 get/put 过程

常见问题:

  • 知道 HashMap 的 put 元素的过程是什么样吗?

  • 知道 get 过程是是什么样吗?

  • 你还知道哪些的 hash 算法?

  • 说一说 String 的 hashcode 的实现

添加方法:put()

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}
复制代码

// 因为有些数据计算出的哈希值差异主要在高位,而 HashMap 里的哈希寻址是忽略容量以上的高位的 // 那么这种处理就可以有效避免类似情况下的哈希碰撞 static final int hash(Object key) { int h; // 如果 key 不为 null,就让 key 的高 16 位和低 16 位取异或 // 和 Java 7 相比,hash 算法确实简单了不少 // 使用异或尽可能的减少碰撞 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

// 放入元素的操作 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // tab 相当于哈希表 Node<K,V>[] tab; Node<K,V> p;

// n保存了桶的个数    // i保存了应放在哪个桶中    int n, i;
// 如果还没初始化哈希表,就调用resize方法进行初始化操作 // resize()方法在后面分析 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;

// 这里的 (n - 1) & hash 相当于 Java 7 中的indexFor()方法,用于确定元素应该放在哪个桶中 // (n - 1) & hash 有以下两个好处:1、放入的位置不会大于桶的个数(n-1全为1) 2、用到了hash值,确定其应放的对应的位置 if ((p = tab[i = (n - 1) & hash]) == null) // 如果桶中没有元素,就将该元素放到对应的桶中 // 把这个元素放到桶中,目前是这个桶里的第一个元素 tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; // 创建和键类型一致的变量 K k;
// 如果该元素已近存在于哈希表中,就覆盖它 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果采用了红黑树结构,就是用红黑树的插入方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 否则,采用链表的扩容方式 else { // binCount用于计算桶中元素的个数 for (int binCount = 0; ; ++binCount) { // 找到插入的位置(链表最后) if ((e = p.next) == null) { // 尾插法插入元素 p.next = newNode(hash, key, value, null); // 如果桶中元素个数大于阈值,就会调用treeifyBin()方法将其结构改为红黑树(但不一定转换成功) if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果遇到了相同的元素,就覆盖它 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } }
if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } }
++modCount;
// 如果size大于阈值,就进行扩容操作 if (++size > threshold) resize();
afterNodeInsertion(evict); return null;复制代码
复制代码

}

复制代码


总结

  1. 对 key 的 hashCode()做 hash 运算,计算 index;

  2. 如果没碰撞直接放到 bucket(哈希桶)里;

  3. 如果碰撞了,以链表的形式存在 buckets 后;

  4. 如果碰撞导致链表过长(大于等于 TREEIFY_THRESHOLD),就把链表转换成红黑树(JDK1.8 中的改动);

  5. 如果节点已经存在就替换 old value(保证 key 的唯一性)

  6. 如果 bucket 满了(超过 load factor*current capacity),就要 resize

同时 对于 Key 和 Value 也要经历以下的步骤

  1. 通过 Key 散列获取到对于的 Table;

  2. 遍历 Table 下的 Node 节点,做更新/添加操作;

  3. 扩容检测;

扩容方法:resize()

HashMap 的扩容实现机制是将老 table 数组中所有的链表取出来,重新对其 Hashcode 做 Hash 散列到新的 Table 中,resize 表示的是对数组进行初始化或 进行 Double 处理。

final Node<K,V>[] resize() {    Node<K,V>[] oldTab = table;    int oldCap = (oldTab == null) ? 0 : oldTab.length;    int oldThr = threshold;    int newCap, newThr = 0;
复制代码


// 原容量大于0(已近执行了put操作以后的扩容)if (oldCap > 0) {    if (oldCap >= MAXIMUM_CAPACITY) {        threshold = Integer.MAX_VALUE;        return oldTab;    }    // 原容量扩大一倍后小于最大容量,那么newCap就为原容量扩大一倍,同时新阈值为老阈值的一倍    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&             oldCap >= DEFAULT_INITIAL_CAPACITY)        newThr = oldThr << 1; // double threshold}// 调用了含参构造方法的扩容// 原容量小于等于0,但是阈值大于0,那么新容量就位原来的阈值(阈值在调用构造函数时就会确定,但容量不会)else if (oldThr > 0) // initial capacity was placed in threshold    newCap = oldThr;
// 调用了无参构造方法的扩容操作else { // zero initial threshold signifies using defaults // 如果连阈值也为0,那就调用的是无参构造方法,就执行初始化操作 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}
// 如果新阈值为0,就初始化它if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);}
// 阈值改为新阈值threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})
// 创建新的表,将旧表中的元素进行重新放入Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; // 为空就直接放入 if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
// 如果是树节点,就调用红黑树的插入方式 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表的插入操作 else { // preserve order // lo 和 hi 分别为两个链表,保存了原来一个桶中元素被拆分后的两个链表 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } }}return newTab;复制代码
复制代码

复制代码

}

获取数据:get()方法

  1. 对 key 的 hashCode()做 hash 运算,计算 index;

  2. 如果在 bucket 里的第一个节点里直接命中,则直接返回;

  3. 如果有冲突,则通过 key.equals(k)去查找对应的 Entry;

  4. 若为树,则在树中通过 key.equals(k)查找,O(logn);

  5. 若为链表,则在链表中通过 key.equals(k)查找,O(n)。

代码如下

public V get(Object key) {    Node<K,V> e;    // 通过key的哈希值和key来进行查找    return (e = getNode(hash(key), key)) == null ? null : e.value;}
复制代码

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

// 哈希表不为空    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {
// 如果第一个元素就是要查找的元素,就返回 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first;
// 如果第一个元素不是,就继续往后找。找到就返回,没至找到就返回null if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null;复制代码
复制代码

}

复制代码


还知道哪些 hash 算法

先说⼀下 hash 算法⼲嘛的,Hash 函数是指把⼀个⼤范围映射到⼀个⼩范围。把⼤范围映射到⼀个⼩范围的⽬的往往是为了 节省空间,使得数据容易保存。

String 中 hashcode 的实现

public int hashCode() {    int h = hash;    if (h == 0 && value.length > 0) {        char val[] = value;
复制代码


for (int i = 0; i < value.length; i++) {        h = 31 * h + val[i];    }    hash = h;}return h;复制代码
复制代码

复制代码

}

String 类中的 hashCode 计算⽅法还是⽐较简单的,就是以 31 为权,每⼀位为字符的 ASCII 值进⾏运算,⽤⾃然溢出来等效 取模。

为什么 hashmap 的在链表元素数量超过 8 时候改为红黑树

  • 知道 jdk1.8 中 hashmap 改了什么吗。

  • 说一下为什么会出现线程的不安全性

  • 为什么在解决 hash 冲突时候,不直接用红黑树,而是先用链表,再用红黑树

知道 jdk1.8 中 hashmap 改了什么吗。

  1. 由数组+链表的结构改为数组+链表+红⿊树。

  2. 优化了⾼位运算的 hash 算法:h^(h>>>16)

  3. 扩容后,元素要么是在原位置,要么是在原位置再移动 2 次幂的位置,且链表顺序不变。 注意: 最后⼀条是重点,因为最后⼀条的变动,hashmap 在 1.8 中,不会在出现死循环问题。

线程不安全问题

HashMap 在 jdk1.7 中 使用 数组加链表的方式,并且在进行链表插入时候使用的是头结点插入的方法。 注 :这里为什么使用 头插法的原因是我们若是在散列以后,判断得到值是一样的,使用头插法,不用每次进行遍历链表的长度。但是这样会有一个缺点,在进行扩容时候,会导致进入新数组时候出现倒序的情况,也会在多线程时候出现线程的不安全性。 但是对于 jdk1.8 而言,还是要进行阈值的判断,判断在什么时候进行红黑树和链表的转换。所以无论什么时候都要进行遍历,于是插入到尾部,防止出现扩容时候还会出现倒序情况。

简而言之:

  1. 在 JDK1.7 中,当并发执行扩容操作时会造成环形链和数据丢失的情况。

  2. 在 JDK1.8 中,在并发执行 put 操作时会发生数据覆盖的情况。

为什么不一开始就使用红黑树,不是效率很高吗?

因为红⿊树需要进行左旋,右旋,变⾊这些操作来保持平衡,而单链表不需要。 当元素小于 8 个档时候,此时做查询操作,链表结构已经能保证查询性能。 当元素大于 8 个的时候,此时需要红黑树来加快查询速度,但是新增节点的效率变慢了。因此,如果一开始就用红黑树结构,元素太少,新增效率又比较慢,无疑这是浪费性能的。

HashMap 的并发问题

  • HashMap 在并发环境下会有什么问题

  • 一般是如何解决的

问题的出现:

(1)多线程扩容,引起的死循环问题

(2)多线程 put 的时候可能导致元素丢失

(3)put 非 null 元素后 get 出来的却是 null

不安全性的解决方案

concurrentHashmap

你一般用什么作为 HashMap 的 key 值

  • key 可以是 null 吗,value 可以是 null 吗

  • 一般用什么作为 key 值

  • 用可变类当 Hashmap 的 Key 会有什么问题

  • 让你实现一个自定义的 class 作为 HashMap 的 Key 该如何实现

key 可以是 null 吗,value 可以是 null 吗

当然都是可以的,但是对于 key 来说只能运行出现一个 key 值为 null,但是可以出现多个 value 值为 null

一般用什么作为 key 值

⼀般⽤Integer、String 这种不可变类当 HashMap 当 key,⽽且 String 最为常⽤。

详见上面的问题:为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

用可变类当 Hashmap 的 Key 会有什么问题

hashcode 可能会发生变化,导致 put 进行的值,无法 get 出来

实现一个自定义的 class 作为 Hashmap 的 key 该如何实现

  • 重写 hashcode 和 equals 方法需要注意什么?

  • 如何设计一个不变的类。

针对问题一,记住下面四个原则即可

(1)两个对象相等,hashcode 一定相等

(2)两个对象不等,hashcode 不一定不等

(3)hashcode 相等,两个对象不一定相等

(4)hashcode 不等,两个对象一定不等

针对问题二,记住如何写一个不可变类

(1)类添加 final 修饰符,保证类不被继承。 如果类可以被继承会破坏类的不可变性机制,只要继承类覆盖父类的方法并且继承类可以改变成员变量值,那么一旦⼦类 以⽗类的形式出现时,不能保证当前类是否可变。

(2)保证所有成员变量必须私有,并且加上 final 修饰 通过这种方式保证成员变量不可改变。但只做到这一步还不够,因为如果是对象成员变量有可能在外部改变其值。所以第 4 点弥补这个不足。

(3)不提供改变成员变量的方法,包括 setter 避免通过其他接⼝改变成员变量的值,破坏不可变特性。

(4)通过构造器初始化所有成员,进行深拷贝(deep copy)

(5) 在 getter 方法中,不要直接返回对象本身,而是克隆对象,并返回对象的拷贝。这种做法也是防⽌对象外泄,防止通过 getter 获得内部可变成员对象后对成员变量直接操作,导致成员变量发生改变

补充一些面试题

能否使用任何类作为 Map 的 key?

可以使用任何类作为 Map 的 key , 然而在使用之前,需要考虑以下几点

  • 如果类重写了 equals() 方法,也应该重写 hashCode()方法。如果一个类没有使用 equals(), 不应该在 hashCode() 中使用它。

  • 类的所有实例需要遵循与 equals() 和 hashCode() 相关的规则。

  • 最好还是使用不可变类

HashMap 为什么不直接使用 hashCode()处理后的哈希值直接作为 table 的下标?

首先 hashcode 方法返回的是 int 整数类型,其范围太大,且存在负数,无法匹配存储位置。二是 hashmap 的容量范围是从 16 开始的,也就是他的初始化默认值

解决

  • HashMap 实现了自己的 hash()方法, 通过两次扰动使得它自己的哈希值高低位自行进行异或运算, 降低哈希碰撞概率,也使得数据分布更平均;

  • 回顾一下 hashmap 长度为 2 的幂次方问题

补充: 为什么是两次扰动

这样就是加大哈希值低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性和均匀性,最终减少 Hash 冲突,两次就够了, 已经达到了高位低位同时参与运算的目的;

HashMap 与 HashTable 有什么区别?

  • 线程安全:HashMap 是非线程安全的, HashTable 是线程安全的。

  • 效率:hashmap 比 hashtable 效率更高(HashTable 内部经过 synchronize 修饰,效率差了点)

  • 对 Null key 和 Null value 的支持:HashMap 中,null 可以作为键,这样的键只有一个,可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null, 直接抛异常.

  • 初始容量大小和每次扩充容量大小的不同:Hashtable 默认的初始大小为 11 , 之后每次扩充, 容量变为原来的 2n+1 。HashMap 默认的初始化大小为 16。之后每次扩充, 容量变为原来的 2 倍。如果指定了容量,Hashtable 会直接使用你给定的大小,而 HashMap 会将其扩充为 2 的幂次方大小。

  • 底层结构:jdk1.8 中 hashmap 会在链表长度大于 8 时将链表转化为红黑树,但是 hashtable 没有这个机制

原文链接:https://juejin.cn/post/6943377094445367333

如果觉得本文对你有帮助,可以关注一下我公众号,回复关键字【面试】即可得到一份 Java 核心知识点整理与一份面试大礼包!另有更多技术干货文章以及相关资料共享,大家一起学习进步!


发布于: 2021 年 03 月 27 日阅读数: 10
用户头像

Java王路飞

关注

需要资料添加小助理vx:17375779923 即可 2021.01.29 加入

Java领域;架构知识;面试心得;互联网行业最新资讯

评论

发布
暂无评论
Hashmap的重要变量与高频面试题整理(含答案)