HashMap 深度解读

HashMap 解读

在面试的过程中,面试官经常会向面试者提问关于 HashMap 的问题,今天我将在这篇文章中仔细介绍一下 HashMap.

jdk7 中的 HashMap

介绍一下 HashMap 及其 put 和 set 方法实现

HashMap 是由数组加上链表的数据结构书写的,它使用 key-value 键值对形式存储数据,每一个键值对也叫做 Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是 HashMap 的主干。HashMap 数组每一个元素的初始值都是 Null。

下面是几个比较重要的参数

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //数组的默认长度,16
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的加载因子 0.75
static final int MAXIMUM_CAPACITY = 1 << 30;//数组的最大长度 2 的 30 次方(1073741824)
static final Entry[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//table' 用来存放数据的位置
transient int size; // 存放的键值对的数量大小,Entry 的数量
int threshold;//桶(bucket)的大小，可在初始化时显式指定
final float loadFactor;//加载因子，可在初始化时显式指定。
transient int modCount;//修改的次数,用于 fail-fast 机制

这个数组的默认长度为 16,默认加载因子为 0.75,数组里面的每一个值初始化的时候默认为 null.当桶中总的键值对(Entry)的数量达到 capacity * loadFactor 的大小时,数组就会扩容,第一次扩容发生在数组中 Entry 数量为 16*0.75f=12 时.每次扩容都会使得数组的容量变为原来的两倍.这两个参数在创建 HashMap 对象的时候都可以指定,但我们一般不指定.

对于 HashMap 我们最常用的两个方法就是put和get

put

jdk7 中的源码如下

    public V put(K key, V value) {
	//如果此时的table仍旧为初始化时的EMPTY_TABLE(空数组)的话,就对其进行初始化扩容
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
	//如果想要存放的数据的key值为空的话,那么就调用putForNullKey方法.
	//putForNullKey会覆盖掉原先的null值对应的Entry的value(如果存在的话)
        if (key == null)
            return putForNullKey(value);
	//对于非空的key存取方法如下
	//1.计算hash值
        int hash = hash(key);
	//2.计算该hash值在table中的位置
        int i = indexFor(hash, table.length);
	//3.判断此位置中是否有Entry存在,使用equals方法判断新插入的键是否等于原有的键, 
	//相同的话就覆盖原有Entry的值,不同的话就插入链表的最上方
	//并使新插入Entry指向原先的Entry
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
		//如果前面return的话,也就不会来到这里调用addEntry方法了
        addEntry(hash, key, value, i);
        return null;
    }
​

上面代码的注释看懂了吗?没看懂也没关系,我再用画图的方式解释一下.
当我们调用 put 方法时,会首先判断插入数据的键是否为空,如果为空的话就调用 putForNullKey 方法,在 HashMap 中只能够存放一个空键的数据,且这个数据一定存放在 table[0] 的位置.
如果插入的数据键不为空的话,那么就会计算键(key)对应的 hash 值并算出该 hash 值在 table 中的位置,如果此时该位置没有数据的话,那么就 addEntry,为此键值对创建一个 Entry 并插入 table 中.

但是此时如果此时的位置已经有 Entry 的话,就会再次判断,如果 hash 相同并且 Entry 的话就将原先的值取而代之,而键不做改变.如下图所示

如果 hash 值不同的话,就会将数据插入新的原先的 Entry 位置,并指向于原先的 Entry.在 jdk7 的 HashMap 中,同一个位置中后插入的数据一定在先插入数据的前面,因为 HashMap 的代码书写者认为后插入的数据比先插入的数据更有可能被使用.
注:在下图中省去了一个指针没有画出来,实际上在 Entry 这个内部类的定义中有一个指针,代码如下

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//此处定义了一个指针
        int hash;
​

get

jdk7 中的源码如下

public V get(Object key) {
	
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }

​

get 方法首先进行判断 key 是否为 null,如果对应的键为 null 的话,就调用 getForNullKey 查询方法,直接去 table[0]的位置查找有无键为 null 的 Entry.如果键不为零的话那么就调用 getEntry 方法,getEntry 的源码如下:

 final Entry<K,V> getEntry(Object key) {
	//首先判断Entry的数量是否为零,为零就不用查找了,直接返回null
        if (size == 0) {
            return null;
        }
	//计算hash值并找到该hash值在table中对应的位置,之后顺着链表一个个的比较hash值
	//hash值一致的话再比较键是否一致,一致则取出数据并返回
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
	//如果查找不到此key则返回null
        return null;
    }

​

下图是我在网上找的关于 jdk7 中 HashMap 的结构图,希望你通过这个图能够自行回忆出 HashMap 的结构和实现方法.

到了这里 jdk7 中 HashMap 的 get 和 set 方法基本就就讲完了,但是不知道读者们有没有发现 HashMap 在数据插入和读取时存在的一个问题,当 HashMap 中同一个桶中的键值对越多的时候,就越有可能发生 hash 冲突问题,每次对 table 里同一个桶的 Entry 的 Hash 值进行比较的话,时间复杂度为 O(n),大量的 hash 冲突会使得数据的读写性能下降,这个问题在 jdk8 中作出了优化,你继续读下去就会得到答案.

jdk7 和 jdk8 中 HashMap 实现的不同之处

jdk7 中使用 Entry 来代表每个 HashMap 中的数据节点，Java8 中使用 Node，基本没有区别，都是 key，value，hash 和 next 这四个属性，不过，Node 只能用于链表的情况，红黑树的情况需要使用 TreeNode。下面的图片是我在网上找的关于 jdk8 中 HashMap 的实现.

jdk8 中的 HashMap 代码个人认为易读性不够好,博主水平有限,希望大家轻喷.
那么现在就开始解读代码吧,首先我觉得需要进行解释的是下面两个字段

static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;

当数组中某一个位置中所包含键值对的数目大于 TREEIFY_THRESHOLD 时,比如说我们在 table[2]的位置插入第九个元素的时候,这个桶的数据结构就会从链表向红黑树转换,此时如果在数组此位置进行数据的存取的话,那么时间复杂度就变为了 O(logn),较之前的 O(n)得到了一定的速度提升.
而当 HashMap 进行 resize 的时候,每一个桶中的键值对的数目势必要下降,如果这个桶中,也就是数组的某个位置它所对应的结点(键值对)数目小于 UNTREEIFY_THRESHOLD 时,数据结构就会又变回链表结构.

put

下面我们来看一下 put 的源码

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
// 第三个参数 onlyIfAbsent 如果是 true的话，那么只有在不存在这个 key 时才会进行 put 操作
//我们传递过来的值是false
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 第一次 put 值的时候，会触发下面的 resize()，类似 jdk7 的第一次 put操作 也要初始化数组长度
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 找到具体的数组下标，如果这个位置上没有node,那么就直接创建
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
 
    else {// 说明数组该位置有数据
        Node<K,V> e; K k;
        // 首先，判断该位置的第一个键值对(node)和我们要插入的数据，key 是不是"相等"，
		  //
        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 {
            // 到这里else中来，说明数组该位置上是一个链表
            for (int binCount = 0; ; ++binCount) {
                // 插入到链表的最后面(Jdk7 是插入到链表的最前面)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // TREEIFY_THRESHOLD 为 8，所以，如果新插入的值是链表中的第 9 个
                    // 会触发下面的 treeifyBin，也就是将链表转换为红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果在该链表中找到了"相等"的 key(== 或 equals)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 此时 break，那么 e 为链表中[与要插入的新值的 key "相等"]的 node
                    break;
                p = e;
            }
        }
        // e!=null 说明存在旧值的key与要插入的key"相等"
        // 和jdk7中一样,保持数据的key不变,将值覆盖为新插入的值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;//修改次数+1
    // 如果 HashMap 由于新插入这个值导致 size 已经超过了阈值，需要进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;

​

resize

在 jdk7 代码的解说中,我并没有详细介绍 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)
            // 将阈值(threshold)扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) 
        newCap = oldThr;
    else {// 对应第一次 put 的时候对数据进行初始化
        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;
 
    // 用新的数组大小初始化新的数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // 如果是初始化数组，到这里就结束了，返回 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 { 
                    // 这块是处理链表的情况，
                    // 需要将此链表拆成两个链表，放到新的数组中，并且保留原来的先后顺序
                    // loHead、loTail 对应一条链表，hiHead、hiTail 对应另一条链表，代码还是比较简单的
                    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;
                        // 第二条链表的新的位置是 j + oldCap
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;

​

get

对于 get 方法,此处不做详细介绍,主要要读者们记住的就是,在 get 操作的时候,会判断是否是采用红黑树存储键值对数据,我们根据数组元素中，第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。两者采用的读取方式不同。源码附上:

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

关于 HashMap 你必须要知道的那些事

HashMap 是线程安全的吗

答:HashMap 不是线程安全的,HashMap 在设计的时候就是为了单线程而服务的,如果你想在多线程中使用 HashMap 的话,可以考虑使用 ConcurrentHashMap 或者 HashTable.

HashMap 在多线程下面可能出现的问题

之前已经说了 HashMap 并非是线程安全的,如果你硬要在多线程的情况下使用 HashMap,可能出现的问题就是 CPU 占用率达到百分之百,这个问题我将会专门写一个博客.欢迎关注.

如果两个键值对键的 hashCode 相同的话,那么在数据的 put 和 get 时会怎样去做

当出现 hashCode 相同的情况时,那么 hash 值也一定相同,这两个键值对所处的数组位置也就是相同的,put 时调用 equals 方法比较是否有键和新插入的键一致,如果有的话,就覆盖原先键值对的值,没有的话就正常将数据插入.在 get 时同理,仅仅是 hash 值相同还不够,必须要比较键是否是一样的.

下面两个问题留给读者自己思考

HashMap 在 jdk7 和 jdk8 的差异

为什么重写 equals 方法就必须要重写 hashCode 方法

这篇博客就到这里结束啦,如果你有任何的疑问或者给我的建议的话,欢迎在底下进行留言.这篇博客似乎写的过于长了,第一次写博客,能力有限,好好加油吧.