从源码角度看Java Map接口的设计理念
2021-12-221.6k 阅读
Java Map接口概述
在Java的集合框架中，Map接口是一个非常重要的存在，它用于存储键值对（key - value pairs）。与List接口以线性方式存储元素不同，Map接口基于键来存储和检索值，这种数据结构提供了快速查找值的能力。Map接口的设计理念围绕着高效的键值对管理，使得开发者可以通过键快速定位到对应的值。
Java中的Map接口定义了一系列方法，用于操作键值对集合。例如，put(K key, V value)方法用于将指定的键值对存储到Map中；get(Object key)方法用于通过键获取对应的值；containsKey(Object key)方法用于判断Map中是否包含指定的键等。
Map接口的设计目标
- 高效查找：设计
Map接口的主要目标之一是实现高效的查找操作。通过使用合适的数据结构，如哈希表（HashMap）或红黑树（TreeMap），Map能够在较短的时间内根据键找到对应的值。这对于需要频繁查找数据的应用场景，如数据库缓存、配置管理等，至关重要。 - 唯一性：
Map接口通常要求键是唯一的。虽然不同的实现类对键的唯一性保证方式可能不同，但总体原则是一个键只能对应一个值。如果尝试将一个已存在的键与新的值关联，新的值通常会覆盖旧的值。这种唯一性设计有助于确保数据的一致性和准确性。 - 灵活性：
Map接口提供了多种操作方法，以满足不同的需求。开发者可以遍历Map中的所有键值对、获取所有键或所有值的集合，还可以根据键删除对应的键值对。这种灵活性使得Map能够适应各种复杂的业务场景。
Map接口的源码剖析
接口定义
Map接口在Java源码中的定义如下：
public interface Map<K, V> {
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K,? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
boolean equals(Object o);
int hashCode();
}
从这段源码可以看出，Map接口定义了一系列用于管理键值对集合的方法。
方法解析
- 基本属性相关方法
size()方法返回Map中键值对的数量。这个方法的实现对于所有Map实现类来说，都是必须提供的，因为它是获取Map大小的基本方式。isEmpty()方法用于判断Map是否为空，即size()是否为0。通过这个方法，开发者可以快速判断Map中是否包含任何键值对。
- 查找相关方法
containsKey(Object key)方法用于判断Map中是否包含指定的键。不同的Map实现类会根据自身的数据结构来实现这个方法。例如，HashMap通过计算键的哈希值来快速定位键是否存在，而TreeMap则通过比较键的大小来查找。containsValue(Object value)方法用于判断Map中是否包含指定的值。与containsKey方法不同，由于值可能不唯一，查找值的操作相对复杂一些，通常需要遍历整个Map。get(Object key)方法通过指定的键获取对应的值。如果Map中不存在该键，则返回null。在实现上，HashMap会根据键的哈希值和内部的哈希表结构来查找值，TreeMap则通过比较键的大小在红黑树中查找。
- 修改相关方法
put(K key, V value)方法将指定的键值对存储到Map中。如果Map中已经存在该键，则新的值会覆盖旧的值，并返回旧的值；如果不存在，则插入新的键值对并返回null。putAll(Map<? extends K,? extends V> m)方法将指定Map中的所有键值对插入到当前Map中。这个方法方便了将一个Map的内容合并到另一个Map中。remove(Object key)方法根据指定的键删除对应的键值对，并返回被删除的值。如果Map中不存在该键，则返回null。
- 集合操作相关方法
keySet()方法返回一个包含Map中所有键的Set集合。由于键的唯一性，使用Set来存储键是合适的。这个Set集合与Map是关联的，对Set的修改会反映到Map中，反之亦然。values()方法返回一个包含Map中所有值的Collection集合。与keySet不同，值可能重复，所以使用Collection。这个Collection与Map也是关联的。entrySet()方法返回一个包含Map中所有键值对（Map.Entry对象）的Set集合。Map.Entry是一个内部接口，它定义了获取键、值以及设置值的方法。通过遍历entrySet，可以同时获取键和值，这在很多场景下非常有用。
- 辅助方法
clear()方法用于清空Map中的所有键值对，将Map恢复到初始的空状态。equals(Object o)和hashCode()方法用于比较两个Map是否相等以及获取Map的哈希码。在比较两个Map时，通常需要比较它们的键值对是否完全相同。
Map.Entry内部接口
Map.Entry是Map接口中的一个内部接口，它代表了Map中的一个键值对。其源码如下：
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
getKey()方法返回键值对中的键，getValue()方法返回值，setValue(V value)方法用于设置键值对中的值（前提是Map支持值的修改）。equals(Object o)和hashCode()方法用于比较两个Entry对象是否相等以及获取Entry的哈希码。通过Map.Entry，开发者可以方便地操作Map中的单个键值对。
Map接口的常用实现类
HashMap
- 设计理念
HashMap基于哈希表实现，它的设计理念是通过对键进行哈希运算，将键值对分散存储在一个数组中，以实现快速的查找和插入操作。哈希表的核心思想是利用哈希函数将键映射到数组的索引位置，这样在理想情况下，查找、插入和删除操作的时间复杂度都可以达到O(1)。HashMap允许null键和null值，但由于哈希表的特性，null键只能有一个。在处理哈希冲突时，HashMap使用链地址法，即当多个键的哈希值相同时，会将这些键值对存储在一个链表中（在Java 8及以后，当链表长度超过一定阈值时，会将链表转换为红黑树，以提高查找效率）。
- 源码剖析
- 存储结构：
HashMap内部主要使用一个数组table来存储键值对，数组的每个元素是一个Node类型的链表头节点。Node类实现了Map.Entry接口，其定义如下：
- 存储结构：
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> 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;
}
public final boolean equals(Object o) {
if (o == this) {
return true;
}
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) {
return true;
}
}
return false;
}
}
- **哈希函数**：`HashMap`使用`hash(Object key)`方法来计算键的哈希值，该方法会对键的`hashCode`进行一些位运算，以减少哈希冲突的概率：
static final int hash(Object key) {
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- **put方法**：`put(K key, V value)`方法的实现逻辑如下：首先计算键的哈希值，然后根据哈希值确定在数组中的索引位置。如果该位置为空，则直接插入新的`Node`；如果该位置已存在节点，则通过链表（或红黑树）来处理冲突，并根据情况更新值或插入新节点。
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<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) {
treeifyBin(tab, hash);
}
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
break;
}
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) {
resize();
}
afterNodeInsertion(evict);
return null;
}
- **get方法**：`get(Object key)`方法首先计算键的哈希值，然后根据哈希值找到对应的数组位置。如果该位置存在节点，则通过链表（或红黑树）查找对应的键值对：
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 && ((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;
}
TreeMap
- 设计理念
TreeMap基于红黑树实现，它的设计理念是按照键的自然顺序（如果键实现了Comparable接口）或自定义顺序（通过传入Comparator）对键值对进行排序。红黑树是一种自平衡的二叉搜索树，它保证了在插入、删除和查找操作时的时间复杂度为O(log n)，其中n是树中节点的数量。TreeMap不允许null键，因为null键无法参与比较。与HashMap不同，TreeMap的键值对是有序存储的，这使得TreeMap适用于需要对键进行排序的场景，如统计单词出现频率并按字母顺序输出。
- 源码剖析
- 存储结构：
TreeMap内部使用红黑树来存储键值对，红黑树的节点类型为Entry，它实现了Map.Entry接口：
- 存储结构：
static final class Entry<K, V> implements Map.Entry<K, V> {
K key;
V value;
Entry<K, V> left;
Entry<K, V> right;
Entry<K, V> parent;
boolean color = BLACK;
Entry(K key, V value, Entry<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry)) {
return false;
}
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
return valEquals(key, e.getKey()) && valEquals(value, e.getValue());
}
public final int hashCode() {
int keyHash = (key == null? 0 : key.hashCode());
int valueHash = (value == null? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public final String toString() {
return key + "=" + value;
}
}
- **比较器**：`TreeMap`在构造时可以选择传入一个`Comparator`，如果没有传入，则使用键的自然顺序。`compare(Object k1, Object k2)`方法用于比较两个键的大小：
final int compare(Object k1, Object k2) {
return comparator == null? ((Comparable<? super K>) k1).compareTo((K) k2) : comparator.compare((K) k1, (K) k2);
}
- **put方法**：`put(K key, V value)`方法的实现逻辑是在红黑树中插入一个新的节点。首先找到合适的插入位置，然后插入节点并通过旋转和颜色调整来保持红黑树的平衡：
public V put(K key, V value) {
Entry<K, V> t = root;
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K, V> parent;
Comparator<? super K> cpr = comparator;
if (cpr!= null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0) {
t = t.left;
} else if (cmp > 0) {
t = t.right;
} else {
return t.setValue(value);
}
} while (t!= null);
} else {
if (key == null) {
throw new NullPointerException();
}
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0) {
t = t.left;
} else if (cmp > 0) {
t = t.right;
} else {
return t.setValue(value);
}
} while (t!= null);
}
Entry<K, V> e = new Entry<>(key, value, parent);
if (cmp < 0) {
parent.left = e;
} else {
parent.right = e;
}
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
- **get方法**：`get(Object key)`方法在红黑树中查找指定键的节点，并返回对应的值：
public V get(Object key) {
Entry<K, V> p = getEntry(key);
return (p == null)? null : p.value;
}
final Entry<K, V> getEntry(Object key) {
if (comparator!= null) {
return getEntryUsingComparator(key);
}
if (key == null) {
throw new NullPointerException();
}
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K, V> p = root;
while (p!= null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
return null;
}
代码示例
- HashMap示例
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 10);
hashMap.put("banana", 20);
hashMap.put("cherry", 30);
System.out.println("Size of HashMap: " + hashMap.size());
System.out.println("Is HashMap empty? " + hashMap.isEmpty());
System.out.println("Does HashMap contain key 'apple'? " + hashMap.containsKey("apple"));
System.out.println("Does HashMap contain value 20? " + hashMap.containsValue(20));
System.out.println("Value for key 'banana': " + hashMap.get("banana"));
Integer removedValue = hashMap.remove("cherry");
System.out.println("Removed value for key 'cherry': " + removedValue);
System.out.println("Keys in HashMap: " + hashMap.keySet());
System.out.println("Values in HashMap: " + hashMap.values());
System.out.println("Entries in HashMap: " + hashMap.entrySet());
}
}
- TreeMap示例
import java.util.Map;
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("banana", 20);
treeMap.put("apple", 10);
treeMap.put("cherry", 30);
System.out.println("Size of TreeMap: " + treeMap.size());
System.out.println("Is TreeMap empty? " + treeMap.isEmpty());
System.out.println("Does TreeMap contain key 'apple'? " + treeMap.containsKey("apple"));
System.out.println("Does TreeMap contain value 20? " + treeMap.containsValue(20));
System.out.println("Value for key 'banana': " + treeMap.get("banana"));
Integer removedValue = treeMap.remove("cherry");
System.out.println("Removed value for key 'cherry': " + removedValue);
System.out.println("Keys in TreeMap (sorted): " + treeMap.keySet());
System.out.println("Values in TreeMap: " + treeMap.values());
System.out.println("Entries in TreeMap: " + treeMap.entrySet());
}
}
通过上述代码示例，可以直观地看到HashMap和TreeMap在使用上的区别，以及Map接口中各种方法的实际应用。同时，从源码角度对Map接口及其常用实现类的剖析，有助于开发者深入理解Map的设计理念和工作原理，从而在实际开发中能够根据不同的需求选择合适的Map实现类。