HashMap源码解读

2017-12-07 撒旦发送到

HashMap和HashTable可以说是Map家族中最常用的两个类了,而两者又都是通过Hash表来进行key值的映射的,因此选择将两者进行统一的比较分析,并借此了解jdk中是如何实现hash表结构的map对象的。这篇博客篇幅较长,但我觉得有很多是很有用的知识,希望读者可以耐心阅读。

HashMap

HashMap是Map的一个Hash表类型的实现,由于Hash表的常数时间内的寻址特性,使得HashMap可以在常数的时间内执行get(key), set(key, value)方法。HashMap支持存储key和value为null的元素。

HashMap有两个非常重要的初始化参数:initial capacity和load factor。initial capacity决定了存储hash(key)的返回值的bucket。因为HashMap是使用了数组加链表的形式进行元素的存储的(1.8之后增加了红黑树的支持,当链表长度大于8之后,会将链表进行 树化 )。

load factor是另一个重要的指标,它标示了这个HashMap什么时候需要扩容,默认值是0.75.举个例子,假如初始容量为100,则当hash(key)的返回值达到75个的时候,该HashMap需要扩容,并rehash,扩容后的大小是扩容前的两倍。load factor只和填充的bucket有关,而和该bucket对应的存储了多少个Node无关,即使该bucket只存了一个,也会将填充数+1。因此,如过initial capacity * load facotr > entry数量,则HashMap不会进行rehash。因此,如果预先知道entry的数量,计算相应的capacity值,有利于提高存取效率。

HashMap不是一个同步类,如果需要进行多线程的访问,可以考虑三种方式

  1. 使用 Map m = Collections.synchronizedMap(new HashMap(...));
  2. 使用HashTable,同步类
  3. 使用ConcurrentHashMap

如果有高并发读的需求,强烈建议使用ConcurrentHashMap,它是无锁读的。

源码分析

bucket长度与Hash函数

HashMap是通过一个内部类Node类存取K/V值的,该Node包含了4个属性:hash,key,value,next。hash存的就是key值经过Hash之后的返回值,HashMap通过hash字段,快速的定位该node; key值就是K/V中的键,value就是K/V中的值,next指向了链表中下一个节点(先分析数组+链表的存储结构,之后分析红黑树,红黑树的节点为TreeNode)。

Node的equals方法比较重要,它决定了HashMap中存储新的的K/V对时,原来的Node中是否有与新的K/V对相同,如果equals为真,则覆盖原来的值,否则,new一个新的Node。equals方法如下:

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;
}
  • 有代码可知,先判断引用是否一致,如果相同,则返回true,然后判断是否为Map.Entry的一个子类,之后判断K/V是否同时相同,如果是,则返回true,否则,返回false。这段判断是否相同的逻辑,对于Set中的元素也使用,因为Set也是使用Map来存储元素的。

HashMap通过一个Node数组来表示存储hash(key)的bucket入口,默认大小为16.这个数字比较特别,是2的4次方,bucket的大小必须是2的整数次幂,这样做的好处是,length-1正好是低x位均为1,起到一个掩码的作用,而掩码的作用与求余相同。如初始长度16,-1后的二进制为1111,和hash值进行与操作,相当于hash值对16求余。这个求余操作用于将hash值映射到Node数组的空间中,在寻找key对应的bucket时,只需要table[(length-1) & hash(key)]即可,然后遍历其指向的链表即可找到K/V对。HashMap为了保证容量为2的整数次幂,使用了一个方法。

static final int tableSizeFor(int cap){
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
  • 该方法很好理解,将cap-1的二进制数为1的最高位以下的所有位置为1,然后加1,则为一个形如00100000的数。

上面提到了hash函数,HashMap的hash函数比较简单,只是简单的将key的高16位与低16位进行位异或即可。这是一个扰动函数,为了防止低16位数的规律性。原因是,由于Node数组长度有限,无法对应hash函数的返回值,而hash函数低x位有可能有一定的规律性,为了减少其低16位的规律性,又因为高16位在求数组index中永远不会用到,因此,选择将高16位直接与低16位做异或,将高16位作为一个扰动信号,维持hash函数的散列性。

put、get源码解读

下面着重分析put(key,value)和get(key)这两个方法。

put的核心方法是putVal方法,其定义如下:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict){
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //table为空,需要初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //bucket入口为空,直接new一个Node,放到数组的对应坐标处
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //hash值冲突,开链法解决冲突
    else {
        Node<K,V> e; K k;
        //链表第一个节点就是要put的key,赋值给e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //链表长度大于8,已经被树化
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                //到达链表末尾,将k/v对添加到最后
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //大于阈值,进行树化
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //链表中已存在key值
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //该key值已存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //key值不存在,已添加进HashMap
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

首先介绍参数,后两个为布尔值,作为flag,表示存储策略,onlyIfAbsent为true的时候,put方法检测到已有值时不会覆盖,evict为false的时候,Hash表处于创建,初始化时刻。hash,key,value分别对应Node中的对应属性。

在上面的代码段中已经添加了必要的注释,最终的结果只有两种。一、key值已存在,根据策略替换原值,返回oldValue;二、key值不存在,找到一个合适的位置插入,返回null。为了达到最后的结果,大致有以下几个步骤:

  1. 判断table是否为空,若为空,则执行resize方法,根据初始容量,初始化table数组
  2. 根据key值运算后的hash值,与数组长度求余(通过(n-1)掩码与运算求余),找到在数组中的index,如果该index对应的为null,则将新的k/v插入到该位置,相当于一个bucket的入口,由此可知,resize只是初始化数组,并没有给数组中的Node进行初始化,因此index位置仍为空
  3. 如果bucket的入口非空,则表示Hash冲突,对应的链表长度>=1,需要通过开链法解决冲突。有三个判断逻辑:链表头节点key值与添加的key值相等;链表已经树化,需要搜索红黑树查找该key值是否已存在;链表未被树化,且头节点key值与新增key值不同,需要遍历链表查找该key值是否存在。
  4. 上面的判断逻辑中,不管是哪一种,只要key值已存在,则赋值给e,因此在后面判断e是否为null,若不为空,则表示已存在,根据策略决定是否覆盖原值
  5. 如果key值不存在,需要将modCount自增1,然后将size自增,判断大小是否超过阈值,是,则通过resize方法double原table数组的容量。

在上面的代码块中,有两个方法比较有趣,afterNodeAccess和afterNodeInsertion方法,它们在HashMap中代码段为空,它们的作用主要是为了让LinkedHashMap继承,这样的话,LinkedHashMap不需要重写putVal方法,而只需要重写afterNodeAccess和afterNodeInsertion方法即可,因为LinkedHashMap需要保证HashMap的顺序,因此需要在putVal之后进行顺序的调整,就是通过上面的两个方法执行顺序调整的。这个编程思想让我十分受用,父类定义了方法的流程,在此为putVal方法的流程,而对于父类中不需要的操作,通过将方法体书写为空,对父类的操作不会影响,而对于子类(LinkedHashMap),只需要重写那两个为空的方法,即可完成功能的增强(在此为保证Map的顺序,也就是key值插入的顺序)。

LinkedHashMap 是一个HashMap和double linklist的结合体,它保证的顺序为key值put的顺序

下面分析TreeNode的putTreeVal方法,它是putVal的树化版。它遍历红黑树以寻找是否已经存在要插入的key值,若存在,则返回该节点,否则,在合适的位置插入节点,并返回null.要分析putTreeVal,首先需要搞清楚TreeNode的结构,其定义如下。

static final class TreeNode<K,V>extends LinkedHashMap.Entry<K,V>{
    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;
}

红黑树的特性

  1. 根结点是黑的。
  2. 每个结点要么是红的,要么是黑的
  3. 如果一个结点是红的,那么它的俩个儿子都是黑的
  4. 任意从根到叶子的路径的黑色节点总数相同。
  5. 本质上是二叉搜索树,左子树节点小于当前节点,右子树节点大于当前节点

上面是典型的红黑树节点定义,包含了指向父节点的指针parent,左子节点left,右子节点right, red表示当前节点是否为红色。

下面来分析putTreeVal方法,其定义如下:

final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v){
    Class<?> kc = null;
    boolean searched = false;
    //找到红黑树的根节点
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //当前节点hash大于h,在左节点查找
        if ((ph = p.hash) > h)
            dir = -1;
        ////当前节点hash小于h,在右节点查找
        else if (ph < h)
            dir = 1;
        //ph == h 且 p.key == k
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // K不是Comparable的实现类 或 pk的类型 不是Comparable的实现类
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                //递归的在左右子树中查找h, k
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            // dir = -1 / 1
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        //到达叶子节点,没有找到key值,插入新节点
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next; //next属性位于HashMap.Node中,在此进行设置,主要是为了方便红黑树和链表之间的转换
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            //插入,并重新平衡红黑树,并确保root节点为bucket的第一个节点
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

我在上面的代码块中添加了必要的代码注释,相信重要的代码分支的含义已经比较清晰。总的来说,putTreeVal方法通过一个循环,从root节点寻找红黑树中是否已存在要插入的key值,最后的结果只有两种,一是找到了,则返回该key值对应的在树中的节点;而是没有找到,此时新建TreeNode,并将其插入到红黑树中,返回null。这里的逻辑与链表插入的逻辑相同,返回null后,通过判断即可得知新增的key值成功插入,且之前不存在。红黑树中查找节点的算法比较简单,和二叉搜索树相同,如果key小于当前节点key,则到左子树查找;大于则到右子树查找,直到找到key值或者到达叶子节点。遍历的方向通过dir表示,-1表示向左子树遍历,1表示向右子树遍历。方法中比较key值得逻辑有几块,主要是满足泛型需要的,key的比较方式有四种:

  1. 通过 <,=,> 比较运算符直接比较;
  2. 通过Object的equals方法比较是否相同,通过Comparable的compareTo比较返回-1或1;
  3. 若key不为Comparable的实现类,则通过find方法查找该key值,find方法只会遍历树一次(searched置为true后,不调用)
  4. 如果上面的方法都没法进行key值得比较,调用tieBreakOrder方法,通过内部System.identityHashCode(key)进行比较,返回-1或者1

最终如果没有找到key值,则new一个TreeNode,进行插入。此处的插入是要满足红黑树的特性的,因此在balanceInsertion(root, x)中插入了x,并整理该树以满足红黑树的性质,返回之后的根节点。moveRootToFront方法将返回的根节点确保其位于tab的对应index位置,也就是确保根节点位于bucket的入口处。

balanceInsertion方法插入节点x,并平衡红黑树,其代码如下:

static <K,V> TreeNode<K,V>balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x){
    x.red = true;
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // x 为根节点
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // x的父节点为黑色节点 或 x的父节点为根节点
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // x的父节点为其父节点的左子节点
        if (xp == (xppl = xpp.left)) {
            //x的叔父节点也为红色节点,不能通过旋转解决颜色冲突,直接通过改变颜色,但改变之后的xpp与其父节点都为红色,在下一次循环中解决冲突
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            //与父节点颜色冲突,都为红色
            else {
                // x 是xp的右子节点, xp是xpp的左子节点,此时需要两次旋转,先左旋,后右旋
                if (x == xp.right) {
                    //左旋
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true; //右旋后xpp成为xp的右子节点,应该变为红色
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else {
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

上面代码块已经加入了我自己的理解,这里主要是通过插入后,判断是否与父节点颜色冲突(均为红色),然后通过二叉树的旋转来保持平衡,旋转的策略分为了左旋和右旋,主要根据插入节点、父亲节点、祖父节点的关系决定,具体规则可以参考 红黑树数据结构剖析 ,写的比较详细。

到此终于把putVal方法分析完了,小小的一个put方法牵扯了这么多的知识,包含了开链法解决Hash冲突,链表插入,红黑树的插入以及每种插入前的查找。既然在此分析到了TreeNode,就小结一下,TreeNode实现的是红黑树的数据结构,在其中包含了插入、删除、查找、split方法,其中插入、删除、查找比较好理解,split方法主要是用在HashMap的resize中,通过将红黑树分为lower和upper两个红黑树,放置到相应的两个bucket处。

分析完put方法,下面分析get方法,有了put的铺垫,get相对来说就简单一些了。getNode是get的核心方法,其定义如下:

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); //do-while遍历链表
        }
    }
    return null;
}

逻辑就比较简单了,首先判断第一个节点是否为要找的key值,然后如果是链表形态,则do-while结构遍历链表;如果是红黑树形态,则调用getTreeNode查找并返回对应的TreeNode。getTreeNode的方法调用了TreeNode的find方法,其定义如下:

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; //通过Comparable的compareTo方法判断,-1遍历左子树,1遍历右子树
        else if ((q = pr.find(h, k, kc)) != null) //
            return q;
        else
            p = pl; //上面两个是递归调用find的两种形式,一个为递归find右子树,另一个为循环遍历左子树
    } while (p != null);
    return null;
}

find的逻辑与putTreeVal的查找逻辑十分类似,也是通过比较符、compareTo方法,递归调用find来查找,不同的是,这里不使用System.identityHashCode来比较了。

有了put和get方法,基本上HashMap的框架就有了,接下来分析resize方法,该方法扩容table的size,使其double原来的大小,这也是HashMap如此好用的原因,我们不需要考虑HashMap的大小,只要使用put、get即可。

resize方法

resize方法有两个作用:1、初始化table; 2、double原table的大小。 resize的定义如下:

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;
                        //oldCap形如00100000,此处相与,类似于选择器,为0的放在lower list,为1的放在upper list
                        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);
                    //将lower list放在newTab的j处
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //将upper list放在newTab的j+oldCap处,原来j处的list一分为二,相距oldCap距离
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

if (oldTab != null) 之前的语句比较容易理解,计算newCap(为oldCap的两倍,左移1位),然后通过new来初始化数组。到 if (oldTab != null) ,说明之前table中已经存了k/v(put方法已经被调用过),需要将原来的K/V值移动到新的table中对应的index处。移动的逻辑也比较简单,如果链表只有一个节点,则直接赋值给新数组的对应index处,这里有一个隐含逻辑,就是当e1.hash & (oldCap-1) = j的时候,e2.hash & (oldCap - 1) = k; j不等于k,则 e1.hash & (newCap - 1) 一定不等于 e2.hash & (newCap - 1),因为它们的低x位不同(x为oldCap-1的1的个数)。因此不需要考虑e.hash & (newCap - 1) 处是否已存在节点,因为一定为null。

如果链表长度大于1,则需要将链表一分为二,分别为lower list和upper list。 将lower list放到 newTab的j处,upper list放到newTab的j+oldCap处。 但它的分割方法是通过e.hash & oldCap进行的,如果为0,则放在lower里面,否则,放在upper里面。但这种方法个人认为并不能保证等分,它的分割是否平均取决于hash值在该位的随机性。split方法是TreeNode的分割版本,其逻辑也是通过e.hash & oldCap进行分割的,在此不再赘述。

遍历源码分析

HashMap的遍历方式与Map的一样,有三种遍历方式,分别为:key的遍历,value的遍历,Entry(K/V对)的遍历。三者的实现一致,下面以key的遍历为例进行分析。

keySet()方法会返回一个Set 对象,它的实现类是一个内部类KeySet,继承了AbstractSet ,通过KeySet的iterator方法,可以返回一个KeyIterator对象,KeyIterator也是一个内部类,继承了HashIterator,ValueIterator(value的遍历对象),EntryIterator(Entry的遍历对象)也继承了该类,因此,在此分析HashIterator即可。

HashIterator在初始化的时候会将next指向从table的0开始数,第一个存了Node的位置,next指向的为一个Node。构造函数定义如下:

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

nextNode方法返回next当前指向的Node,并将next指向下一个Node。

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();
    //将next指向下一个不为空的Node
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    return e;
}

到此为止,HashMap就分析结束了,主要分析了HashMap的put、get方法,存储方式,扩容方式,遍历方式,这些是Map的几个最重要的操作,也是体现HashMap之所以为HashMap的特征,接下来,分析两个和HashMap关系密切的类:LinkedHashMap、HashTable。

LinkedHashMap

LinkedHashMap关系最为密切,它是在HashMap的基础上进行的功能增强,提供了双向链表的存储结构。这里的意思不是说LinkedHashMap完全舍弃了HashMap使用数组的存取方式,而是说在此基础上,通过添加一个双向链表(节点类型为LinkedHashMap.Entry , 有一个before指针,和after指针,因此为双向链表),保证了Map的顺序,而在遍历时,舍弃了上面HashMap的HashIterator,选择直接对双向链表遍历,因此就达到了保证顺序的目的。

LinkedHashMap中有一个比较有趣的属性,叫作accessOrder,它是一个布尔值,表示了双向链表所保证的顺序是否为访问顺序。如果accessOrder为true,则保证的为访问顺序,即通过put修改了某个key对应的value后,会将该节点放在双向链表的最后。如果accessOrder为false,则保证的是插入顺序,此时put修改不会更改该节点在双向链表中的顺序。

LinkedHashMap重写了HashMap的newNode方法,在newNode中调用了linkNodeLast方法将新生成的节点放到了双向链表的最后。因此,在HashMap的putVal方法中调用newNode时,实际调用的为LinkedHashMap的newNode方法,这就达到了复用putVal方法的目的。在插入、修改、删除Node后,通过afterNodeInsertion,afterNodeAccess,afterNodeRemoval修改LinkedHashMap中的双向链表即可。三个方法的含义为

  • afterNodeInsertion在节点插入后执行,在LinkedHashMap中没有实际作用,它提供了一个潜在的功能,就是在插入后删除eldest节点,可以达到一个类似于固定长度的缓冲队列的功能。
  • afterNodeAccess在accessOrder为true的时候触发,将修改或者通过get访问的节点放到双向链表的最后。
  • afterNodeRemoval在删除节点后触发,删除双向链表中的对应节点。

LinkedHashMap的遍历同构一个内部类LinkedHashIterator实现了双向链表的遍历,在此不再赘述。

HashTable

HashTable经常拿来跟HashMap比较,是因为在ConcurrentHashMap,它可以作为一个线程安全的HashMap来使用。但实际HashTable的出生日期比HashMap还要早一些,从1.0开始就存在了,而HashMap在1.2才出现。HashTable就是一个标准的Hash表,继承了Dictionary抽象类,实现的是基本的K/V操作,没有HashMap那么多的基于性能的优化。HashTable中很多方法直接使用的是synchronized修饰,因此是线程安全的。HashTable不能将null作为key值存放,且key值必须是一个对象,定义了hashCode和equals方法。存储结构就是标准的数组+链表的方式,解决Hash冲突的方法就是采用标准的开链法,每次将新的node放在链表的头部。下面分析一下put方法,其定义如下:

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;
    //hash值为key的hashCode,因此key必须实现了hashCode方法
    int hash = key.hashCode();
    //index和31个1相与,然后对length求余,因为int长度为32,第一个1代表为负数,而index>=0
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        //key值已存在,则覆盖
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }
    //key值不存在,新增节点
    addEntry(hash, key, value, index);
    return null;
}

逻辑很清晰,先计算hash值在数组中的index,然后在index对应的链表寻找是否有对应的key,有的话覆盖旧值,否则,调用addEntry方法,新增节点。

private void addEntry(int hash, K key, V value, int index){
    modCount++;

    Entry<?,?> tab[] = table;
    if (count >= threshold) {
        // Rehash the table if the threshold is exceeded
        rehash();

        tab = table;
        hash = key.hashCode();
        index = (hash & 0x7FFFFFFF) % tab.length;
    }

    // Creates the new entry.
    @SuppressWarnings("unchecked")
    Entry<K,V> e = (Entry<K,V>) tab[index];
    //将新增节点放在链表的头部,原来的链表头e,作为新节点的next节点
    tab[index] = new Entry<>(hash, key, value, e);
    count++;
}

如果大小大于阈值,需要进行rehash,对数组进行扩容。rehash方法double当前的容量,然后将旧节点放到 (e.hash & 0x7FFFFFFF) % newCapacity 处,代码不在此处粘贴。

HashTable的遍历时从数组的末尾index递减的顺序进行遍历的,通过一个内部的Enumerator来实现,通过属性type判断要取的是key值还是value值或者Entry值,在此不做赘述。

由上面所说,HashTable大多数的方法都为同步方法,已经不太适合多并发编程,因此推荐使用ConcurrentHashMap类满足并发需求,ConcurrentHashMap的读不加锁,因此适合频繁多线程读的场景。

总结

分析HashMap是我读Collection 家族的最多收获的一次,在过程中不仅复习了开链法解决Hash冲突,还学到了通过掩码实现类似于求余的操作,并搞懂了为什么capacity为什么必须是2的整数次幂,在后面有学习了一下红黑树的相关知识,虽然让我实现一个红黑树还是困难重重,但已经增加了很深对于红黑树的理解。而且在分析LinkedHashMap的时候,了解了LinkedHashMap巧妙复用HashMap的put方法的编程技巧,这一点也是让我受益匪浅。

> if(sad) {
>    sad = false;
>    beAwesome();
> }
>

用户评论
开源开发学习小组列表