咱们最先苍老的不是模样，而是不顾一切的闯劲。有时候，要敢于背上超出本人意料的包袱，真的致力后，你会发现自己要比设想的优良很多。

HashMap抵触的解决办法比拟考验一个开发者解决问题的能力。
下文给出HashMap抵触的解决办法以及原理剖析，无论是在面试问答或者理论应用中，应该都会有所帮忙

在Java编程语言中，最根本的构造就是两种，一种是数组，一种是模仿指针(援用)，所有的数据结构都能够用这两个根本构造结构，HashMap也一样。

当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：

HashMap<String,Object> m=new HashMap<String,Object>();   m.put("a", "rrr1");   m.put("b", "tt9");   m.put("c", "tt8");   m.put("d", "g7");   m.put("e", "d6");   m.put("f", "d4");   m.put("g", "d4");   m.put("h", "d3");   m.put("i", "d2");   m.put("j", "d1");   m.put("k", "1");   m.put("o", "2");   m.put("p", "3");   m.put("q", "4");   m.put("r", "5");   m.put("s", "6");   m.put("t", "7");   m.put("u", "8");   m.put("v", "9");

HashMap 采纳一种所谓的“Hash 算法”来决定每个元素的存储地位。当程序执行 map.put(String,Obect)办法 时，零碎将调用String的 hashCode() 办法失去其 hashCode 值——每个 Java 对象都有 hashCode() 办法，都可通过该办法取得它的 hashCode 值。失去这个对象的 hashCode 值之后，零碎会依据该 hashCode 值来决定该元素的存储地位。

源码如下:

public V put(K key, V value) {    if (key == null)        return putForNullKey(value);    int hash = hash(key.hashCode());    int i = indexFor(hash, table.length);    for (Entry<K, V> e = table[i]; e != null; e = e.next) {        Object k;        //判断以后确定的索引地位是否存在雷同hashcode和雷同key的元素，如果存在雷同的hashcode和雷同的key的元素，那么新值笼罩原来的旧值，并返回旧值。          //如果存在雷同的hashcode，那么他们确定的索引地位就雷同，这时判断他们的key是否雷同，如果不雷同，这时就是产生了hash抵触。          //Hash抵触后，那么HashMap的单个bucket里存储的不是一个 Entry，而是一个 Entry 链。          //零碎只能必须按程序遍历每个 Entry，直到找到想搜寻的 Entry 为止——如果恰好要搜寻的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），          //那零碎必须循环到最初能力找到该元素。          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {            V oldValue = e.value;            e.value = value;            return oldValue;        }    }    modCount++;    addEntry(hash, key, value, i);    return null;}

下面程序中用到了一个重要的外部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从下面程序中能够看出：当零碎决定存储 HashMap 中的 key-value 对时，齐全没有思考 Entry 中的 value，仅仅只是依据 key 来计算并决定每个 Entry 的存储地位。

这也阐明了后面的论断：咱们齐全能够把 Map 汇合中的 value 当成 key 的从属，当零碎决定了 key 的存储地位之后，value 随之保留在那里即可。HashMap程序通过我革新，我成心的结构出了hash抵触景象，因为HashMap的初始大小16，然而我在hashmap外面放了超过16个元素，并且我屏蔽了它的resize()办法。不让它去扩容。

这时HashMap的底层数组Entry[] table构造如下:

Hashmap外面的bucket呈现了单链表的模式，散列表要解决的一个问题就是散列值的抵触问题，通常是两种办法：链表法和凋谢地址法。

  • 链表法就是将雷同hash值的对象组织成一个链表放在hash值对应的槽位；
  • 凋谢地址法是通过一个探测算法，当某个槽位曾经被占据的状况下持续查找下一个能够应用的槽位。

java.util.HashMap采纳的链表法的形式，链表是单向链表。造成单链表的外围代码如下：

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

下面办法的代码很简略，但其中蕴含了一个设计：零碎总是将新增加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处曾经有了一个 Entry 对象，那新增加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象，也就是下面程序代码的 e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。

HashMap外面没有呈现hash抵触时，没有造成单链表时，hashmap查找元素很快,get()办法可能间接定位到元素，然而呈现单链表后，单个bucket 里存储的不是一个 Entry，而是一个 Entry 链，零碎只能必须按程序遍历每个 Entry，直到找到想搜寻的 Entry 为止——如果恰好要搜寻的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那零碎必须循环到最初能力找到该元素。

当创立 HashMap 时，有一个默认的负载因子（load factor），其默认值为 0.75，这是工夫和空间老本上一种折衷：增大负载因子能够缩小 Hash 表（就是那个 Entry 数组）所占用的内存空间，但会减少查问数据的工夫开销，而查问是最频繁的的操作（HashMap 的 get() 与 put() 办法都要用到查问）；减小负载因子会进步数据查问的性能，但会减少 Hash 表所占用的内存空间。

一、HashMap概述

HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并容许应用 null 值和 null 键。（除了不同步和容许应用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保障映射的程序，特地是它不保障该程序恒久不变。

值得注意的是HashMap不是线程平安的，如果想要线程平安的HashMap，能够通过Collections类的静态方法synchronizedMap取得线程平安的HashMap。
 Map map = Collections.synchronizedMap(new HashMap());

二、HashMap的数据结构

HashMap的底层次要是基于数组和链表来实现的，它之所以有相当快的查问速度次要是因为它是通过计算散列码来决定存储的地位。HashMap中次要是通过key的hashCode来计算hash值的，只有hashCode雷同，计算出来的hash值就一样。如果存储的对象对多了，就有可能不同的对象所算进去的hash值是雷同的，这就呈现了所谓的hash抵触。学过数据结构的同学都晓得，解决hash抵触的办法有很多，HashMap底层是通过链表来解决hash抵触的。

图中，紫色局部即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决抵触的，如果不同的key映射到了数组的同一地位处，就将其放入单链表中。

咱们看看HashMap中Entry类的代码：

/** Entry是单向链表。     * 它是 “HashMap链式存储法”对应的链表。     * 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数   **/static class Entry<K, V> implements Map.Entry<K, V> {    final K key;    V value;    // 指向下一个节点        Entry<K, V> next;    final int hash;    // 构造函数。        // 输出参数包含"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"        Entry(int h, K k, V v, Entry<K, V> n) {        value = v;        next = n;        key = k;        hash = h;    }    public final K getKey() {        return key;    }    public final V getValue() {        return value;    }    public final V setValue(V newValue) {        V oldValue = value;        value = newValue;        return oldValue;    }    // 判断两个Entry是否相等        // 若两个Entry的“key”和“value”都相等，则返回true。        // 否则，返回false        public final boolean equals(Object o) {        if (!(o instanceof Map.Entry))            return false;        Map.Entry e = (Map.Entry) o;        Object k1 = getKey();        Object k2 = e.getKey();        if (k1 == k2 || (k1 != null && k1.equals(k2))) {            Object v1 = getValue();            Object v2 = e.getValue();            if (v1 == v2 || (v1 != null && v1.equals(v2)))                return true;        }        return false;    }    // 实现hashCode()        public final int hashCode() {        return (key == null ? 0 : key.hashCode()) ^                (value == null ? 0 : value.hashCode());    }    public final String toString() {        return getKey() + "=" + getValue();    }    // 当向HashMap中增加元素时，绘调用recordAccess()。        // 这里不做任何解决        void recordAccess(HashMap<K, V> m) {    }    // 当从HashMap中删除元素时，绘调用recordRemoval()。        // 这里不做任何解决        void recordRemoval(HashMap<K, V> m) {    }}

HashMap其实就是一个Entry数组，Entry对象中蕴含了键和值，其中next也是一个Entry对象，它就是用来解决hash抵触的，造成一个链表。

三、HashMap源码剖析

1、要害属性

先看看HashMap类中的一些要害属性：

transient Entry[] table;//存储元素的实体数组    transient int size;//寄存元素的个数    int threshold; //临界值   当理论大小超过临界值时，会进行扩容threshold = 加载因子*容量    final float loadFactor; //加载因子    transient int modCount;//被批改的次数

其中loadFactor加载因子是示意Hsah表中元素的填满的水平.

若:加载因子越大,填满的元素越多,益处是,空间利用率高了,但:抵触的机会加大了.链表长度会越来越长,查找效率升高。反之,加载因子越小,填满的元素越少,益处是:抵触的机会减小了,但:空间节约多了.表中的数据将过于稠密（很多空间还没用，就开始扩容了）

抵触的机会越大,则查找的老本越高.

因而,必须在 "抵触的机会"与"空间利用率"之间寻找一种均衡与折衷. 这种均衡与折衷实质上是数据结构中有名的"时-空"矛盾的均衡与折衷.

如果机器内存足够，并且想要进步查问速度的话能够将加载因子设置小一点；相同如果机器内存缓和，并且对查问速度没有什么要求的话能够将加载因子设置大一点。不过个别咱们都不必去设置它，让它取默认值0.75就好了。

2、构造方法

上面看看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);    // Find a power of 2 >= initialCapacity    int capacity = 1;   //初始容量    while (capacity < initialCapacity)   //确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂        capacity <<= 1;    this.loadFactor = loadFactor;    threshold = (int) (capacity * loadFactor);    table = new Entry[capacity];    init();}public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR;    threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);    table = new Entry[DEFAULT_INITIAL_CAPACITY];    init();}

咱们能够看到在结构HashMap的时候如果咱们指定了加载因子和初始容量的话就调用第一个构造方法，否则的话就是用默认的。默认初始容量为16，默认加载因子为0.75。咱们能够看到下面代码中13-15行，这段代码的作用是确保容量为2的n次幂，使capacity为大于initialCapacity的最小的2的n次幂，至于为什么要把容量设置为2的n次幂，咱们等下再看。

重点剖析下HashMap中用的最多的两个办法put和get

3、存储数据

上面看看HashMap存储数据的过程是怎么的，首先看看HashMap的put办法：

public V put(K key, V value) {    // 若“key为null”，则将该键值对增加到table[0]中。    if (key == null)        return putForNullKey(value);    // 若“key不为null”，则计算该key的哈希值，而后将其增加到该哈希值对应的链表中。    int hash = hash(key.hashCode());    //搜寻指定hash值在对应table中的索引    int i = indexFor(hash, table.length);    // 循环遍历Entry数组,若“该key”对应的键值对曾经存在，则用新的value取代旧的value。而后退出！    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))) { //如果key雷同则笼罩并返回旧值            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    //批改次数+1    modCount++;    //将key-value增加到table[i]处    addEntry(hash, key, value, i);    return null;}

下面程序中用到了一个重要的外部接口：Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。从下面程序中能够看出：当零碎决定存储 HashMap 中的 key-value 对时，齐全没有思考 Entry 中的 value，仅仅只是依据 key 来计算并决定每个 Entry 的存储地位。

这也阐明了后面的论断：咱们齐全能够把 Map 汇合中的 value 当成 key 的从属，当零碎决定了 key 的存储地位之后，value 随之保留在那里即可。

咱们缓缓的来剖析这个函数，第2和3行的作用就是解决key值为null的状况，咱们看看putForNullKey(value)办法：

private V putForNullKey(V value) {    for (Entry<K, V> e = table[0]; e != null; e = e.next) {        if (e.key == null) {   //如果有key为null的对象存在，则笼罩掉            V oldValue = e.value;            e.value = value;            e.recordAccess(this);            return oldValue;        }    }    modCount++;    addEntry(0, null, value, 0); //如果键为null的话，则hash值为0    return null;}

留神：如果key为null的话，hash值为0，对象存储在数组中索引为0的地位。即table[0]

咱们再回去看看put办法中第4行，它是通过key的hashCode值计算hash码，上面是计算hash码的函数：

//计算hash值的办法 通过键的hashCode来计算static int hash(int h) {    // 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);}

失去hash码之后就会通过hash码去计算出应该存储在数组中的索引，计算索引的函数如下：

static int indexFor(int h, int length) { //依据hash值和数组长度算出索引值    return h & (length - 1);  //这里不能轻易算取，用hash&(length-1)是有起因的，这样能够确保算进去的索引是在数组大小范畴内，不会超出}

这个咱们要重点说下，咱们个别对哈希表的散列很天然地会想到用hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种办法根本能保障元素在哈希表中散列的比拟平均，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的办法来代替取模，同样实现了平均的散列，但效率要高很多，这也是HashMap对Hashtable的一个改良。

接下来，咱们剖析下为什么哈希表的容量肯定要是2的整数次幂。首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保障了散列的平均，同时也晋升了效率；其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最初一位是1，这样便保障了h&(length-1)的最初一位可能为0，也可能为1（这取决于h的值），即与后的后果可能为偶数，也可能为奇数，这样便能够保障散列的平均性，而如果length为奇数的话，很显著length-1为偶数，它的最初一位是0，这样h&(length-1)的最初一位必定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标地位上，这便节约了近一半的空间，因而，length取2的整数次幂，是为了使不同hash值产生碰撞的概率较小，这样就能使元素在哈希表中平均地散列。

这看上去很简略，其实比拟有玄机的，咱们举个例子来阐明：

假如数组长度别离为15和16，优化后的hash码别离为8和9，那么&运算后的后果如下：

 h & (table.length-1)   hash        table.length-1   8 & (15-1)：            0100    &   1110            =       0100   9 & (15-1)：            0101    &   1110            =       0100   -----------------------------------------------------------------------------------------------------------------------   8 & (16-1)：            0100    &   1111            =       0100   9 & (16-1)：            0101    &   1111            =       0101

从下面的例子中能够看出：当它们和15-1（1110）“与”的时候，产生了雷同的后果，也就是说它们会定位到数组中的同一个地位下来，这就产生了碰撞，8和9会被放到数组中的同一个地位上造成链表，那么查问的时候就须要遍历这个链 表，失去8或者9，这样就升高了查问的效率。同时，咱们也能够发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么 最初一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个地位永远都不能寄存元素了，空间节约相当大，更糟的是这种状况中，数组能够应用的地位比数组长度小了很多，这意味着进一步减少了碰撞的几率，减慢了查问的效率！而当数组长度为16时，即为2的n次方时，2n-1失去的二进制数的每个位上的值都为1，这使得在低位上&时，失去的和原hash的低位雷同，加之hash(int h)办法对key的hashCode的进一步优化，退出了高位计算，就使得只有雷同的hash值的两个值才会被放到数组中的同一个地位上造成链表。

所以说，当数组长度为2的n次幂的时候，不同的key算得得index雷同的几率较小，那么数据在数组上散布就比拟平均，也就是说碰撞的几率小，绝对的，查问的时候就不必遍历某个地位上的链表，这样查问效率也就较高了。

依据下面 put 办法的源代码能够看出，当程序试图将一个key-value对放入HashMap中时，程序首先依据该 key 的 hashCode() 返回值决定该 Entry 的存储地位：如果两个 Entry 的 key 的 hashCode() 返回值雷同，那它们的存储地位雷同。如果这两个 Entry 的 key 通过 equals 比拟返回 true，新增加 Entry 的 value 将笼罩汇合中原有 Entry 的 value，但key不会笼罩。如果这两个 Entry 的 key 通过 equals 比拟返回 false，新增加的 Entry 将与汇合中原有 Entry 造成 Entry 链，而且新增加的 Entry 位于 Entry 链的头部——具体阐明持续看 addEntry() 办法的阐明。

void addEntry(int hash, K key, V value, int bucketIndex) {    Entry<K, V> e = table[bucketIndex]; //如果要退出的地位有值，将该地位原先的值设置为新entry的next,也就是新entry链表的下一个节点    table[bucketIndex] = new Entry<>(hash, key, value, e);    if (size++ >= threshold) //如果大于临界值就扩容        resize(2 * table.length); //以2的倍数扩容}

参数bucketIndex就是indexFor函数计算出来的索引值，第2行代码是获得数组中索引为bucketIndex的Entry对象，第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的地位，并且将该地位原先的对象设置为新对象的next形成链表。

第4行和第5行就是判断put后size是否达到了临界值threshold，如果达到了临界值就要进行扩容，HashMap扩容是扩为原来的两倍。

4、调整大小

resize()办法如下：

从新调整HashMap的大小，newCapacity是调整后的单位

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);//用来将原先table的元素全副移到newTable外面    table = newTable;  //再将newTable赋值给table    threshold = (int) (newCapacity * loadFactor);//从新计算临界值}

新建了一个HashMap的底层数组，下面代码中第10行为调用transfer办法，将HashMap的全副元素增加到新的HashMap中,并从新计算元素在新的数组中的索引地位

当HashMap中的元素越来越多的时候，hash抵触的几率也就越来越高，因为数组的长度是固定的。所以为了进步查问的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会呈现在ArrayList中，这是一个罕用的操作，而在HashMap数组扩容之后，最耗费性能的点就呈现了：原数组中的数据必须从新计算其在新数组中的地位，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小_loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。__也就是说，默认状况下，数组大小为16，那么当HashMap中元素个数超过16_0.75=12的时候，就把数组的大小扩大为 2*16=32，即扩充一倍，而后从新计算每个元素在数组中的地位，扩容是须要进行数组复制的，复制数组是十分耗费性能的操作，所以如果咱们曾经预知HashMap中元素的个数，那么预设元素的个数可能无效的进步HashMap的性能。

5、数据读取

public V get(Object key) {    if (key == null)        return getForNullKey();    int hash = hash(key.hashCode());    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.equals(k)))            return e.value;    }    return null;}

有了下面存储时的hash算法作为根底，了解起来这段代码就很容易了。从下面的源代码中能够看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应地位的某一元素，而后通过key的equals办法在对应地位的链表中找到须要的元素。

6、HashMap的性能参数：

HashMap 蕴含如下几个结构器：

  • HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。
  • HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创立一个 HashMap。
    HashMap的根底结构器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。
  • initialCapacity：HashMap的最大容量，即为底层数组的长度。
  • loadFactor：负载因子loadFactor定义为：散列表的理论元素数目(n) 散列表的容量(m)。

负载因子掂量的是一个散列表的空间的应用水平，负载因子越大示意散列表的装填水平越高，反之愈小。对于应用链表法的散列表来说，查找一个元素的均匀工夫是O(1+a)，因而如果负载因子越大，对空间的利用更充沛，然而结果是查找效率的升高；如果负载因子太小，那么散列表的数据将过于稠密，对空间造成重大节约。

HashMap的实现中，通过threshold字段来判断HashMap的最大容量：

threshold = (int)(capacity * loadFactor);  

联合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下容许的最大元素数目，超过这个数目就从新resize，以升高理论的负载因子。默认的的负载因子0.75是对空间和工夫效率的一个均衡抉择。当容量超出此最大容量时，resize后的HashMap容量是容量的两倍。