当前位置： 首页>后端>正文

Java基础-数据结构HashMap

后端2024-04-21 23:12:54

收录面试高频题汇总，面试复习 or 查漏补缺

本文讲解Java面试必问的数据结构Map以及其JDK1.7和JDK1.8的源码分析

什么是HashMap？

JDK1.7和JDK1.8的HashMap区别？

什么是CurrentHashMap？

HashMap

HashMap是我们最常用的数据结构之一，现在以JDK1.8的版本来看看面试考察的点有哪些。

先了解一些HashMap的初始变量

负载因子：0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

初始容量：16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

扩容阈值：DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR

数据结构

数组+链表/红黑树

Java基础-数据结构HashMap,第1张
数组+链表/红黑树

数组中存储的是链表的node节点，当一个数组的位置要存多个node节点时，会形成链表；当链表的长度大于8的时候，链表会转为红黑树来存储。

数据插入的过程

HashMap常用插入数据的方法是put(K key, V value)，其插入的过程如下

  1. 判断数组tab是否为空，如果为空则初始化数组tab；
  2. 如果数组不为空，计算key的hash值，通过(n-1) & hash计算得出key应该存放到数组下标索引index的位置；
  3. 判断当前数组下标index的位置是否有值，如果没有值则构造一个新的node节点存到当前index位置；
  4. 如果判断有值，说明hash值发生冲突了，并且判断key的值与发生冲突节点的key的值是否相等，如果相等就替换原来node；
  5. 如果判断key值不相等，判断当前节点是不是树节点TreeNode，如果是树节点则插入到红黑树中；
  6. 如果不是树节点，则遍历链表，创建节点node插入到链表中；
  7. 如果判断链表的长度大于8并且数组大小大于64，则链表转为红黑树treeifyBin；
  8. 修改计数modCount++、++size；
  9. 插入完成后判断size是否大于阈值threshold，如果大于则开始扩容resize为原来容量的2倍。

源码分析

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
   // 1.判断数组是否为空，如果为空则初始化数组；
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;  
   // 2.如果数组不为空，计算key的hash值，通过(n-1) & hash计算得出key应该存放到数组下标索引index的位置；
    if ((p = tab[i = (n - 1) & hash]) == null)
   // 3.判断当前数组下标index的位置是否有值，如果没有值则构造一个新的node节点存到当前index位置；   
        tab[i] = newNode(hash, key, value, null); 
    else {
        Node<K,V> e; K k;
   // 4.否则说明有值，说明hash值发生冲突了，并且判断key的值与发生冲突节点的key的值是否相等,如果相等就替换原来node；  
        if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
            e = p; 
   // 5.如果判断key值不相等，判断当前节点是不是树节点TreeNode，如果是树节点则插入到红黑树中；   
        else if (p instanceof TreeNode) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
   // 6.如果不是树节点，则遍历链表，创建节点node插入到链表中；
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                  // 7.如果判断链表的长度大于8，则链表转为红黑树；
                    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;
        }
    }
  // 8.修改计数；
    ++modCount;
  // 9.插入完成后判断size是否大于阈值threshold，如果大于则开始扩容resize为原来容量的2倍。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

注：数据获取的方法get(Object key)的逻辑也是类似的步骤，只不过一个是写，一个是读，自己脑海可以简单过下。

为什么容量始终是2的n次方

在HashMap的构造方法中，无论我们传多大的容量进去，HashMap的tableSizeFor方法总会帮我们把容量调整为2的n次方。

tableSizeFor方法如下：

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;
}

通过cap-1数值的二进制最高位的1不断地向右移，把最高位1的后面全部二进制位换成1，最后再加一，做法是或运算然后在无符号右移，假设cap为12，计算如下

  1. cap=12，其二进制是1100；
  2. 通过上面的运算把二进制最高的1右移并且做或运算，得到1111，即十进制数15；
  3. 最后15+1=16，即为2的n次方。

我们知道2^n - 1的数在二进制上最高的位1后面全是1，假设容量不是2的n次方，意味着二进制位上就不全是1，就有0情况，那么在做位运算的时候就导致有部分的数组位置始终是没有数据的，这也就是没有达到分布均匀松散的效果。

正常的做法，假设容量为16，16-1=15，哈希计算如下：

  11010011 10011101   // key的哈希值假设
& 00000000 00001111   // 15
--------------------
  00000000 00001101   // 保留低位用作访问数组的index

不是2的n次方做法，假设容量为12，哈希计算如下：

  11010011 10011101   // key的哈希值假设
& 00000000 00001100   // 12
--------------------
  00000000 00001100   // 保留低位用作访问数组的index

可以看出，12的二进制位最后2位始终是0，那么它与任何数&操作后都是0，意味着数组位置index的数的二进制上只要最后2位有1的都不可能映射到，也就是不会存储到数据。

为什么初始化容量是16

还未看到官方的解释，初始化容量这个值不能太小避免扩容，也不能太大，所以不是4，8，32，而取值16只是经验值

为什么负载因子是0.75

提高空间利用率和减少查询成本的折中，主要是泊松分布，0.75的话碰撞最小。

如果负载因子是0.5，那么Map容量达到一半就开始扩容，虽然提高了时间查询效率，但是空间利用率低；

如果负载因子是1，那么Map在容量满时才扩容，会使哈希碰撞较为严重，虽然空间利用率高，但是查询成本过高

hash函数如何设计的

这里采用了扰动函数，从源码可以看出，key的hash计算是通过key的hashcode的低16位和高16位进行异或运算得出的

static final int hash(Object key) {
    int h;
    return (key == null) 0 : (h = key.hashCode()) ^ (h >>> 16); // 扰动
}

为什么要这样高位和低位异或呢？

假设不用高位低位异或，将key的hashcode与容量n-1进行位运算得出数组位置index，如果有多个不同hashcode，二进制低16位是相同，只是高16位不相同，那么这样的多个hashcode就会计算出相同的数组位置index，导致严重的哈希冲突。扰动函数就是通过高位与低位进行位运算，混合了hashcode的二进制位，这样碰到诸如上述说的hashcode的时候就不会发生严重的哈希冲突了。

链表为什么是大于8时转红黑树，红黑树为什么小于6时转链表

我们知道当链表节点数量大于8并且数组大小大于64的时候会转为红黑树，转红黑树是为了降低链表的查询复杂度，O(n) 降为O(logn)

为什么链表节点阈值数量是8呢？源码中给了解释，就是统计学，如下

* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006
* more: less than 1 in ten million

即扩容阈值为0.75，当哈希发生冲突的次数为超过8的概率小于十万分之一。

那为什么数组大小要大于64呢？

当哈希发生严重冲突导致链表到达8个节点时候，进行数组扩容比转为红黑树成本更低且效果更好。

我们知道当红黑树节点小于6的时候会转为链表，why？

如果红黑树的节点不断减少，继续使用红黑树显得成本较大，那么这时候就需要转为链表。假设红黑树节点减少为8了，需要转为链表，但是这时候又有节点插入，反复如此，一个可能就是红黑树和链表之间来回在不断转换，为了解决这个问题，可以将红黑树的节点减少到6个后，再转为链表。

是否线程安全

HashMap不是线程安全的。

如果想要线程安全的HashMap有其他办法：

  • ConcurrentHashMap（优先考虑）
  • Collections.synchronizedMap
  • Hashtable

HashMap在JDK1.7和8的区别

数据结构

JDK1.7：数组+链表

JDK1.8：数组+链表/红黑树

链表插入方式

JDK1.7：头插法


Java基础-数据结构HashMap,第2张
头插法

JDK1.8：尾插法

Java基础-数据结构HashMap,第3张
尾插法

为什么JDK1.8要使用尾插法替换头插法？

因为JDK1.7的头插法有缺陷，在并发情况下会发生死循环。

Java基础-数据结构HashMap,第4张
缺陷

当遇到多线程扩容的时候使用头插法会导致死循环，看下代码和图

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key 0 : hash(e.key); 
            }
            int i = indexFor(e.hash, newCapacity);      
            e.next = newTable[i]; // 线程1执行到这里调度挂起
            newTable[i] = e;            
            e = next;
        }
    }
}
Java基础-数据结构HashMap,第5张
死循环bug

多线程情况下可能出现链表环如图

  • 正常情况：查询某个不存在的值，索引到数组A位置，遍历链表到尾部，即节点的next为null时，链表遍历结束，最后返回
  • 死循环：查询某个不存在的值，索引到数组A位置，遍历链表，链表中没有next为null的节点，会不停地遍历导致死循环。
扩容计算

JDK1.7：重新哈希计算。当需要扩容的时候，申请新数组，然后将旧数组上的每个节点重新计算key的索引值定位到新数组位置。

JDK1.8：位运算。我们都知道HashMap扩容的时候，数组会扩容为原来的2倍。扩容后重新计算key的规则又是如何变化的呢？还记得哈希计算的方法吗？公式很简单hash = hashcode & (n - 1)。细细观察可以知道，其实key的哈希值没有变，变的是容量n，而扩容n只是变化为原来的2倍，扩容前的n-1比扩容后的n-1在二进制位上高位多了个1，所以我们要想知道计算的索引有没有变化，只要知道hashcode与对应扩容后容量n的最高位多出来的1做位运算是否有变化即可。如下

扩容前容量为16，假设hashcode=51
  0011 0011  // 51的二进制
& 0000 1111  // n-1=15
------------
  0000 0011  // 数组的索引值
  
扩容后容量为32，hashcode不变
  0011 0011  // 51的二进制
& 0001 1111  // n-1=31，二进制比前者多一位1，这是影响索引结果的关键
------------
  0001 0011  // 数组的索引值

因此，在做扩容，也就是把旧数组上的节点迁移到新数组上时，如果hashcode值对应的二进制位是0，那么它的数组索引值不变；如果hashcode值对应的二进制位是1，那么它的数组新索引值=原索引+原数组的容量。

扩容判断

JDK1.7：先判断是否需要扩容再插入，扩容后再插入；

JDK1.8：先插入再判断是否需要扩容，先插入后扩容。

<br />

扩容条件

JDK1.7：节点数量大于阈值（即容量*负载因子），并且发生哈希冲突，就扩容。

JDK1.8：节点数量大于阈值（即容量*负载因子），就扩容。

总结
不同点 JDK1.7 JDK1.8
数据结构 数组+链表 数组+链表/红黑树
链表插入方式 头插法（死循环） 尾插法
扩容计算 重新哈希计算 位运算
扩容判断 先扩容再插入节点 先插入节点再扩容
扩容条件 节点大于阈值 & 发生哈希冲突 节点大于阈值

LinkedHashMap

LinkedHashMap实现的是一个有序的Map，它是在HashMap的基础上实现的，内部维护着一个单链表，也就是LinkedHashMap内部的Entry是继承HashMap的，并且在它的基础上额外增加了before和after指针，用于标识节点的顺序，内部实现的顺序规则有按插入排序或按访问排序。

TreeMap

TreeMap，有序的Map，底层实现是红黑树；

默认情况下是按key的自然顺序排序，提供对外扩展的接口是Comprator，通过实现这个接口可以对key进行自定义排序规则。

WeakHashMap

非线程安全；

key是弱引用，gc时会回收entry

IdentityHashMap

非线程安全；

哈希冲突时，底层使用==等于符号判断是不是同个key（比如key1==key2），所以可以存相同key值不同对象的key-value；

key和value是紧挨着存在数组上的。

Hashtable

Hashtable是遗留类，数据结构由数组+链表组成，与HashMap类似，但是它是线程安全类；

初始容量是11，是质数，质数在做哈希运算的时候可以有效避免哈希冲突，但是扩容后不不一定保证了，扩容容量是原来的2n+1倍；

Hashtable的的线程安全是通过synchronized实现的，就是在get和put的方法都使用synchronized修饰。

ConcurrentHashMap

ConcurrentHashMap可以理解为基于HashMap实现的线程安全的Map，使用的数据结构同样是数组+链表/红黑树，不同的是线程安全的部分，实现并发编程有参考价值。

数据结构

ConcurrentHashMap是在JDK1.7和JDK1.8版本数据结构方面实现线程安全有所有不同。

JDK1.7实现中有一个Segment内部类，继承ReentrantLock，又称为分段锁，是实现线程安全主要手段；ConcurrentHashMap内部定义了一个Segment数组，是一个固定数组，初始默认容量为16，且不支持扩容。

final Segment<K,V>[] segments;

static final class Segment<K,V> extends ReentrantLock implements Serializable {
  
        transient volatile HashEntry<K,V>[] table;
    ...
}

Segment中索引位置保存的是内部实现类HashEntry数组，HashEntry类中定义有next指针，用于形成链表或红黑树的结构。

transient volatile HashEntry<K,V>[] table;
...
static final class HashEntry<K,V> {
    final int hash;
    final K key;
    volatile V value;
    volatile HashEntry<K,V> next;

    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
  ...
}

如图

<img src="https://cdn.jsdelivr.net/gh/huangwenkan9/img@main/img/截屏2022-04-10 11.44.47.png" />

JDK1.8实现中数据结构基本与HashMap相同

transient volatile Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    
    ...
}
加锁

在JDK1.7加锁实现是在Segment上，也就是当操作每个Segment的的时候都需要加ReentrantLock锁，实现线程安全；

在JDK1.8加锁实现是在数组索引上存储的第一个节点，通过synchronized加锁实现线程安全，因为只有发生哈希碰撞才有可能多线程并发操作同个节点，且必须经过第一个节点。

扩容

在JDK1.7，Segment是不支持扩容的，而扩容的是HashEntry，与HashMap类似，都是开辟新的数组，把旧数组下的节点进行打包迁移到新数组；

在JDK1.8实现上考虑了多线程的情况，当多线程操作Map的时候，如果都发现Map正在扩容，多个线程会申请属于自己的数组分片并且加锁帮忙完成扩容操作。多线程是创建新的节点并迁移到新数组上，因此当在Map在扩容的时候，通过get操作会从旧的数组拿到数据。

元素个数计数原理

我们知道Map在加入节点的时候，会对集合数量计数，接下来看看多线程情况下JDK1.7和JDK1.8实现的区别

在JDK1.7，计数是先不加锁多次计算size的值，对比前后两次结果是否一致，一致说明没有元素加入，计算结果是对的；如果一直失败，它会给每个segment加锁计算，然后计算返回。

在JDK1.8，计数有两部分相加组成，分别是baseCount和counterCell，涉及变量有baseCount、counterCells[]两个辅助变量和一个counterCell辅助内部类。

// 优先cas累加在这个baseCount变量，如果并发比较大，cas失败，则累加到CounterCell
private transient volatile long baseCount; 

// CounterCell在数组中有多个，只要计数要其中一个即可
private transient volatile CounterCell[] counterCells;

累加计数：在put方法的时候有个addCount计数方法。它先对baseCount进行cas操作，如果失败，那么就使用counterCells[]数组，取数组其中一个元素进行cas加数，如果也失败了，那么就调用fullAddCount方法，这个方法就会一直死循环操作直到成功（这里面会不断cas计数baseCount或counterCells，直到成功）

获取计数：JDK推荐使用mappingCount()方法取size，返回long类型，而size最大返回int最大值。不论是size还是mappingCount都是基于sumCount方法实现的。为了解决伪共享问题，counterCells是@sum.misc.Contented注解。sumCount方法就是遍历counterCells[]取到每个元素（每个元素就是counterCell辅助内部类）的value加到baseCount，最后返回baseCount的值。

ConcurrentSkipListMap

ConcurrentSkipListMap，优势是能支持范围查找（跳表），又能支持常数复杂度获取元素权重（哈希表），也是线程安全类。

工作原理：CAS+ConcurrentHashMap

接下来我们来了解一下跳表，数据结构正如其名，如图

Java基础-数据结构HashMap,第6张
跳表

最下面一层正如我们熟悉的单链表，然后在这个单链表的基础上再建立一层链表，上层的链表需要与下层的链表关联起来。当节点数量越来越多，层级就越来越高。这种就是非常典型的空间换时间的做法。当我们需要查询数据的时候，首先从最上层的链表找，如果找到数据的对应区间，那么就下沉到下一级的链表，以此类推，直到找到对应节点；相比一开始遍历最底层的最长链表效率高些。

其他

还有一些其他类似的数据结构，原理差不多

  • HashSet

  • CopyOnWriteArraySet

  • ConcurrentSkipListSet

结尾

本文收录至我的《面试高频题及答案汇总》系列。

你努力走过的路，每一步都算数。


https://www.xamrdz.com/backend/3se1925687.html

相关文章：