Java集合框架中Map接口有哪些实现？
作者：徐梦旗，发布于：2023-09-28 20:00，字数：5.6k，预计阅读：23分钟
1. Map接口详解
1.1. Map接口有哪些实现？
1.2. Map接口的实现有什么不同？
| HashMap | LinkedHashMap | Hashtable | TreeMap | |
|---|---|---|---|---|
| 底层数据结构 | 数组，链表和红黑树 | HashMap和双向链表 | 数组和链表 | 红黑树 |
| 初始容量 | 16 | 16 | 11 | / |
| 扩容 | 2倍 | 2倍 | 2倍+1 | / |
| 有序性 | 无序 | 插入顺序和访问顺序 | 无序 | 自然排序和比较器排序 |
| 允许空键 | 是 | 是 | 否 | 自定义比较器排序时可能允许 |
| 允许空值 | 是 | 是 | 否 | 是 |
| 线程安全性 | 不安全（fast-fail） | 不安全（fast-fail） | 安全（内置锁） | 不安全（fast-fail） |
| 添加新的键值对 | O(1) | O(1) | O(1) | O(logn) |
| 根据键查找值 | O(1) | O(1) | O(1) | O(logn) |
2. HashMap详解
2.1. HashMap是如何设计的？
- 继承关系：
HashMap继承了AbstractMap，实现了Map接口。 - 底层数据结构：
HashMap使用了动态数组，并使用了链表和红黑树来解决哈希冲突。 - 存储元素：
HashMap允许存储null键和null值，是无序的。 - 线程安全：
HashMap是线程不安全的，采用fast-fail机制。
2.2. HashMap是如何解决哈希冲突的？
哈希冲突是指两个对象经过哈希函数计算得到的哈希值相同。解决哈希冲突的方法有：
- 开放定址法：冲突时寻找新的空闲的内存地址。
- 再哈希法：再次计算哈希值直到不发生哈希冲突。
- 链表法：利用链表维护哈希冲突的节点。
- 建立公共溢出区：额外开辟一块内存区域来维护冲突的节点。
HashMap使用链表法来解决哈希冲突，哈希值相同的键所对应的节点由链表或红黑树维护。
当链表中的节点越来越多时，查询的时间复杂度会由O(1)退化为O(n)，故当满足最小树化容量为64，树化阈值为8的条件时链表会被树化为红黑树，使用红黑树查询的时间复杂度为O(logn)。而使用红黑树的代价是新增和修改操作需要维护红黑树的结构，效率较低，故当满足链化阈值为6的条件时红黑树会被链化为链表。
2.3. HashMap的哈希函数是如何设计的？
HashMap通过键的哈希码同右移16位后的键的哈希码做异或操作来得到键的哈希值。合适的哈希函数可以减小哈希冲突的概率。
(h = key.hashCode()) ^ (h >>> 16)当n为2的倍数时，(n - 1) & hash同hash % n相等，故HashMap限制容量必须为2的倍数，以通过数组长度减一同键的哈希值做且位运算来得到数组下标。相比于%取模运算，&且位运算有更好的性能。
p = tab[i = (n - 1) & hash]2.4. HashMap为什么需要扩容？
当键值对的个数大于扩容的阈值（即数组长度乘以负载因子，负载因子默认为0.75）时，HashMap会进行扩容，数组长度扩容为原数组长度的2倍。负载因子越大，哈希冲突的几率越小，浪费的内存空间越多；负载因子越小，哈希冲突的几率越大，浪费的内存空间越少。
if (++size > threshold)
resize();如果不进行扩容，当HashMap存储的键值对的个数较多时，由于数组大小固定，会频繁发生哈希冲突，导致大量的键值对存放在链表或红黑树中，使得查询的时间复杂度由O(1)退化为O(n)或O(logn)。
2.5. HashMap为提升性能做了哪些设计？
- 在一定的条件下使用红黑树代替链表，避免查询效率退化为O(n)，提高了查询效率。
- 约定数组长度为2的倍数，使得可以使用位运算代替取模运算，提高了计算效率。
- 扩容为原数组大小的2倍，使得重新计算节点的数组下标时，要么是原始下标的位置，要么是原始下标加原数组长度的位置，提高了扩容效率。
2.6. HashMap是如何添加键值对的？
1. 计算键的哈希值，位运算得到数组下标
通过哈希函数计算键的哈希值，然后通过数组长度减一同哈希值做且位运算得到数组下标。如果数组中该下标不存在节点，则在该下标创建新的键值对节点。
2. 头节点判断
如果数组中该下标存在节点，且该节点对应的哈希值以及对应的键同要添加的键的都相同，则修改该节点对应的值，否者需要判断该节点是树节点还是链表节点。
3. 如果头节点是红黑树，则在红黑树中添加或修改节点
如果是树节点，代表使用的是红黑树解决哈希冲突，则在红黑树中找到对应的位置创建新的键值对节点或修改节点对应的值。
4. 如果头节点是链表，则在链表中添加或修改节点
如果是链表节点，代表使用的是链表解决哈希冲突，则在链表中找到对应的位置创建新的键值对节点或修改节点对应的值。在一定的条件下，链表会被树化为红黑树。
5. 超出阈值进行扩容
如果键值对的个数大于扩容的阈值，即数组长度乘以负载因子，会进行扩容。在一定的条件下，红黑树会被链化为链表。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 通过哈希函数计算键的哈希值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次添加元素需要扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通过数组长度减一同哈希值做且位运算得到数组下标
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 {
// 如果是链表节点，代表使用的是链表解决哈希冲突，则在链表中找到对应的位置创建新的键值对节点或修改节点对应的值
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;
}
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;
// 如果键值对的个数大于扩容的阈值，即数组长度乘以负载因子，会进行扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}2.7. HashMap是如何根据键找到值的？
1. 计算键的哈希值，位运算得到数组下标
通过哈希函数计算键的哈希值，然后通过数组长度减一同哈希值做且位运算得到数组下标。
2. 头节点判断
如果数组中该下标存在节点，且该节点对应的哈希值以及对应的键同要添加的键的都相同，则返回该节点对应的值，否者需要判断该节点是树节点还是链表节点。
3. 如果头节点是红黑树，则在红黑树中查找键对应的值
如果是树节点，则遍历红黑树查找键对应的节点，并返回该节点对应的值，时间复杂度为O(logn)。
3. 如果头节点是链表，则在红黑树中查找键对应的值
如果是链表节点，则遍历链表查找键对应的节点，并返回该节点对应的值，时间复杂度为O(n)。
public V get(Object key) {
Node<K,V> e;
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;
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;
}2.8. HashMap是如何扩容的？
- 计算原数组长度的2倍作为新数组的长度，并创建新数组。
- 遍历数组上的节点，并判断该节点是否有后继节点，如果没有则获取该节点对应的键的哈希值，然后通过新数组长度减一同哈希值做且位运算得到在新数组中的下标，并设置新数组中对应下标的节点。
- 如果该节点是树节点且有后继节点，则遍历红黑树，并获取节点对应的键的哈希值同原数组长度作且运算的结果是否为零为条件，构建两个红黑树；一个红黑树关联新数组中到原始下标的位置，另一个红黑树关联到新数组中原始下标加原数组长度的位置。在一定的条件下，红黑树会被链化为链表。
- 如果该节点是链表节点且有后继节点，则遍历链表，并获取节点对应的键的哈希值同原数组长度作且运算的结果是否为零为条件，构建两个链表；一个链表关联新数组中到原始下标的位置，另一个链表关联到新数组中原始下标加原数组长度的位置。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 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)
// 计算原数组长度的2倍作为新数组的长度
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// (e.hash & oldCap) 为 0，意味着 (2oldCap - 1) & e.hash = (oldCap - 1) & hash，即原始下标的位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// (e.hash & oldCap) 不为 0，意味着 (2oldCap - 1) & e.hash = (oldCap - 1) & hash + oldCap，即原始下标加原数组长度的位置
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;
}3. LinkedHashMap详解
3.1. LinkedHashMap是如何设计的？
- 继承关系：
LinkedHashMap继承了HashMap，实现了Map接口。 - 底层数据结构：除继承了
HashMap外，LinkedHashMap额外添加了双向链表来维护顺序。 - 存储元素：
LinkedHashMap允许存储null键和null值，支持插入顺序和访问顺序。 - 线程安全：
LinkedHashMap是线程不安全的，采用fast-fail机制。
3.2. LinkedHashMap是如何实现有序的？
有序的原理
LinkedHashMap在继承了HashMap的基础上，额外添加了双向链表来维护顺序，支持插入顺序和访问顺序，默认为插入顺序。原理为LinkedHashMap使用了LinkedHashMap#Entry节点来代替了HashMap#Node节点；相比于其父类Node节点，Entry节点额外多了before指针和after指针，即额外维护了一个双向链表。
插入顺序的维护
当创建新节点时，LinkedHashMap会将新节点添加到双向链表的尾部。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// link at the end of list
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
// 将新节点添加到双向链表的尾部
p.before = last;
last.after = p;
}
}访问顺序的维护
当采用访问顺序且访问节点时，LinkHashMap会将被访问的节点移到双向链表的尾部。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 采用访问顺序
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
// 将被访问的节点移到双向链表的尾部
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}3.3. LinkedHashMap和HashMap有什么区别？
LinkedHashMap可以理解为有序的HashMap，支持插入顺序和访问顺序。
4. Hashtable详解
4.1. Hashtable是如何设计的？
- 继承关系：
Hashtable继承了Dictionary，实现了Map接口。 - 底层数据结构：
Hashtable使用了动态数组，并使用了链表来解决哈希冲突。 - 存储元素：
Hashtable不允许存储null键和null值，是无序的。 - 线程安全：
Hashtable是线程安全的，采用synchronized修饰了所有方法。
4.2. Hashtable是如何添加键值对的？
1.计算键的哈希值，取模得到数组下标
通过哈希函数计算键的哈希值，然后通过哈希值同数组长度取模得到数组下标。
2.使用头插法创建新的键值对节点
如果数组中该下标存在节点，且该节点对应的哈希值以及对应的键同要添加的键的都相同，则修改该节点对应的值，否则使用头插法创建新的键值对节点。
3.创建新的键值对节点前，超出阈值进行扩容
如果键值对的个数大于扩容的阈值，即数组长度乘以负载因子，会进行扩容。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
// 通过哈希函数计算键的哈希值，然后通过哈希值同数组长度取模得到数组下标
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 如果数组中该下标存在节点，且该节点对应的哈希值以及对应的键同要添加的键的都相同，则修改该节点对应的值
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 创建新的键值对节点
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
// 如果键值对的个数大于扩容的阈值，即数组长度乘以负载因子，会进行扩容
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
// 使用头插入法创建新的键值对节点
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}4.3. Hastable是如何扩容的？
- 计算原数组长度的2倍加一作为新数组的长度（加一是为了扰动哈希值以减小哈希冲突的概率），并创建新数组。
- 遍历所有节点，依次通过哈希函数计算节点对应的键的哈希值，并同新数组长度取模得到新数组下标。
- 使用头插法在新数组中插入节点。
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 计算原数组长度的2倍加一作为新数组的长度
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
// 创建新数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 遍历数组上的所有节点
for (int i = oldCapacity ; i-- > 0 ;) {
// 遍历链表上的所有节点
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// 通过哈希函数计算节点对应的键的哈希值，并同新数组长度取模得到新数组下标
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 使用头插法在新数组中插入节点
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}4.4. HashMap和Hashtable有什么区别？
Hashtable可以理解为线程安全的HashMap。线程安全的Map的实现推荐使用ConcurrentHashMap，线程不安全的Map的实现推荐使用HashMap。
4.5. Properties是如何设计的？
Properties继承了Hashtable，限制键和值的类型都为字符串。
5. TreeMap详解
5.1. TreeMap是如何设计的？
- 继承关系：
TreeMap继承了AbstractMap，实现了NavigableMap接口。 - 底层数据结构：
TreeMap使用了红黑树。 - 存储元素：
TreeMap允许null值，在使用自然排序的情况下不允许null键，在使用比较器排序的情况下，是否允许null键由比较器决定，是有序的。 - 线程安全：
TreeMap是线程不安全的，采用fast-fail机制。
5.2. TreeMap是如何实现有序的？
TreeMap底层维护了红黑树的数据结构，在新增元素时，会通过TreeMap#compare方法比较元素的顺序，排序方式有两种：自然排序和比较器排序。
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}5.3. HashMap和TreeMap有什么区别？
- 底层数据结构不同：
TreeMap底层使用红黑树，HashMap底层使用数组，并使用链表和红黑树解决哈希冲突。 - 操作的性能不同：
TreeMap新增和查找元素的时间复杂度为O(logn)，HashMap新增和查找元素的时间复杂度为O(1)。 - 适用场景不同：
TreeMap适用于需要键值对需要排序的场景。
6. EnumMap详解
6.1. EnumMap是如何设计的？
- 继承关系：
EnumMap继承了AbstractMap。 - 底层数据结构：
EnumMap使用了固定大小的数组，每个下标代表枚举项所对应的键，每个下标对应的值代表枚举项所对应的值。 - 存储元素：
EnumMap不允许null键，允许null值，且键只能是指定的枚举类型。 - 线程安全：
EnumaMap是线程不安全的。
6.2. HashMap和EnumMap有什么区别？
适用场景不同。EnumMap适用于枚举作为键的场景。
7. 参考文档
