深入解析单向链表、双向链表及HashMap数据结构的时间复杂度与实现原理
询问
添加删除
单向链表
头部 O(1)，其他 O(n)
头部 O(1)，其他 O(n)
双向链表
头尾 O(1)，其他 O(n)，给定节点 O(1)
头尾 O(1)，其他 O(n)，给定节点 O(1)
2.HashMap相关面试题
HashMap中最重要的数据结构是哈希表，其中用到了红黑树和链表。
2.1 红黑树和哈希表 2.1.1 红黑树查找、添加、删除的时间复杂度为O(n)。
2.1.2 哈希表
（哈希表、哈希函数、哈希碰撞、拉链法的概念）
1）哈希表（Hash Table）：又称散列表/Hash table，是一种根据键（Key）直接访问内存存储位置的值（Value）的数据结构。它是由数组演变而来并使用数组。支持根据下标随机访问数据的功能。
假设有100人参加马拉松比赛，不使用1到100的自然数来给跑步者编号。编号有一定的规则，如：2023ZHBJ001，其中2023代表年份，ZH代表中国，BJ代表北京，001代表原始编号。此时，数字2023ZHBJ001不能直接用作数组的下标。这个时候应该如何实施呢？
2）哈希冲突：也叫散列冲突、散列碰撞，是指多个key映射到同一个数组下标位置。
3）哈希冲突——链表法（拉链）：在哈希表中，数组的每个下标位置都可以称为一个桶（bucket）或槽（slot），每个桶（槽）对应一个链表。我们将所有具有相同哈希值的元素放入同一个槽对应的链表中。时间复杂度如下
2.2 HashMap源码分析（底层实现）
我们主要从以下几个方面来分析源码：成员变量、构造函数、关键方法。
2.2.1 HashMap成员变量
代码语言：java
复制
//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数量，该数组最大值为2^30。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子。如果构造的时候不传则为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一个位置里存放的节点转化成树的阈值，也就是8，比如数组里有一个node，这个node链表的长度达到该值才会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当一个反树化的阈值，当这个node长度减少到该值就会从树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//满足节点变成树的另一个条件，就是存放node的数组长度要达到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具体存放数据的数组！！！
transient Node[] table; //见下
//entrySet，一个存放k-v缓冲区
transient Set> entrySet;
//size是指hashMap中存放了多少个键值对
transient int size;
//对map的修改次数
transient int modCount;
//The next size value at which to resize (capacity * load factor).
int threshold;
//加载因子
final float loadFactor; 代码语言：java
复制
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
} 注意HashMap中瞬态的Node[]表。该表是实际存储数据的容器。容器是由一个又一个节点组成的，节点有三种实现方式，因此hashMap中存储的节点可以是Node或者TreeNode的形式。 。可见HashMap是基于数组、链表或者树来实现的。
【HashMap的定义是哈希表，是一种支持快速查找元素的数据结构，所以后面必然要用到数组的随机访问特性。因此，HashMap的一维结构是一个数组，数组元素是一个包含Key、Value和hashcode的Entry节点。当我们需要访问集合的元素时，实际上是先通过key计算hashcode，然后将hashCode的余数取到数组长度得到数组下标，最后利用下标找到对应的Value中大批]
DEFAULT_INITIAL_CAPACITY 默认初始容量
DEFAULT_LOAD_FACTOR默认负载系数
扩容阈值==阵列容量*负载系数
2.2.2 HashMap构造函数
代码语言：java
复制
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//当容量大于2^31就取最大值1<<31;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//当前数组table的大小，一定是2的幂次方
// tableSizeFor保证了数组一定是2的幂次方，是大于initialCapacity最接近的值。
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}HashMap是延迟加载的，在创建对象时不会初始化数组；在无参数构造函数中，默认加载因子设置为 0.75。
构造函数重载总共有四个，主要初始化三个参数：
最常用的一种是无参数构造。在该构造方法中，仅将荷载系数设置为默认值。另外两个参数将在 resize 方法中初始化。到这里就知道这个结论了。它将在下面的源代码中。分析;另一种具有两个参数的构造方法初始化初始容量和阈值。阈值的初始化方法是tableSizeFor(int cap)。看一下源码：
代码语言：java
复制
//找到大于或等于 cap 的最小2的幂
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;
}tableSizeFor()方法确保数组大小必须是2的幂。它是如何实现的？ ——这个方法将一个二进制数的第一个1之后的所有数字都变成1，然后加1，这样二进制数一定是100的形式……这里的实现在实现中也采用了类似的方法ArrayDeque 来确保数组长度必须是 2 的幂。
如果你不明白无符号右移运算符，可以看一下。下面以10为例进行分析：
另外，需要注意的是，第一步int n = cap - 1；这个操作，执行这个操作的主要原因是为了防止当cap已经是2的n次方时操作后得到的结果。结果是上限的两倍。例如n为l6，经过一系列运算后，结果为0001 1111。此时，执行完最后一步n+1后，将返回32。如果你有兴趣，可以自己尝试一下。
2.2.3 HashMap key 方法 2.2.3.1 put 方法
hashMap源码中，put方法的逻辑是最复杂的。接下来我们看一下源码：
代码语言：java
复制
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//如果table尚未初始化，则此处进行初始化数组，并赋值初始容量，重新计算阈值
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//通过hash找到下标，如果hash值指定的位置数据为空，则直接将数据存放进去。这儿p赋值成了table该位置的node值
tab[i] = newNode(hash, key, value, null);
else {
//如果通过hash找到的位置有数据，发生碰撞
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果需要插入的key和当前hash值指定下标的key一样，先将p赋值给e
e = p;
else if (p instanceof TreeNode)
//如果此时桶中数据类型为 treeNode，使用红黑树进行插入，调用putTreeVal方法
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
//如果此时桶中数据类型为链表，遍历
// 进行循环。注意e = p.next这个一直将下一节点赋值给e，直到尾部，注意开头是++binCount
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//如果链表中没有最新插入的节点，将新放入的数据放到链表的末尾
p.next = newNode(hash, key, value, null);
//如果链表过长，达到树化阈值，将链表转化成红黑树，树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果链表中有新插入的节点位置数据不为空，则此时e 赋值为节点的值，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//经过上面的循环后，如果e不为空，则说明上面插入的值已经存在于当前的hashMap中，那么更新指定位置的键值对
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果此时hashMap size大于阈值，则进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 从代码来看，put方法分为三种情况：
首先分析表未初始化时的情况：
代码语言：java
复制
n = (tab = resize()).length; //table尚未初始化的时候，会调用resize()方法代码语言：java
复制
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//1.table已经初始化，且容量 > 0
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
//如果旧的容量已近达到最大值，则不再扩容，阈值直接设置为最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果旧的容量不小于默认的初始容量，则进行扩容，容量扩张为原来的二倍
newThr = oldThr << 1; // double threshold
}
//2.阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//3.threshold 和 table 皆未初始化情况，此处即为首次进行初始化
//也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题
else { // zero initial threshold signifies using defaults
//如果阈值为零，表示使用默认的初始化值。这种情况在调用无参构造的时候会出现，此时使用默认的容量和阈值
newCap = DEFAULT_INITIAL_CAPACITY;
//此处阈值即为 threshold=initialCapacity*loadFactor
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// newThr 为 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[] newTab = (Node[])new Node[newCap];
table = newTab;
//如果之前的数组桶里面已经存在数据，由于table容量发生变化，hash值也会发生变化，需要重新计算下标
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
//如果指定下标下有数据
if ((e = oldTab[j]) != null) {
//1）将指定下标数据置空
oldTab[j] = null;
//2）指定下标只有一个数据
if (e.next == null)
//直接将数据存放到新计算的hash值下标下
newTab[e.hash & (newCap - 1)] = e;
//3）如果是TreeNode数据结构
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
//4）对于链表，数据结构
else { // preserve order
//如果是链表，重新计算hash值，根据新的下标重新分组
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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;
} resize方法的逻辑比较复杂，需要静下心来一步步分析，但总的来说，分为以下几个步骤：
2.2.3.2 get方法、搜索
put方法分析完成后，剩下的就很简单了。我们先看一下源码：
代码语言：java
复制
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//1）根据hash算法找到对应位置的第一个数据，如果是指定的key，则直接返回。
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//如果该节点为红黑树，则通过树进行查找
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
//如果该节点是链表，则遍历查找到数据。当链表后续为null 退出循环
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
} 与put相比，get方法的逻辑要简单得多：
根据哈希值查找指定位置的数据。验证指定位置第一个节点的数据是否为key。如果有，则直接返回第一个节点。否则继续寻找第二个节点。如果数据是TreeNode（红黑树结构），则直接通过红黑树查找节点数据并返回。如果是链表结构，则循环遍历所有节点并返回数据。如果没有找到符合要求的节点，则返回null。
在这个方法中，有两点需要注意：hash（key）和hash的取模运算（n - 1）&hash。
哈希（键）源代码
代码语言：java
复制
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这段代码称为扰动函数，也就是hashMap中的哈希操作。主要分为以下几个步骤：
模运算 (n - 1) 和哈希
在hashMap代码中，你会在很多地方看到类似的代码：
代码语言：java
复制
first = tab[(n - 1) & hash])在哈希算法中，为了使元素的分布更加均匀，很多会使用取模运算。在hashMap中，hash%n不用于执行取模运算。相反，使用 (n - 1) & hash 来代替。原因是，在 hashMap 计算机中，& 的效率远高于 %;需要注意的是，只有当容量为2的n次方时，(n - 1) & hash才能等价于hash%n，这也是hashMap初始化初始容量时，无论传入什么值，会通过tableSizeFor(int cap)方法转换成2的n次方。这个巧妙的设计着实让人惊叹；至于为什么只有2的n次方才能进行求模运算，这里不再详细介绍。有兴趣的话可以看看大佬写的文章：
2.2.3.3remove方法，删除
了解完get方法后，我们最后看一下remove方法：
代码语言：java
复制
public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
//根据key和key的hash值，查找到对应的元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果查找到了元素node，移除即可
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是TreeNode，通过树进行移除
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
//如果是第一个节点，移除第一个节点，将index下标的位置指向第二个节点
else if (node == p)
tab[index] = node.next;
else
//如果不是链表的第一个节点，则移除该节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
} 从源码中可以看出，通过key查找需要移除的元素的操作过程与get方法几乎相同。最后找到key对应的节点后，根据节点的位置和类型完成相应的移除操作。这个过程非常简单。
2.3 说说HashMap的实现原理
HashMap数据结构：底层使用哈希表数据结构，即数组和链表或红黑树。 jdk1.7采用数组+链表，jdk1.8当链表长度大于阈值（默认为8）且数组长度达到64时会转换为红黑树
初始容量：HashMap的初始容量为0，这是一种懒加载机制。在第一次 put 操作之前，数组大小不会被初始化。默认大小为 16。
扩展逻辑：
HashMap使用拉链方式来解决哈希冲突。扩容不是必须的，但是如果不扩容，拉链的长度会越来越长，导致哈希表的时间复杂度趋于O(n)而不是O(1)。
当元素数量超过阈值（capacity * loadFactor）时，就会触发HashMap扩容。集合的一维数组会加倍，然后重新计算每个元素的位置。
获取时，直接找到哈希值对应的下标，然后进一步判断key是否相同找到对应的值。
注意：链表长度大于8，数组长度大于64。转换为红黑树
面试官问：HashMap的jdk1.7和jdk1.8有什么区别？
2.4 HashMap的jdk1.7和jdk1.8有什么区别？
2.5 HashMap的put方法的具体过程
判断键值对数组表是否为空或者为null，否则执行resize()进行扩容（初始化）。根据键值key计算哈希值，得到数组索引。判断tablei==null。如果条件成立，则直接创建新节点并添加。如果 tablei== null ，如果不成立，则插入成功后，判断实际键值对数量大小是否超过最大容量阈值（数组长度 * 0.75）。如果超过，则扩大容量。 2.6 说说HashMap的扩展机制
2.7 hashMap(n - 1) & hash的寻址算法：获取数组中的索引而不是取模，性能更好。数组长度必须是 2 的 n 次方
2.8 为什么HashMap的数组长度必须是2^n次方？
这是为了尽可能将集合元素均匀分布到数组中的不同位置。
计算索引时效率更高：如果是2的n次方，可以使用按位与运算，而不是取模【HashMap确定元素对应的数组下标时，使用hashCode取数组长度的余数，这实际上是等价的。 hashCode 对数组 length - 1 的 AND 运算（h % length 相当于 h & (lenght -1)，AND 运算效率更高，只有偶数才有效）] 与 2^ 次方对应的长度n - 1 恰好全为 1（1000-1 = 111），所以影响下标的因素都归结为 hashCode 本身，所以可以尽可能均匀的共享。扩展时重新计算索引效率更高：hash & oldCap == 0的元素保留在原来位置，否则新位置=old位置+oldCap2.9 1.7中hashmap的多线程死循环问题
jdk7的数据结构为：数组+链表
数组扩容时，由于链表使用了头插值，因此在数据迁移过程中可能会导致死循环【下面的代码是HashMap的扩容操作，重新定位每个桶的下标，并使用头插值。将元素移动到新数组中。头插入方式会颠倒链表的顺序，这也是形成死循环的关键点】
参考答案：
jdk1.7的hashmap中扩展数组时，由于链表是头插入方式，数据迁移过程中可能会出现死循环。
例如现在有两个线程
线程1：读取当前的hashmap数据。数据中有一个链表。当准备扩展时，线程 2 介入。
线程2：同样读取hashmap，直接扩容。因为是头插入，所以链表的顺序会颠倒过来。例如，原来的顺序是AB，扩展后的顺序是BA，线程两端执行。
线程1：继续执行会出现无限循环。
线程1首先将A移动到新的链表中，然后将B插入到链头中。由于另外一个线程，B的next指向A，所以B->A->B，形成循环。当然，JDK 8调整了扩展算法，不再向链表头部添加元素（但保持扩展前的顺序）。尾部插入方式避免了jdk7中的死循环问题。
2.10 为什么HashMap常用String作为key？
1、不可变类String可以避免修改后无法定位键值对：假设String是一个可变类，当我们在HashMap中构建一个以String为Key的键值对，并修改此时的String时间，那么通过修改后的String就无法匹配刚刚构造的键值对了，因为修改后的hashCode可能会发生变化。不可变类可以避免这个问题。
2. String可以满足Java对hashCode()和equals()的通用约定：如果两个对象有相同的equals()，那么hashCode()将相同。如果 hashCode() 相同，则 equals() 可能不同。这个约定是为了避免两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对，造成冲突。
2.11 HashMap和Hashtable的区别
Hashtable和HashMap都是基于哈希表实现的KV结构的集合。 Hashtable是jdk1.0中引入的线程安全集合类。内部以数组+链表的形式实现。
从功能特点来看
1、Hashtable是线程安全的（HashTable给每个方法添加了synchronized），但HashMap不是
2、HashMap的性能比Hashtable要好，因为Hashtable使用了全局同步锁来保证安全，对性能影响较大。
从内部实施角度
1）Hashtable采用数组加链表，HashMap采用数组+链表+红黑树
2）HashMap初始容量为16，Hashtable初始容量为11
3）HashMap可以使用null作为key； Hashtable 不允许 null 作为键，并且会抛出 NullPointerException。
它们两个key的哈希算法不同：Hashtable直接使用key的hashcode对数组长度取模；而HashMap则对key的hashcode进行二次哈希，避免key分布不均匀影响查询性能。
phper