Map：接口
-
AbstractMap：抽象类
-
HashMap：散列表
- LinkedHashMap：维护插入或访问顺序的散列表
-
TreeMap：维护键值大小顺序
-
-
Hashtable：同步的散列表
Map
public interface Map<K, V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations
V put(K key, V value);
V remove(Object key);
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Views
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();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// Comparison and hashing
boolean equals(Object o);
int hashCode();
// Defaultable methods
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key)) ? v : defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch (IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { /*...*/ }
default V putIfAbsent(K key, V value) { // key 不存在关联的 value 或 关联的 value 为 null 时 put
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) { // 当 map 中存在 key value 键值对时才 remove
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) { /*...*/ }
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) { /*...*/ }
default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { /*...*/ }
default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value : remappingFunction.apply(oldValue, value);
if (newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
// 自从 JDK 9/10 开始加入的一些静态方法
// of() 系列方法 返回一个不可变的 Map 最多 10 个键值对
// 即 of() ... of(K k1, V v1, K k2, V v2, ..., K k10, V v10)
static <K, V> Map<K, V> of() {
return ImmutableCollections.emptyMap();
}
// 返回一个不可变的 map 传入一系列 Entry
static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) { /*...*/ }
// 返回一个不可变的 Entry
static <K, V> Entry<K, V> entry(K k, V v) {
return new KeyValueHolder<>(k, v);
}
// 返回一个不可变的 map 传入一个 Map
@SuppressWarnings({"rawtypes","unchecked"})
static <K, V> Map<K, V> copyOf(Map<? extends K, ? extends V> map) {
if (map instanceof ImmutableCollections.AbstractImmutableMap) {
return (Map<K,V>)map;
} else {
return (Map<K,V>)Map.ofEntries(map.entrySet().toArray(new Entry[0]));
}
}
}
-
Map 接口定义了一系列的查询修改等基本操作，并为很多复杂方法提供了默认实现。
-
Map 内部定义了一个接口 Entry，用于定义键值对，并提供键值对的比较器。
AbstractMap
public abstract class AbstractMap<K,V> implements Map<K,V> {
protected AbstractMap() {
}
// Query Operations
public int size() {
return entrySet().size();
}
public boolean isEmpty() {
return size() == 0;
}
public boolean containsValue(Object value) { /*...*/ } // 实现方式与 get 类似
public boolean containsKey(Object key) { /*...*/ } // 实现方式与 get 类似
public V get(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return e.getValue();
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return e.getValue();
}
}
return null;
}
// Modification Operations
public V put(K key, V value) { // 支持 put 的 Map 覆盖该方法 不支持 put 的 Map 不需要覆盖 直接抛异常
throw new UnsupportedOperationException();
}
public V remove(Object key) { // O(n) 级别的 remove 很多 Map 可以覆盖该方法 提高效率
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}
V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}
// Bulk Operations
public void putAll(Map<? extends K, ? extends V> m) { /*...*/ }
public void clear() {
entrySet().clear();
}
// Views
transient Set<K> keySet;
transient Collection<V> values;
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
// 定义一个匿名内部类
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
// 将各种操作委托给外部
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
keySet = ks;
}
return ks;
}
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
// 与 keySet() 类似 将操作委托给外部
};
values = vals;
}
return vals;
}
public abstract Set<Entry<K,V>> entrySet();
// Comparison and hashing
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Map))
return false;
Map<?,?> m = (Map<?,?>) o;
if (m.size() != size())
return false;
// 比较每一个键值对中 key 和 value 而不是 Entry
try {
for (Entry<K, V> e : entrySet()) {
K key = e.getKey();
V value = e.getValue();
if (value == null) {
if (!(m.get(key) == null && m.containsKey(key)))
return false;
} else {
if (!value.equals(m.get(key)))
return false;
}
}
} catch (ClassCastException unused) {
return false;
} catch (NullPointerException unused) {
return false;
}
return true;
}
public int hashCode() {
int h = 0;
for (Entry<K, V> entry : entrySet())
h += entry.hashCode();
return h;
}
public String toString() { /*...*/ }
protected Object clone() throws CloneNotSupportedException { /*...*/ }
// 提供给 SimpleEntry 和 SimpleImmutableEntry 使用的工具方法
private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}
// Entry 的简单实现
public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = -8499721149061103585L;
private final K key;
private V value;
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleEntry(Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
public K getKey() { return key; }
public V getValue() { return value; }
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
public String toString() { return key + "=" + value; }
}
// 不可变 Entry 的简单实现
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable
{
private static final long serialVersionUID = 7138329143949025153L;
private final K key;
private final V value; // value 是 final 不可变的
// 构造方法 与 SimpleEntry 类似
// get 方法 与 SimpleEntry 一致
public V setValue(V value) {
throw new UnsupportedOperationException();
}
// equals hashCode String 方法 与 SimpleEntry 一致
}
}
-
AbstractMap 提供了几乎所有操作的实现，各种操作都基于 entrySet() 抽象方法，因此子类只需要实现 entrySet() 方法，可修改的 Map 需要提供 put 的实现。
-
AbstractMap 提供了两种简单的 Entry 实现，一种可变的 Entry，一种不可变的 Entry。
HashMap
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
// 链表转红黑树的条件1：链表长度 > 8
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
// 链表转红黑树的条件2：数组长度 >= 64
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
}
/* ---------------- Static utilities -------------- */
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
// 将 hash 值高位扩散散列到低位上 因为通常只有 hash 值的低位决定数组下标
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* ---------------- Fields -------------- */
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
*/
int threshold;
/**
* The load factor for the hash table.
*/
final float loadFactor;
/* ---------------- Public operations -------------- */
/**
* Constructs an empty {@code HashMap} with the specified initial
* capacity and load factor.
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) { /*...*/ }
/**
* Constructs an empty {@code HashMap} with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public int size() { return size; }
public boolean isEmpty() { return size == 0; }
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;
}
public boolean containsKey(Object key) { return getNode(hash(key), key) != null; }
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) // 取 hash 值的低若干位
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
// 此时 binCount 为 7
// 从 0 开始计数 说明除头结点外 还有 8 个结点
// 因此插入后 链表结点数量 > 8 时 转为红黑树
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); // LinkedHashMap 使用
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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)
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;
if ((e.hash & oldCap) == 0) { // 新位置在新数组的前半部分(原位置)
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { // 新位置在新数组的后半部分(偏移oldCap)
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;
}
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) // 数组长度 < 64 只调整数组大小 不会转为红黑树
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null; // 头结点 和 尾结点
do { // 将所有 Node 转为 TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // tree 化
}
}
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
// 与 putVal 类似
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
// 找到待 remove 的结点
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<K,V>)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);
}
}
if (node != null
&& (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 头结点
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); // LinkedHashMap 使用
return node;
}
}
return null;
}
public void clear() { /*...*/ }
// 遍历数组的每一个结点
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (Node<K,V> e : tab) {
for (; e != null; e = e.next) {
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
// 内部类实现
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
final class KeySet extends AbstractSet<K> { /*...*/ }
// 内部类实现
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
final class Values extends AbstractCollection<V> { /*...*/ }
// 内部类实现
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (Node<K,V> e : tab) {
for (; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
/* ------------------------------------------------------------ */
// iterators
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
removeNode(p.hash, p.key, null, false, false);
expectedModCount = modCount;
}
}
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
/* ------------------------------------------------------------ */
// LinkedHashMap support
/*
* The following package-protected methods are designed to be
* overridden by LinkedHashMap, but not by any other subclass.
* Nearly all other internal methods are also package-protected
* but are declared final, so can be used by LinkedHashMap, view
* classes, and HashSet.
*/
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// For conversion from TreeNodes to plain nodes
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
// Create a tree bin node
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
return new TreeNode<>(hash, key, value, next);
}
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
/* ------------------------------------------------------------ */
// Tree bins
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
// LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>
// TreeNode 是一种特化的 Node
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) { /*...*/ }
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
/**
* Forms tree of the nodes linked from this node.
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 遍历链表的每个结点
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
// 找到插入位置
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); // 平衡红黑树
break;
}
}
}
}
moveRootToFront(tab, root); // 确保根节点为头结点
}
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) { // 遍历红黑树 重新组合成链表
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { /*...*/ }
/**
* Removes the given node, that must be present before this call.
* This is messier than typical red-black deletion code because we
* cannot swap the contents of an interior node with a leaf
* successor that is pinned by "next" pointers that are accessible
* independently during traversal. So instead we swap the tree
* linkages. If the current tree appears to have too few nodes,
* the bin is converted back to a plain bin. (The test triggers
* somewhere between 2 and 6 nodes, depending on tree structure).
*/
// 当树结点数量过少时 可能发生转化成链表
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) { /*...*/ }
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 根据数量决定 链表化 还是 重新树化
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
}
}
-
HashMap 底层结构：数组 + 链表 + 红黑树。
链表和红黑树 的选择：
- 红黑树的查询复杂度是对数级的，链表的查询是线性的，但结点个数较少的情况下，链表的查询速度已经很快。
- 红黑树结点的空间占用约为链表结点的 2 倍。
因此，只有当冲突结点足够多的时候，才考虑转化为红黑树。
-
链表转红黑树：
-
插入新结点后，链表结点数量 > 8
-
数组的长度 >= 64
同时满足以上两个条件才能转化为红黑树
-
-
红黑树转链表：红黑树结点数量 <= 6
选择 8 的原因：
在理想情况下，使用随机 hashCode 和 0.75 的负载因子，hash 冲突的结点数量概率基本符合泊松分布，结点数量超过 8 的可能小于千万分之一。因此，出现了红黑树的情况，表明很有可能 hash 方法出现了问题。
TREEIFY 和 UNTREEIFY 门限不等的原因(个人理解)：
如果相等，可能会使得链表和红黑树的转化过于频繁。即结点个数始终在门限附近徘徊，导致数据结构多次转化。
而门限不等，相当于留下了一些缓冲的空间，当结点数量下降到一定程度时，才会将红黑树转化为链表。 -
HashMap put 流程：
-
如果是空数组，调用 resize() 方法，将容量和门限初始化。
-
是否存在 hash 冲突(数组对应位置是否为 null)
- 不存在冲突，直接创建新结点，接 3
- 存在冲突，找到对应插入/修改的位置，3 种情况：
- 头结点 key 值相等
- 否则，遍历红黑树
- 否则，遍历链表；如果是插入新结点，可能会转为红黑树
如果是插入新结点，已经在上述流程中完成，后接 3；
否则，根据 ifAbsent 更新结点，调用 afterNodeAccess() 方法，并返回旧值。 -
修改 modCount
-
size++; 根据情况(结点个数 > 负载因子 * 数组长度)调用 resize
-
调用 afterNodeInsertion() 方法
-
返回空值
即：插入新结点会走1~6完整的流程，更新 value 会在第 2 步完成，然后直接返回。
-
-
HashMap 数组长度永远是 2 的幂，默认初始为 16。
- 方便通过 hash 值计算下标。
- 数组扩容时，再散列后的下标值计算也会方便很多。
// 下标计算
index = (n - 1) & hash; // 通过位运算 只取 hash 值的低若干位
// 再散列下标计算
final Node<K,V>[] resize() {
// ...
// oldCapacity = 0b0...010...0
// newCapacity = 0b0...100...0
if ((e.hash & oldCap) == 0) { // 通过位运算 判断新下标位于新数组的前半部还是后半部
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// ...
}
可见，下标的计算只用到了 hash 值的后若干位。因此，HashMap 将原本 hashCode 的高位映射到低位上，减少哈希冲突。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-
HashMap 内部类 KeySet，Values，EntrySet，分别用于 keySet()，values()，entrySet()。
-
HashMap 内部抽象类 HashIterator，迭代的方式是数组遍历。内部类 KeyIterator，ValueIterator，EntryIterator 继承了该抽象类。
-
HashMap 内部类 Node 实现了 Map.Entry，作为链表的结点。内部类 TreeNode 间接继承了 Node 类，作为红黑树的节点。
LinkedHashMap
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
private static final long serialVersionUID = 3801124242820219131L;
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* The iteration ordering method for this linked hash map: {@code true}
* for access-order, {@code false} for insertion-order.
*/
final boolean accessOrder;
// internal utilities
// 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;
}
}
// apply src's links to dst
private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
// overrides of HashMap hook methods
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
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;
}
}
// 方法覆盖 遍历链表
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
public V getOrDefault(Object key, V defaultValue) { /*...*/ }
/**
* Returns {@code true} if this map should remove its eldest entry.
* This method is invoked by {@code put} and {@code putAll} after
* inserting a new entry into the map. It provides the implementor
* with the opportunity to remove the eldest entry each time a new one
* is added. This is useful if the map represents a cache: it allows
* the map to reduce memory consumption by deleting stale entries.
*/
// LinkedHashMap 适合用于实现缓存等与插入顺序或访问顺序有关的数据结构
// 比如 LRU 算法 可以将该方法覆盖 return size > ? 来实现(并且构造时将 accessOrder 置为 true)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
public Set<K> keySet() { /*...*/ }
final class LinkedKeySet extends AbstractSet<K> { /*...*/ }
public Collection<V> values() { /*...*/ }
final class LinkedValues extends AbstractCollection<V> { /*...*/ }
public Set<Map.Entry<K,V>> entrySet() { /*...*/ }
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { /*...*/ }
// Map overrides
public void forEach(BiConsumer<? super K, ? super V> action) { /*...*/ }
public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { /*...*/ }
// Iterators
abstract class LinkedHashIterator {
LinkedHashMap.Entry<K,V> next;
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
removeNode(p.hash, p.key, null, false, false);
expectedModCount = modCount;
}
}
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
}
-
LinkedHashMap 继承自 HashMap，内部维护了一条链表，代表访问顺序，或者插入顺序。默认为 插入顺序。
-
插入或访问之后，会调用 afterNodeInsertion/afterNodeAccess 方法，来维护链表的顺序。
-
afterNodeInsertion 方法会调用 removeEldestEntry 来判断是否需要移除链表的头节点。
-
removeEldestEntry 方法永远返回 false。但我们可以覆盖该方法来实现定容量的 LinkedHashMap，从而实现缓存等结构。
-
class LRUCache {
LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
cache = new LinkedHashMap<Integer, Integer>(capacity, .75f, true) { // 设置 accessOrder 为 true
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return cache.size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
-
LinkedHashSet 的底层是 LinkedHashMap，但只有 accessOrder 置为 false 的构造器，因此 LinkedHashSet 只维护 插入顺序。
-
LinkedHashMap 中所有的 Entry 被链接在一起，map 的遍历操作都是通过链表来完成的。
TreeMap
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
// K 必须实现 Comparable 接口
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
public TreeMap(Map<? extends K, ? extends V> m) { /*...*/ }
public TreeMap(SortedMap<K, ? extends V> m) { /*...*/ }
// Query Operations
public int size() { return size; }
public boolean containsKey(Object key) { return getEntry(key) != null; }
public boolean containsValue(Object value) {
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
if (valEquals(value, e.value))
return true;
return false;
}
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
public Comparator<? super K> comparator() { return comparator; }
public K firstKey() { return key(getFirstEntry()); }
public K lastKey() { return key(getLastEntry()); }
public void putAll(Map<? extends K, ? extends V> map) { /*...*/ }
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
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;
}
final Entry<K,V> getEntryUsingComparator(Object key) { /*...*/ }
final Entry<K,V> getCeilingEntry(K key) { /*...*/ }
final Entry<K,V> getFloorEntry(K key) { /*...*/ }
final Entry<K,V> getHigherEntry(K key) { /*...*/ }
final Entry<K,V> getLowerEntry(K key) { /*...*/ }
// NavigableMap API methods
public Map.Entry<K,V> firstEntry() { return exportEntry(getFirstEntry()); }
public Map.Entry<K,V> lastEntry() { return exportEntry(getLastEntry()); }
public Map.Entry<K,V> pollFirstEntry() { /*...*/ }
public Map.Entry<K,V> pollLastEntry() { /*...*/ }
public Map.Entry<K,V> lowerEntry(K key) { return exportEntry(getLowerEntry(key)); }
public K lowerKey(K key) { return keyOrNull(getLowerEntry(key)); }
public Map.Entry<K,V> floorEntry(K key) { return exportEntry(getFloorEntry(key)); }
public K floorKey(K key) { return keyOrNull(getFloorEntry(key)); }
public Map.Entry<K,V> ceilingEntry(K key) { return exportEntry(getCeilingEntry(key)); }
public K ceilingKey(K key) { return keyOrNull(getCeilingEntry(key)); }
public Map.Entry<K,V> higherEntry(K key) { return exportEntry(getHigherEntry(key)); }
public K higherKey(K key) { return keyOrNull(getHigherEntry(key)); }
// Views
/**
* Fields initialized to contain an instance of the entry set view
* the first time this view is requested. Views are stateless, so
* there's no reason to create more than one.
*/
private transient EntrySet entrySet;
private transient KeySet<K> navigableKeySet;
private transient NavigableMap<K,V> descendingMap;
public Set<K> keySet() { return navigableKeySet(); }
public NavigableSet<K> navigableKeySet() {
KeySet<K> nks = navigableKeySet;
return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}
public NavigableSet<K> descendingKeySet() {
return descendingMap().navigableKeySet();
}
public Collection<V> values() { /*...*/ }
public Set<Map.Entry<K,V>> entrySet() { /*...*/ }
public NavigableMap<K, V> descendingMap() { /*...*/ }
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { /*...*/ }
public NavigableMap<K,V> headMap(K toKey, boolean inclusive) { /*...*/ }
public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) { /*...*/ }
public SortedMap<K,V> subMap(K fromKey, K toKey) { /*...*/ }
public SortedMap<K,V> headMap(K toKey) { /*...*/ }
public SortedMap<K,V> tailMap(K fromKey) { /*...*/ }
// Red-black mechanics
private static final boolean RED = false;
private static final boolean BLACK = true;
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;
// ...
}
}
-
TreeMap 的内部是 红黑树。key 必须实现 Comparable 接口，或构造时传入一个 key 类型的比较器。并且 key 不能为 null，因为无法排序。
-
TreeMap 的查询就是树的查询。遍历顺序是 key 的升序。
Hashtable
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
private transient Entry<?,?>[] table;
private transient int count;
private int threshold;
private float loadFactor;
private transient int modCount = 0;
public Hashtable(int initialCapacity, float loadFactor) { /*...*/ }
public Hashtable(int initialCapacity) { this(initialCapacity, 0.75f); }
/**
* Constructs a new, empty hashtable with a default initial capacity (11)
* and load factor (0.75).
*/
public Hashtable() {
this(11, 0.75f);
}
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
public synchronized Enumeration<K> keys() {
return this.<K>getEnumeration(KEYS);
}
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1; // 扩容 2 倍 + 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;
}
}
}
// key 和 value 不能为空
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(); // key 为空会抛出异常
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;
}
/**
* Hashtable bucket collision list entry
*/
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
// ...
}
// Types of Enumerations/Iterations
private static final int KEYS = 0;
private static final int VALUES = 1;
private static final int ENTRIES = 2;
private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
final Entry<?,?>[] table = Hashtable.this.table;
int index = table.length;
Entry<?,?> entry;
Entry<?,?> lastReturned;
final int type;
/**
* Indicates whether this Enumerator is serving as an Iterator
* or an Enumeration. (true -> Iterator).
*/
final boolean iterator;
protected int expectedModCount = Hashtable.this.modCount;
Enumerator(int type, boolean iterator) {
this.type = type;
this.iterator = iterator;
}
// ...
}
}
-
Hashtable 与 HashMap 原理是一致的。
相比于 HashMap ：
-
Hashtable 是线程安全的，方法是同步的
-
Hashtable 初始容量为 11，每次扩容 2 × size + 1
-
Hashtable 遍历使用 Enumerator
-
Hashtable 继承 Dictionary
-
Hashtable 的 key 和 value 均不允许为 null
-
Hashtable 的 hash 值直接使用 key.hashCode()
-