jdk源码之java集合类（四）——Map & Set
我们来看一下Map和Set这两个集合
前两篇我们已经把List和Queue给看完了，这一篇之所以Map和Set一起看，主要是由于Map和Set的关系太紧密了。虽然在接口定义的时候二者并没有太紧密的联系，无非就是Map会返回关于Key的Set、Value的List以及Key-Value组合的Map.Entry的Set。但是，在二者实现类在实现的时候，尤其是Set在实现的时候，几乎就是把Map给用了一遍。所以如果单纯讲Set的话，我们除了看一看Set的类族结构外，其余的都会由一句“它调用了对应的Map，我们留到Map章节再讲”来结束，所以，为了让阅读更加直接彻底，我们将Map和Set放在一章中完成讲解。
Map和Set拥有不少实现类，为了方便起见，我们以其中最具代表性的Hash和Tree为主要实现类来讲解，先看类图：
可以看到，Set和Map在类族设计上是完全对应的，Set有AbstractSet，Map有AbstractMap。而对应又有HashSet、TreeSet，而HashSet和TreeSet又分别和HashMap和TreeMap聚合。
一、接口设计
我们先看Set的接口设计，直接上图：
在Set的接口中，最重要的应该属于add和contains方法了，Set和List的区别在于，它不顺序地存储数据，而是以一定规律存放，因此它不具有按index获取（get方法）的功能，但是却方便了contains（检查是否存在）方法的作用。
然后再看Map：
Map中除了基本的增删改查（put、remove、get等等）外，最具特性的遍历性质方法有三：entrySet、keySet、values，分别返回key-value键值对的Set、key的Set、value的list
值得一提的自然是这个键值对，在Map接口中还有个内部接口Map.Entry：
这个接口的作用主要存放键值对，事实上这个接口还是非常重要的，我们接下来看实现的时候便知道了。
二、抽象类
先来看AbstractSet，AbstractSet在继承了AbstractCollection以后只实现了三个方法：equals、hashCode、removeAll。前两个方法我们单纯从集合的角度看似乎不怎么要紧，而removeAll无非也是调用了迭代器的remove方法：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}通常根据我们的经验，迭代器的实现（在子类中实现）无非也是调用子类本身具有的增删方法。
然后再看AbstractMap，相比起AbstractSet，AbstractMap这个抽象类就显得非常“劳心”了，他替子类完成了一系列重要的方法，我们简单看几个：
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}containsValue，用来检测是否包含此类value值，通过获取entrySet的迭代器（说白了就是遍历entrySet）然后检查是否有哪个value和传入值一样。与这个方法类似的还有containsKey，这里就不展示源码了；
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;
}get方法，如此核心的方法被放在抽象类中实现，这在几大集合家族中是绝无仅有的（别的较少参数的get调用较多参数的get的不算），究其原因还是在Map中，get方法可以不直接和数据源的存储方式相关，它获取entrySet，并通过遍历的方式拿到需要的值。
但是，对的我要说但是了，这样的get方法显然在效率上很有问题，所以事实上这里的get方法只是给了Map家族一个最基本（也可以说最差的）get的实现，事实上在其子类中都会重写get方法。此外remove和get也类似，遍历entrySet。
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}putAll，调用尚未被实现的put方法完成该完成的事情。
AbstractMap中几乎提供了put以外所以方法的基本实现，但是其在子类中均被重写，与get方法相同，AbstractMap中许多方法都是给出了最基本的实现方式，以便让一些并没有更优实现方式的数据结构不用去重复实现。但是由于我们本文主要阅读的是Hash和Tree，这种实现显然并没有太大效应，所以我们可以直接略过去阅读子类的实现。
三、HashSet & HashMap
先看HashSet吧，HashSet中：
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}包含了一个HashMap，并在构造函数中初始化。
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
。。。。。。。
之后的所有方法都是调用HashMap来完成的。。。。（这可能是我看到现在最水的一个实现类了唉哈哈哈）
那么既然如此，就直接来看HashMap吧，事实上在前面的文章jdk源码之java集合类（一）中我已简单讲解了HashMap的实现以及HashMap和HashTable的区别，并给出了最基本的add方法的源码解读。这里权且作为复习再详细看一遍：
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;
}
}首先他给出键值对的存放单元Map.Entry的实现类Node。这个实现没啥好说的，应该都看得懂。
/**
* 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;而后hashMap内部存放一个Node的数组。
/**
* 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;并且记录长度。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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;
}重写抽象类中遍历获取的get方法，通过hash值和表长度求并运算的结果来得到位置的下标，返回其值。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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;
}put方法相对复杂一些，他需要先判断hash&length位置是否为空，若是，则直接复制，若非，即如果当前key已经在表里，则覆盖value的值。并且还会返回oldValue的值。但是如果这个位置的值还是不对，即hash&length这个位置被占了，但是占位的为null或者占位的key不等于传入的key，就往后移动下标直到找到。（典型hash表的处理），如果还是找不到，size大于这个threshold，就重新调整数组的大小。
这里顺便也可以理解为何size不直接用数组的length来表达（好像这是个很蠢的问题）
增和查都看了，删除修改应该也差不多，我们把核心往遍历上靠。去看一看几个Set的方法：
public Set<K> keySet() {
Set<K> ks;
return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
}
final class KeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<K> iterator() { return new KeyIterator(); }
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super K> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}keySet，我一直感觉这个设计非常骚：HashSet里有HashMap，HashMap又有KeySet。。。
话说我们看到KeySet，总体来讲很好理解，但是有一点不太明白，就是几个基本操作：add、remove等等没有实现，因为其父类是AbstractSet，我们刚刚前面也说了AbstractSet基本啥也没干。这里我们要看到AbstractCollection里的实现：
public boolean add(E e) {
throw new UnsupportedOperationException();
}在讲解List家族的时候我曾经说过，AbstractCollection具有典型的抽象类设计特点，把最核心的部分留给子类实现。但是我当时并没有提到为何这里要通过直接抛异常的方式实现add，而不是将其作为抽象方法强制子类去实现？
我曾经在一篇学习总结中对反射有个定义：抛弃编译检查，把错误留给Exception；诚然这种方式确实降低了容错性，但是如果开发人员有做过详细的单元测试的话，这种容错上的问题基本可以忽略，替代它的则是更灵活的实现方式。
集合，作为一种工具类，他不需要开发人员批量去实现，相反的只需要根据也无需要去调用所需的集合，或是自己实现一两个自己需要的集合即可，作为工具类，完整的单元测试的需要是不可避免的。而AbstractCollection中这种设计给与那些不愿提供对应操作的集合类的实现提供了方便。譬如这里的keySet，我们几乎可以肯定，HashMap的keySet势必是只读的，其写操作应该在HashMap中完成。而也是由于AbstractCollection将对应操作实现成为直接抛出异常而不是留作抽象方法，因此keySet可以免去这个势必会抛出异常的方法的实现步骤。
public Collection<V> values() {
Collection<V> vs;
return (vs = values) == null ? (values = new Values()) : vs;
}
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. If the map is modified
* while an iteration over the set is in progress (except through
* the iterator's own <tt>remove</tt> operation, or through the
* <tt>setValue</tt> operation on a map entry returned by the
* iterator) the results of the iteration are undefined. The set
* supports element removal, which removes the corresponding
* mapping from the map, via the <tt>Iterator.remove</tt>,
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
* <tt>clear</tt> operations. It does not support the
* <tt>add</tt> or <tt>addAll</tt> operations.
*
* @return a set view of the mappings contained in this map
*/
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 (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}其values和entrySet方法的实现细节也类似，这里就不做详解了。
四、TreeMap
TreeSet的实现和HashSet类似，基本是调用TreeMap来实现的，我们就直接看TreeMap的实现吧。
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;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
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 valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}先来看他特别标准的树节点Entry的实现，key、value，左节点右节点。
private transient Entry<K,V> root;
/**
* The number of entries in the tree
*/
private transient int size = 0;
/**
* The number of structural modifications to the tree.
*/
private transient int modCount = 0;存放根节点。
至于其内部的具体实现，其实基本就是树结构的一个java实现而已，我们这里可以看个put方法：
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
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;
}step1：看看树是否为空，若是，把根节点设置为新传入的key-value；
step2：从根节点开始遍历，比较节点的key和传入的key，若大，往右，若小，往左，若为空，则赋值。
这里还有个细节就是comparator是否存在，TreeMap是允许传入比较器的，如果有比较器就通过比较器比较，如果没有则根据默认的比较方法（这里这个默认比较方法比较复杂，就是key的类型必须实现Comparable接口，基本上么。。。看图）
可以看到我们通常认为能比较的东西都可以比较，不能比较的东西你要么自己去实现比较的方式，要么就让这个被比较的东西自己实现可比较（comparable）接口。
看完put方法以后，对于TreeMap的内部数据结构应该有个大概了解了，其余的方法就不再叙述了，有兴趣自行阅读源码。
小结
到目前为止，我们已经把List、Queue、Set、Map的基本情况都说明了，本篇虽然略过了HashTable、ConcurrentHashMap之类的方法，但是一来是因为集合类的第一篇已经描述过了，二来是后面我再重新阅读CAS的时候或许还会重新提到Concurrent的一些集合类。