HastSet, HashMap(二) 看看源码

前言

上面我们已经对Hash的工作原理，以及HashSet和HashMap的基本的介绍了。那么现在我们就直接从HashMap的原码开始看起吧。

HashMap源码

先看一下HashMap的空参构造函数。

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

里面对一个属性loadFactor做了一个赋值，其余的什么都没有做。联系到之前我们说的ArrayList的源码，我们不难猜出HashMap将在我们第一次使用put操作的时候加载底层的数据结构，实现了所谓的懒加载的机制。不过我们似乎先要将这个this.loadFactor搞清楚到底是个什么玩意。

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * The load factor for the hash table.
 *
 * @serial
 */
final float loadFactor;

似乎什么也看不出来，这到底是一个什么玩意。不过按照中文的直译，这个东西应该被称为——装载因子。不过现在这个东西其什么作业我们还是不得而知，需要进一步的看源码。不过想要看懂下面的源码还是需要先来看看HashMap中有什么属性，也就是说用了什么结构。

table

/**
 * 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;

先看第一个，table。table前面有个限定词transient，这个之前也是说过的，加上了transient的属性在对象被序列化的时候将不会被序列化，也就是说不会被写入到文件中去。反序列化之后值将会被初始化。

看上面的注释，说这个table将会在第一次使用的时候被初始化，这正印证了刚才我们的猜想。后面还说了如果不够用的话这个数组将会扩容，一般规则是变成原来的两倍的大小，这个和Vector的规则是一致的。ArrayList的扩容规则是变成原来的1.5倍，StringBuilder则是变成原来的两倍加上2.

实际上这个table就是我们说的组成散列的那个数组，那么链表该如何来呢？我们看一下Node中的属性就明白了。

/**
 * 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;
    ......

hash明显是用来存放放入的对象的hash值的，后面还有一个next属性，就是通过next属性，一个又一个的Node构成了一条链表。我们还注意到key是final的，但是value不是。那是因为如果我们插入相同的键的不同值，后面的那个值将会覆盖前面的值，所以不是vlalue不是final的。

entrySet

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

Map.Entry这个类，我们之前也已经说过了，至于entrySet就是返回键值对的集合，如何使用我们之前也说过了，这里不在赘述。

threshold

/**
 * The next size value at which to resize (capacity * load factor).
 *
 * @serial
 */
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;

threshold是阈值的意思。不过这个东西比较有意思的地方是，竟然出现了单行注释//。emm，，有点儿奇怪。注释中说。这个阈值是table将要改变容量时大小的位置，后面还标注了capacity * load factor。容量乘以上面的提到的加载因子。那么谜团也就解开了，HashMap的扩容不是等到table放满了才扩容。比如说容量是16，默认的加载因子是0.75，那么等到table的被占用12个时候可能就要扩容了。当然这里扩容的具体的细节我们是不知道的。下面的单行注释就是一些细节上面的问题。

put源码

其实要说的也就这几个属性，其他的属性还有点儿看不懂。还有一个属性是loadFactor之前已经说过了。

现在我们就好好的来看看put方法的源码。

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with {@code key}, or
 *         {@code null} if there was no mapping for {@code key}.
 *         (A {@code null} return can also indicate that the map
 *         previously associated {@code null} with {@code key}.)
 */
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;
    .......

从put方法中，我们进入了putVal方法。其中hash函数是用来计算对象的hash值，这里可以不管他。不过我们可以稍微观摩一下hash函数的源码。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这里我们还是需要注意一点的，HashMap是可以放null值的。从上面的函数就可以看出来。如果放null的key的话，返回的hashCode的值是0。

putVal函数最后还有两个参数，其实不是很重要。onlyIfAbsent名如其意，只有当没有对象的键的时候添加，也就是说不要给我来所谓的替换值的操作。evict这个单词是真的不认识，不过注解中说如果是假的话，就开启创建模式。说实话有点懵。这里先不关注这个了。

直接看30行的那个if，此时table还没有创建，毫无疑问是空的，此时将进入resize函数。

/**
 * 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 {
                            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;
}

这个函数写的真的是，又臭又长，我有点儿不想看，嘤嘤嘤！！不过还是耐心来看一下吧。

首先看注释这个函数作用是，初识化table，或者对table进行扩容，扩容的规则是变成原来的两倍。

假如我们是以空数组初识化的目的来的，首先就会进入到26行的else语句块中，然后给数组的大小进行赋了一个默认值。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

默认值是1 << 4也就是16，至于为什么不直接写16，那当然是1 << 4比直接写16的效率高啊。

新的阈值就被赋成了16 * 0.75f，也就是12。

通过31行代码，创建了table数组。而原来的数组就是空的。于是函数就直接返回了这个新创建的数组了。

假如我们是以扩容的数组的目的来到这个函数的，(这里就不探讨什么数组的长度直接超过了最大值的这种特殊的情况了)。其实将通过第一个if将容量和阈值变成原来的两倍。然后同样的通过31行代码新建了扩容后的数组。和初始化不同得是，此时将会进入39行的if中去。因为我们需要将原来的数组上面的数据拷贝到新创建的数组中来。看一下具体扩容的细节，我们发现了46行代码竟然判断了一下节点是不是TreeNode的节点。数组中挂的不应该是链表吗，怎么变成树了？难道说这也是HashMap的特殊手段吗？看到了48行代码中的else语句块，这个又是对链表的处理。

那么我们可以判定HashMap中table中储存的是既有链表又有树的。不过如何区分呢？这里还无从得知。

让我们回到putVal函数中去，通过resize函数，我们的table得到了初始化，下面就该放值进去了。其实这时候我们就不用考虑数组空还是不空了。

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;
}

看一下上面的第6行。要提一下上面忘了说了的,(length-1) & hash其实就是相当于length % hash这种取模运算，但是与运算的效率比较高，所以选择使用与运算。第六行中的(n-1) & hash就是该对象应该放入table的第几个位置中。如果那个位置是空的，也就是说== null，那么直接放进去就行了（tab[i] = newNode(hash, key, value, null);）。

如果那个位置不是空的，那么就是按照我们之前说的那个原则进行判断。其中下面依旧提到了treeNode，这个我们之前是没有想到的，我们认为是只有链表的。先来一步一步看吧。

第10行的if如果进入了就相当于key是和那个位置的节点的key是一样的。不过为什么使用这种方式进行判断呢？

if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))

其实这也就是我们之前说过的。先判断hash值p.hash == hash，如果hash值都不想等那么两个对象肯定是不一样的。然后我们应该比较得是key是否相等。这里使用的是

(k = p.key) == key || (key != null && key.equals(k))

在Java中三个逻辑云算法的优先级是! > && > ||。所以说上面的写法是后面的先结合。也就相当于。

(k = p.key) == key || (key != null && key.equals(k))

我们先比较key的地址，因为地址比较特别容易，如果地址相同，那么就是同一个对象，就没有必要进行equals操作了，因为equals操作可能是比较费时的，而且使用equals必须要key != null。然后13行就是处理树的操作。这里先不说。直接看一下后面的操作。

注意看一下第19行的操作binCount >= TREEIFY_THRESHOLD - 1，其中binCount其实就是已经存在的链表的节点数-1，因为binCount是从0开始的。其中TREEIFY_THRESHOLD的声明如下。

/**
 * 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.
 */
static final int TREEIFY_THRESHOLD = 8;

其实无论是从这个变量的名字还是从文档的注释中我们都可以清楚的了解到，这个变量是用来标记什么时候一个链表将要变成一棵树。其实在JDK之前，我们使用的HashMap的底层都是使用数组加上链表来实现的，到了JDK8之后变成了数组加链表加红黑树的形式。众所周知，当链表变得很长的时候，查询的效率会变得特别的低，而如果我们使用树结构的话，将会大大降低我们的查询速度。如果binCount >= TREEIFY_THRESHOLD - 1，就就代表这这个链表太长了，我们需要将其变成红黑树来存储。于是调用了函数treeifyBin(tab, hash);将链表变成了二叉树。

我们可以来看一看这个函数干了什么。

/**
 * 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)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            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);
    }
}

static final int MIN_TREEIFY_CAPACITY = 64;

看注释中的文档，如果数组的长度太小了的话，是不会将链表变成树的。其中，从第7行代码，我们可以得知，tab为空(这里明显不是空啊)或者是数组的长度太小（小于64）的话，会进行扩容而不是变树。然后下面就是变树的操作了，这里也不是二叉树专辑，所以不再介绍了。

我们继续回到putVal函数中，其中还有这样的代码。

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

这里的e代表的是什么？其实就是查到了和所要插入的对象的键是相同的节点。这时候一般来说我们需要进行替换操作。不过这就要提到我们之前说的那个onlyIfAbsent参数了。如果这个参数是false的话，我们只有在值为空的时候才可以替换值。(键当然不是空的)。后面的函数就没啥好说的了。

不过还有一点是我们需要说的，就是对象插入链表是以何种方式的呢？请看第19行代码

p.next = newNode(hash, key, value, null);

其中这里的p是当前比较过后不相等的节点。此时我们新建一个节点，直接挂到这个节点的后面。(此时p节点的后面没有元素了)。其实这也是JDK8中采用的方式，JDK7之前采用的是使用新元素指向旧元素。但是JDK8使用的是旧元素指向新元素。这也被称为是七上八下。其实也就是JDK7中采用链表的头插法。JDK8中采用的是链表的尾插法，仅此而已。

至此，我们的put源码就都看完了。下面简单的说一下get的源码。

get源码

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 *
 * <p>More formally, if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
 * key.equals(k))}, then this method returns {@code v}; otherwise
 * it returns {@code null}.  (There can be at most one such mapping.)
 *
 * <p>A return value of {@code null} does not <i>necessarily</i>
 * indicate that the map contains no mapping for the key; it's also
 * possible that the map explicitly maps the key to {@code null}.
 * The {@link #containsKey containsKey} operation may be used to
 * distinguish these two cases.
 *
 * @see #put(Object, Object)
 */
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;
}

相较于put方法，这个get方法可谓是简单的不要不要的。我们先通过hash找到数组的index。然后一次下去比较就完事了。不过还是要注意一下，下面到底是链表还是树，两者的比较的方法可是不同的。

总结

上面简单的看了一下HashMap的源码，其实也就是put和get这两个方法，其实再说白了也就只是通过put方法简单的说明了Java当中HashMap底层的实现。看起来确实是蛮复杂的，但是如果仔细研究，认真阅读还是可以看懂大部分内容的。毕竟每一个方法上面都有详细的注释的说明。