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

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

数据结构

数组+链表/红黑树

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

数据插入的过程

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

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

cap=12，其二进制是1100；
通过上面的运算把二进制最高的1右移并且做或运算，得到1111，即十进制数15；
最后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：头插法

头插法

JDK1.8：尾插法

尾插法

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

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

缺陷

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

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

死循环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;
    }
  ...
}

如图

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

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

跳表

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

其他

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

HashSet
CopyOnWriteArraySet
ConcurrentSkipListSet

结尾

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

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

查看全文

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

HashMap

数据结构

数据插入的过程

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

为什么初始化容量是16

为什么负载因子是0.75

hash函数如何设计的

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

是否线程安全

HashMap在JDK1.7和8的区别

数据结构

链表插入方式

扩容计算

扩容判断

扩容条件

总结

LinkedHashMap

TreeMap

WeakHashMap

IdentityHashMap

Hashtable

ConcurrentHashMap

数据结构

加锁

扩容

元素个数计数原理

ConcurrentSkipListMap

其他

结尾

相关文章：