HashMap 是 Java 中常用的哈希表实现，它基于哈希函数来存储键值对（key-value）。在 HashMap 中，获取、遍历键集（keySet）、值集（values）或键值对集（entrySet）是常见的操作。entrySet() 和 keySet() 是两个非常重要的方法，分别用于获取 HashMap 中所有的键值对集合和所有的键集合。
我们来详细分析 entrySet() 和 keySet() 的实现原理。
1. entrySet() 实现原理
entrySet() 方法返回一个 Set<Map.Entry<K, V>>，它是一个包含所有 Map.Entry 的集合。Map.Entry 是 HashMap 中每个元素（键值对）的内部表示。
源码：
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es = entrySet; // entrySet 是一个缓存
if (es == null) {
es = new AbstractSet<Map.Entry<K,V>>() {
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
Object key = e.getKey();
Node<K,V> node = getNode(hash(key), key);
return node != null && node.equals(e);
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
Object key = e.getKey();
Node<K,V> node = getNode(hash(key), key);
if (node != null && node.equals(e)) {
removeNode(hash(key), key, null, false, true);
return true;
}
return false;
}
};
entrySet = es;
}
return es;
}
分析：
- 返回类型：
Set<Map.Entry<K, V>>。Set接口的实现是一个匿名的AbstractSet实现，它重写了iterator()、size()、contains()和remove()方法。 iterator()：返回一个EntryIterator的迭代器，EntryIterator是一个内部迭代器，用于遍历Map.Entry。size()：返回HashMap的大小（元素个数）。contains(Object o)：判断集合中是否包含特定的Map.Entry，通过检查key和value是否匹配来确认。remove(Object o)：如果包含给定的Map.Entry，则通过getNode()找到对应的节点并删除。
Map.Entry 的定义：
public 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 K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue());
}
public int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
}
Node是HashMap中的链表节点，Map.Entry是每个键值对的表示，它实现了Map.Entry接口。
迭代过程：
EntryIterator使用链表结构遍历HashMap中的所有键值对。对于每个桶（bucket），迭代器会遍历链表中的所有节点，直到遍历完所有节点。
2. keySet() 实现原理
keySet() 返回一个 Set<K>，包含所有 HashMap 中的键。其实现类似于 entrySet()，但它只关心键，不关心值。
源码：
public Set<K> keySet() {
Set<K> ks = keySet; // keySet 是一个缓存
if (ks == null) {
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new KeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
if (containsKey(o)) {
removeNode(hash(o), o, null, false, false);
return true;
}
return false;
}
};
keySet = ks;
}
return ks;
}
分析：
- 返回类型：
Set<K>，表示所有键的集合，Set接口的实现是一个匿名的AbstractSet实现，重写了iterator()、size()、contains()和remove()方法。 iterator()：返回一个KeyIterator的迭代器，KeyIterator是一个用于遍历键的内部迭代器。size()：返回HashMap中的键数量。contains(Object o)：检查HashMap是否包含给定的键，调用containsKey()方法。remove(Object o)：移除指定的键，如果存在该键，调用removeNode()删除对应的键值对。
迭代过程：
KeyIterator通过遍历HashMap的所有桶，遍历每个桶的链表来获取所有的键。
3. 总结
entrySet()：返回Map.Entry集合，每个Map.Entry对应HashMap中的一个键值对。通过EntryIterator遍历键值对。entrySet提供了访问键和值的途径，是遍历HashMap的一种高效方式。keySet()：返回Map中所有键的集合。通过KeyIterator遍历所有的键。keySet方法适用于只需要访问键的场景。
这两种方法的实现原理非常类似，都是通过创建 Set 的匿名实现类来支持集合操作，并且通过内部迭代器来遍历 HashMap 中的元素。entrySet() 直接访问键值对，而 keySet() 只关注键。
发表回复