HashMap从认识到源码分析

2019-03-07 Java编程基础 HashMap 0 Comments Word Count: 5.9k(words) Read Count: 23(minutes)

Map

Map在开发过程中使用频率很高的数据结构，Map是Key-value键值对映射的抽象接口，该映射不包括重复的键，既一个键对应一个值。HashMap、HashTable、ConcurrentHashMap都是Java Collection Framework的重要成员。Map接口提供三种collection视图，允许以键集(keySet())、值集(values())或键-值映射关系集(entrySet())的形式查看某个映射的内容。

HasH表

我们知道数组的储存方式是在内存上分配固定的连续的空间，寻址速度快（查询速度快），时间复杂度为O(1)，但是在插入、删除元素时候需要移动数组的元素，所以插入、删除时候速度慢，时间复杂度为O(n)。链表的存储方式在内存上是不连续的，每个元素都保存着下个元素的内存地址，通过这个地址找到下个元素，所以链表在查询的时候速度慢，时间复杂度为O(n)，在插入和删除的时候速度快，时间复杂度为O(1)。
如果我们想要一个数据结构既查询速度快，插入和删除速度也要快，那我们应该怎么做呢？这时哈希(Hash)表就应时而生了，通过哈希函数计算出键在哈希表中指定的储存位置(注意这里的储存位置是在表中的位置，并不是内存的地址)，称为哈希地址，然后将值储存在这个哈希地址上，然后通过键就可以直接操作到值，查询、插入、删除等操作时间复杂度都是O(1)。
既然是键通过哈希函数计算出储存位置，那么哈希函数的好坏直接影响到哈希表的操作效率，如会出现浪费储存空间、出现大量冲突(即不同的键计算出来的储存位置一样)。

哈希函数可以将任意长度的输入映射成固定长度的输出，也就是哈希地址
哈希冲突是不可避免的，常用的哈希冲突解决办法有以下2种方法。

链地址法(拉链法)
采用数组和链表结合的方法，对哈希表中每个哈希地址建立一个线性表，将哈希地址相同的数据储存在线性表中，并将链表的头指针保存在数组中，哈希地址、键、值等信息一般保存在链表节点中。一般通过哈希地址计算出数组的下标，将哈希值相同的保存在下标相同的数组中的。拉链法适合经常进行插入、删除操作的情况。
开放定址法
开放定址法也称线性探测法，基本思想是：将哈希表T[0…m-1]看成是个循环向量，若初始探测地址为d，则最长的探测路径为：d，d+i，d+2i，…，m-1。即探测时候从地址d开始，首先探测T[d]，如果T[d]发生哈希冲突则继续探测下一个T[d+1]…直到探测到T[m-1]为止，i为自定义的常数。开放定址法很容易产生堆聚现象，所谓堆聚现象就是哈希表中的数据连成一片，在加入新元素的时候就容易产生哈希冲突。
拉链法和开放定址比较
拉链法：处理冲突简单，无堆聚现象，同时链表插入、删除操作简单，所以拉链法适合经常进行插入、删除操作的情况。
开放定址法：为了减少冲突，要求负载因子(装填因子)较小，当节点规模较大时候会浪费很多空间。且开放定址法在删除节点的时候，不能简单的将节点所在的空间置为空，否则将截断在它之后的节点的查找路径，这是因为各种开放定址法中，空地址单元都是查找失败的条件。因此在进行删除节点操作的时候，需要使用逻辑删除，即在被删除的节点上做删除标记。

负载因子 = 填入哈希表中的元素个数 / 哈希表的数组长度

HashMap

数据结构

HashMap采用上述的拉链法解决哈希冲突.HashMap是非线程安全的，允许键、值为null，不保证有序(比如插入的顺序)，也不保证顺序不随时间变化(哈希表加倍扩容后，数据会有迁移)。
我们创建个HashMap运行看看

HashMap<String, Integer> map = new HashMap();
map.put("语文", 1);
map.put("数学", 2);
map.put("英语", 3);
map.put("历史", 4);
map.put("政治", 5);
map.put("地理", 6);
map.put("生物", 7);
map.put("化学", 8);

通过图可以看到HashMap并不是按照插入顺序存储的(无序的)。
接下来我们看看HashMap的数据结构

HashMap有几个重要的成员变量，table，size，threshold，loadFactor，modCount。

table：是一个Entry[]数组类型，而Entry实际上是一个单向链表，哈希表的键值对都是储存在Entry数组中，每个Entry对应一个哈希地址，这里的Entry即常说的桶
size：是HashMap的大小，为保存的键值对的数量
DEFAULT_INITIAL_CAPACITY：HashMap默认容量(数组的大小) 默认为16
MAXIMUM_CAPACITY：HashMap的最大容量(2的30)，如果传入的容量大于这个值，则被最大容量替换
threshold：是HashMap的阈值，用于判断是否需要调整HashMap的容量。threshold=容量*负载因子，当HashMap中储存的键值对数量到达threshold时，HashMap就会将容量加倍的扩容
loadFactor：即负载因子

modCount：用来实现快速失败(fail-fast)机制的

快速失败机制：对于线程不安全(注意是线程不安全的集合才有这个机制)的集合对象的迭代器，如果在使用迭代器的过程中有其他的线程修改了集合对象的结构或者元素数量，那么迭代立刻结束，迭代器将抛出ConcurrentModificationException。

构造函数

HashMap有4个构造函数，如下：

//无参构造函数，负载因子为默认的0.75，HashMap的容量(数组大小)默认容量为16
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

//指定HashMap容量大小的构造函数 负载因子为默认的0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//指定HashMap容量大小和负载因子的构造函数
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);
}

//包含子Map的构造函数，负载因子为默认的0.75
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

为什么负载因子默认是0.75？按照官方给出的解释是，当负载因子为0.75时候，Entry单链表的长度几乎不可能超过8(到达8的概率是0.00000006)，作用就是让Entry单链表的长度尽量小，让HashMap的查询效率尽可能高。

由于当HashMap的大小(即size)大于初始容量(capacity)时候，HashMap就会扩大一倍，由于很多时候并不需要扩大这么多，所以当我们知道我们的数据的大小的时候，就可以在HashMap初始化的时候指定容量(数组大小)。
需要注意的是，我们指定的容量必须是2的幂次方，即使我们传入的容量不是2的幂次方，源码中也会将容量转成2的幂次方，比如我们传入的是5，最终的容量是8。

为什么容量一定要是2的幂次方？因为HashMap是数组+单链表的结构，我们希望元素的存放的更均匀，最理想的状态是每个Entry中只存放一个元素，这样在查询的时候效率最高。那怎么才能均匀的存放呢？我们首先想到的是取模运算哈希地址%容量大小，SUN的大师们的想法和我们的也一样，只不过他们使用位运算来实现这个运算(位运算效率高)，为了使位运算和取模运算结果一样，即hash & (capacity - 1) == hash % capacity，容量(Capacity)的大小就必须为2的幂次方。

put方法

在JDK1.8之前hashMap的插入是在链表的头部插入的，本文分析的是JDK1.8源码，是在链表的尾部插入的。

根据键(key)的hashCode()计算出当前键值对的哈希地址，用于定位键值对在HashMap数组中存储的下标
判断table是否初始化，没有初始化则调用resize()为table初始化容量，以及threshold的值
根据table数组长度和哈希地址做&运算(i = (n - 1) & hash)计算出该key对应的table数组索引，如果对应的数组索引位置没有值，则调用newNode(hash, key, value, null)方法，为该键值对创建节点。

这里思考个问题，当table数组长度变化后，是不是取到的值就不正确了？后面给出分析。这里简单分析下为什么不是直接按照哈希地址做数组下标，而是用table数组长度和哈希地址做&运算(i = (n - 1) & hash)(因为数组的大小是2的幂次方，所以这个运算等效于mod 数组大小的运算)计算数组下标，因为哈希地址可能超过数组大小，还有就是为了让键值对更均匀的分布的在各个桶(链表)中，也因为容量会变所以各个桶(链表)中的节点的哈希地址并不是相同的，相同的哈希地址也可能分到不同的下标。
如果根据哈希地址计算出该key对应的table数组索引有节点，且节点的键key和传入的键key相等，哈希地址和传入的哈希地址也相等，则将对应的节点引用赋值给e。
如果根据哈希地址计算出该key对应的table数组索引有节点，且节点的哈希地址和传入的哈希地址一样，但是节点的键key和传入的键key不相等，则遍历链表，如果遍历过程中找到节点的键key和传入的键key相等，哈希地址和传入的哈希地址也相等，则将对应的value值更新。否则调用newNode(hash, key, value, null)方法，为该键值对创建节点添加到链表尾部，如果追加节点后的链表长度 >= 8，则转为红黑树

如果e不为空，且onlyIfAbsent为true则不会覆盖相同key和相同哈希地址的value。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//如果参数onlyIfAbsent是true，那么不会覆盖相同key的值value。如果evict是false。那么表示是在初始化时调用的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab存放 当前的哈希桶， p用作临时链表节点  
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前哈希表是空的，代表是初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        //那么直接去扩容哈希表，并且将扩容后的哈希桶长度赋值给n
        n = (tab = resize()).length;
    //如果当前index的节点是空的，表示没有发生哈希碰撞。 直接构建一个新节点Node，挂载在index处即可。
    //这里再啰嗦一下，数组下标index 是利用 哈希地址 & 哈希桶的长度-1，替代模运算
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//否则 发生了哈希冲突。
        //e
        Node<K,V> e; K k;
        //如果哈希值相等，key也相等，则是覆盖value操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//将当前节点引用赋值给e
        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);
                    //如果追加节点后，链表数量》=8，则转化为红黑树
                    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;
            }
        }
        //如果e不是null，说明有需要覆盖的节点，
        if (e != null) { // existing mapping for key
            //则覆盖节点值，并返回原oldValue
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //这是一个空实现的函数，用作LinkedHashMap重写使用。
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //如果执行到了这里，说明插入了一个新的节点，所以会修改modCount，以及返回null。

    //修改modCount
    ++modCount;
    //更新size，并判断是否需要扩容。
    if (++size > threshold)
        resize();
    //这是一个空实现的函数，用作LinkedHashMap重写使用。
    afterNodeInsertion(evict);
    return null;
}

hashCode()是Object类的一个方法，hashCode()方法返回对象的hash code，这个方法是为了更好的支持hash表，比如Set、HashTable、HashMap等。hashCode()的作用：如果用equals去比较的话，如果存在1000个元素，你new一个新的元素出来，需要去调用1000次equals去逐个和它们比较是否是同一个对象，这样会大大降低效率。ashcode实际上是返回对象的存储地址，如果这个位置上没有元素，就把元素直接存储在上面，如果这个位置上已经存在元素，这个时候才去调用equal方法与新元素进行比较，相同的话就不存了，散列到其他地址上。

get方法

table不为空，且table的长度大于0，且根据键key的hashCode()计算出哈希地址，再根据桶的数量-1和哈希地址做&运算计算出数组的下标，该下标下不为空(即存有链表头指针)则继续往下进行，否则返回null。
如果和第一个节点的哈希地址、键key都相同，则返回第一个节点。

如果第一个节点的下个节点不为空，则继续，如果第一个节点为树的节点，则执行getTreeNode(hash, key)，在树中寻找节点，并且返回。否则遍历链表，找到键key、哈希地址一样的则返回此节点。

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 && // 如果索引到的第一个Node，key 和 hash值都和传递进来的参数相等，则返回该Node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) { //如果索引到的第一个Node 不符合要求，循环变量它的下一个节点。
            if (first instanceof TreeNode) // 在树中get
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {// 在链表中get
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

remove方法

table不为空，且table的长度大于0，且根据键key的hashCode()计算出哈希地址，再根据哈希地址计算出数组的下标，该下标下不为空(即存有链表头指针)则继续往下进行，否则执行6`。
如果哈希地址、键key一样，则将对应的节点引用赋值给node，然后执行4。否则执行3。
如果为树，则执行getTreeNode(hash, key)在树中寻找节点并且返回，否则遍历链表，找到键key、哈希地址一样的节点然后将对应的节点引用赋值给node，然后执行4，否则执行6。
如果节点node不为空(即查询到键key对应的节点)，且当matchValue为false的时候或者value也相等的时候，则执行5，否则执行6。
如果节点为树，则调用removeTreeNode(this, tab, movable)移除相应的节点。否则在链表中移除相应的节点，

返回null。

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) {
    // p 是待删除节点的前置节点
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //如果哈希表不为空，则根据hash值算出的index下 有节点的话。
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //node是待删除节点
        Node<K,V> node = null, e; K k; V v;
        //如果链表头的就是需要删除的节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;//将待删除节点引用赋给node
        else if ((e = p.next) != null) {//否则循环遍历 找到待删除节点，赋值给node
            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);
            }
        }
        //如果有待删除节点node，  且 matchValue为false，或者值也相等
        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)//如果node ==  p，说明是链表头是待删除节点
                tab[index] = node.next;
            else//否则待删除节点在表中间
                p.next = node.next;
            ++modCount;//修改modCount
            --size;//修改size
            afterNodeRemoval(node);//LinkedHashMap回调函数
            return node;
        }
    }
    return null;
}

containsKey方法

如果存在指定的键key，返回true，否则返回false。
containsKey方法调用的get调用的方法一样的方法，参考get方法的解析。

1
2
3

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

哈希表的初始化和加倍扩容resize方法

分析resize方法，我们就可以知道为什么哈希表的容量变化后，仍然能取到正确的值

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //如果哈希表是空的 则将旧容量置为0，否则置为旧哈希表的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //旧的哈希表的阈值
    int oldThr = threshold;
    //新的哈希表的容量和阈值 都置为0
    int newCap, newThr = 0;
    //如果旧的容量大于0 即不是第一次初始化 是扩容操作
    if (oldCap > 0) {
        //旧的容量是否大于2的30次幂方(容量的最大值)
        if (oldCap >= MAXIMUM_CAPACITY) {
            //阈值设置为Integer的最大值
            threshold = Integer.MAX_VALUE;
            //返回旧的哈希表(旧的哈希表已经到最大的容量了，不能继续扩容 所以返回)
            return oldTab;
        }
        //新的哈希表容量的=旧的容量<<1，即新的容量=旧的2倍，如果新的容量小于2的30次幂方(容量的最大值) 且 旧的容量大于等于默认的容量(16)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //新的哈希表的阈值=旧的哈希表的阈值<<1，既即新的阈值=旧的2倍 扩容table
            newThr = oldThr << 1; // double threshold
    }
    //第一次初始化，如果旧的阈值>0 即HashMap是以传入容量大小或者传入容量大小、负载因子的构造函数进行初始化的，阈值threshlod已经在构造函数初始化过了，所以阈值在这里大于0
    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);
    }
    //新的阈值=0，即执行的是上面的else if (oldThr > 0)(使用带参数的构造函数初始化)，是使用带参数的构造函数进行的初始化，并且计算出新的阈值
    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
                    //将旧的哈希表的节点全部重新定位，比如旧的哈希表容量是16，有一个值a放在数组下标为0上，现在新的哈希表容量是32，重新定位后值a就被重新定位到下标为32上，即新的哈希表的下标为32储存值a，简单来说就是 新的下标=旧的哈希表的下标+旧的哈希表的容量，正是因为这个节点的迁移，所以我们在hashMap put get操作的时候，在哈希表容量变化后仍让取到正确的值，但是也因为这个迁移操作，
                    会消耗很多资源，所以尽量在创建HashMap的时候就估计哈希表的容量，尽量不要让他加倍扩容。这里的迁移也都是运用的位运算，所以在初始化的时候，桶的数量必须是2
                    幂次方，才能保证位运算和取模运算结果一样。
                    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;
}

我们可以运行个例子，调试看看。

HashMap<String, Integer> map = new HashMap();
for (int i = 1; i <= 24; i ++) {
    map.put(String.valueOf(i), i);
}
for (int i = 25; i <= 80; i ++) {
    map.put(String.valueOf(i), i);
}

我们以无参构造函数(即哈希表容量默认是16，负载因子默认是0.75)new一个HashMap，然后调试看看

运行第一个for循环，看到11保存的下标为0，12保存的下标是1
在继续运行第二个for，发现下标为0的变成了44，下标为1的变成了45

那我们的11和12保存在哪了？可以发现11和12到了下标为32、33上，即当执行第二个for的时候哈希表发生了扩容，然后节点都迁移了，新的下标=旧的下标+旧的哈希表的容量

参考资料

Java HashMap工作原理及实现
 Map 综述（一）：彻头彻尾理解 HashMap

本文链接： http://ddnd.cn/2019/03/07/jdk1.8-hashmap/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

薛8Web Developer

个人简介。