转载

深度解析HashMap

概述

HashMap对于使用Java的小伙伴们来说最熟悉不过，每天都在使用它。这次主要是分析下HashMap的工作原理，为什么我会拿这个东西出来分析，主要是最近面试的小伙伴们，中被人问起HashMap，HashMap涉及的知识远远不止put和get那么简单。

为什么叫做HashMap？内部是怎样实现的呢？使用的时候大多数都是用String作为它的key呢？下面就让我们来了解HashMap，并给你详细解释这些问题。

HashMap名字的由来

其实HashMap的由来是基于Hasing技术(Hasing),Hasing就是将很大的字符串或者任何对象转换成一个用来代表它们的很小的值，这些更短的值就可以很方便的用来方便索引、加快搜索。

什么是HashMap

HashMap是一个用于存储Key-Value键值对的集合，你可以用一个”key”去存储数据。当你想获得数据的时候，你可以通过”key”去得到数据，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。

HashMap作为一种数据结构，像数组和链表一样用于常规的增删改查，在存数据的时候(put)并不是随便乱放，而是会先进行一次分配索引（可以理解为“分类”）的操作再存储，一旦分配索引存储之后，下次取(get)的时候就可以大大缩短查找的时间。我们知道数组在执行查、改的效率很高，而增、删(不是尾部)的效率低，链表相反，HashMap则是把这两者结合起来，看下HashMap的数据结构

先介绍一下HashMap的变量

size ,就是HashMap的存储大小。 threshold 是HashMap临界值，也叫阀值，如果HashMap到达了临界值，需要重新分配大小。 loadFactor 是负载因子，默认为75%。阀值 = 当前数组长度✖负载因子。 modCount 指的是HashMap被修改或者删除的次数总数。

HashMap的存储结构

深度解析HashMap

Entry分散存储在一个Entry类型的数组table， table里的每一个数据都是一个Entry对象。Y轴方向代表的就是数组，X轴方向就是链表的存储方式。

table里面存储的Entry类型，Entry类里包含了hashcode变量，key,value 和另外一个Entry对象。因为这是一个链表结构。通过我找到你，你再找到他。不过这里的Entry并不是LinkedList，它是单独为HashMap服务的一个内部单链表结构的类。

数组的特点是特点是查询快，时间复杂度是O(1)，插入和删除的操作比较慢，时间复杂度是O(n)。而链表的存储方式是非连续的，大小不固定，特点与数组相反，插入和删除快，查询速度慢。HashMap引用他们，选取了他们的有段，可以说是在查询，插入和删除的操作，都会有些提速。

HashMap的基本原理

1、首先判断Key是否为Null，如果为null，直接查找Enrty[0]，如果不是Null，先计算Key的HashCode，然后经过二次Hash，得到Hash值。

2、根据Hash值，对Entry[]的长度length求余，得到的就是Entry数组的index。

3、根据对应的索引找到对应的数组，就是找到了其所在的链表，然后按照链表的操作对Value进行插入、删除和查询操作。

Hash碰撞

hash 方法

我们都知道在Java中每个对象都有一个hashcode()方法用来返回该对象的 hash值。HashMap先对hashCode进行hash操作，然后再通过hash值进一步计算下标。

final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
public final int hashCode() {
    return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}

HashMap是怎么通过Hash查找数组的索引的呢，调用indexFor，其中h是hash值，length是数组的长度，这个按位与的算法其实就是h%length求余。

/**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

其中h是hash值，length是数组的长度，这个按位与的算法其实就是h%length求余。

一般什么情况下利用该算法，典型的分组。例如怎么将100个数分组16组中，就是这个意思。应用非常广泛。

static int indexFor(int h, int length) {
        return h & (length-1);
    }

举个例子

int h=15,length=16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0001111", 2) & Integer.parseInt("0001111", 2));
        h=15+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0011111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("0111111", 2) & Integer.parseInt("0001111", 2));
        h=15+16+16+16;
        System.out.println(h & (length-1));
        System.out.println(Integer.parseInt("1111111", 2) & Integer.parseInt("0001111", 2));

在做按位与的时候，始终是 低位在做计算，高位不参与计算 ，因为高位都是0。这样导致的结果就是只要是低位是一样的，高位无论是什么，最后结果是一样的， 如果这样依赖，hash碰撞始终在一个数组上，导致这个数组开始的链表无限长，那么在查询的时候就速度很慢， 又怎么算得上高性能的啊。所以hashmap必须解决这样的问题，尽量让key尽可能均匀的分配到数组上去。避免造成Hash堆积。

调用put方法时，尽管我们设法避免碰撞以提高HashMap的性能，还是可能发生碰撞。据说碰撞率还挺高，平均加载率到10%时就会开始碰撞。

源码分析

HashMap初始化

默认情况下，大多数人都调用 HashMap hashMap = new HashMap(); 来初始化的，我们在这分析newHashMap（int initialCapacity, float loadFactor）的构造函数。

我们都知道在Java中每个对象都有一个hashcode()方法用来返回该对象的 hash值。HashMap先对hashCode进行hash操作，然后再通过hash值进一步计算下标。

代码如下：

public HashMap(int initialCapacity, float loadFactor) {
　// initialCapacity代表初始化HashMap的容量，它的最大容量是MAXIMUM_CAPACITY = 1 << 30。
　// loadFactor代表它的负载因子，默认是是DEFAULT_LOAD_FACTOR=0.75，用来计算threshold临界值的。    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);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and the default load factor (0.75).
 *
 * @param  initialCapacity the initial capacity.
 * @throws IllegalArgumentException if the initial capacity is negative.
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

由上面的代码可以看出，初始化的时候需要知道初始化的容量大小，因为在后面要通过按位与的Hash算法计算Entry数组的索引，那么要求Entry的数组长度是2的N次方。

put操作

HashMap怎么存储一个对象呢，代码如下：

public V put(K key, V value) {
        //数组为空时创建数组
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //①key为空单独对待
        if (key == null)
            return putForNullKey(value);
        //②根据key计算hash值
        int hash = hash(key);
        //②根据hash值和当前数组的长度计算在数组中的索引
        int i = indexFor(hash, table.length);
        //遍历整条链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //③hash值和key值都相同的情况，替换之前的值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                //返回被替换的值
                return oldValue;
            }
        }

        modCount++;
        //③如果没有找到key的hash相同的节点,直接存值或发生hash碰撞都走这
        addEntry(hash, key, value, i);
        return null;
    }

从代码中可以看出，步骤如下：

1.首先会判断可以是否为null，如果是null，就调用pullForNullKey（value）处理。代码如下：

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

如果key为null的值，默认就存储到table[0]开头的链表了。然后遍历table[0]的链表的每个节点Entry，如果发现其中存在节点Entry的key为null，就替换新的value，然后返回旧的value，如果没发现key等于null的节点Entry，就增加新的节点。

2. 计算key的hashcode，再用计算的结果二次hash，通过indexFor(hash, table.length);找到Entry数组的索引i。

(3) 然后遍历以table[i]为头节点的链表，如果发现有节点的hash，key都相同的节点时，就替换为新的value，然后返回旧的value。

如果没有找到key的hash相同的节点，就增加新的节点addEntry(),代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
        //判断数组容量是否足够，不足够扩容
            resize(2 * table.length);
    }

（4）如果HashMap大小超过临界值，就要重新设置大小，扩容，稍后讲解。

附上一张流程图，这个图是从别的博主哪里copy的，感觉画的不错。

深度解析HashMap

get操作

我们通过hashMap.get(K key) 来获取存入的值，key的取值很简单了。我们通过数组的index直接找到Entry，然后再遍历Entry，当hashcode和key都一样就是我们当初存入的值啦。

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

        return null == entry ? null : entry.getValue();
    }

调用getEntry(key)拿到entry ,然后返回entry的value,来看getEntry(key)方法

final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

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

相比put，get操作就没这么多套路，只需要根据key值计算hash值，和数组长度取模，然后就可以找到在数组中的位置(key为空同样单独操作)，接着就是Entry遍历，hash相等的情况下，如果key相等就知道了我们想要的值。

再get方法中有null的判断，null取hash值总是0,再getNullKey(K key)方法中，也是按照遍历方法来查找的。

modCount的作用

众所周知，HashMap不是线程安全的，但在某些容错能力较好的应用中，如果你不想仅仅因为1%的可能性而去承受hashTable的同步开销，HashMap使用了Fail-Fast机制来处理这个问题，你会发现modCount在源码中是这样声明的。

reSize

调用put方法时，当HashMap的大小超过临界值的时候，就需要扩充HashMap的容量了。代码如下：

void resize(int newCapacity) { //传入新的容量
        //获取旧数组的引用
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        //极端情况，当前键值对数量已经达到最大
        if (oldCapacity == MAXIMUM_CAPACITY) {
            //修改阀值为最大直接返回
            threshold = Integer.MAX_VALUE;
            return;
        }
        //步骤①根据容量创建新的数组
        Entry[] newTable = new Entry[newCapacity];
        //步骤②将键值对转移到新的数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        //步骤③将新数组的引用赋给table
        table = newTable;
        //步骤④修改阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

如果大小超过最大容量就返回。否则就new 一个新的Entry数组，长度为旧的Entry数组长度的两倍。然后将旧的Entry[]复制到新的Entry[].代码如下：

void transfer(Entry[] newTable, boolean rehash) {
        //获取新数组的长度
        int newCapacity = newTable.length;
        //遍历旧数组中的键值对
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //计算在新表中的索引，并到新数组中
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

到这里相信你对HashMap内部已经非常清楚了，如果本篇文章对你有帮助记得点赞和评论，或者关注我，我会继续更新文章，感谢支持！

原文 https://juejin.im/post/5aca15785188255cb32e6991

正文到此结束