一、什么是哈希表

在讨论哈希表之前，我们先大概了解下其他数据结构的新增、查找等基础操作的执行性能。

数组：

采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：

对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

二叉树：

对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

哈希表：

相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。

我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。

比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：
插入过程如下图所示：

查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

哈希冲突

然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀，但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种：开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法。而HashMap即是采用了链地址法，也就是数组+链表的方式。

二、HashMap的实现原理

HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）

//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。至于为什么这么做，后面会有详细分析。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

Entry是HashMap中的一个静态内部类。代码如下

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        } 
        

所以，HashMap的总体结构如下：

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。

其他几个重要字段：

/**实际存储的key-value键值对的个数*/
transient int size;

/**阈值，当table == {}时，该值为初始容量（初始容量默认为16）；
当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。
HashMap在进行扩容时需要参考threshold，后面会详细谈到*/
int threshold;

/**负载因子，代表了table的填充度有多少，默认是0.75
加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
*/
final float loadFactor;

/**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，
如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
需要抛出异常ConcurrentModificationException*/
transient int modCount;

HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值，initialCapacity默认值为16，loadFactory默认值为0.75

我们看下其中一个：

public HashMap(int initialCapacity, float loadFactor) {
　　　　　//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
        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;
        threshold = initialCapacity;
　　　　　
        init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}

从上面这段代码我们可以看出，在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组，我们来看看put操作的实现

put方法

public V put(K key, V value) {
	 //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
	 //此时threshold为initialCapacity 默认是1<<4(2^4=16)
	 if (table == EMPTY_TABLE) {
	     inflateTable(threshold);
	 }
	//如果key为null，存储位置为table[0]或table[0]的冲突链上
	 if (key == null)
	     return putForNullKey(value);
	 int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
	 int i = indexFor(hash, table.length);//获取在table中的实际位置
	 for (Entry<K,V> e = table[i]; e != null; e = e.next) {
	 	 //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
	     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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
	 addEntry(hash, key, value, i);//新增一个entry
	 return null;
}

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

private void inflateTable(int toSize) {
	int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
	/**此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，
	capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1 */
	threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
	table = new Entry[capacity];
	initHashSeedAsNeeded(capacity);
}

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.

private static int roundUpToPowerOf2(int number) {
	// assert number >= 0 : "number must be non-negative";
	return number >= MAXIMUM_CAPACITY
	        ? MAXIMUM_CAPACITY
	        : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}

hash函数：

/**这是一个神奇的函数，用了很多的异或，移位等运算
对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
final int hash(Object k) {
	int h = hashSeed;
	if (0 != h && k instanceof String) {
	    return sun.misc.Hashing.stringHash32((String) k);
	}
	
	h ^= k.hashCode();
	
	h ^= (h >>> 20) ^ (h >>> 12);
	return h ^ (h >>> 7) ^ (h >>> 4);
}

以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置

/**
  * 返回数组下标
  */
static int indexFor(int h, int length) {
    return h & (length-1);
}

h&（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18，转换成二进制计算为index=2(18 &15=2)。位运算对计算机来说，性能更高一些（HashMap中有大量位运算）

所以最终存储位置的确定流程是这样的：

继续看addEntry的实现：

void addEntry(int hash, K key, V value, int bucketIndex) {
	if ((size >= threshold) && (null != table[bucketIndex])) {
		resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
		hash = (null != key) ? hash(key) : 0;
		bucketIndex = indexFor(hash, table.length);
	}
	
	createEntry(hash, key, value, bucketIndex);
}

通过以上代码能够得知，当发生哈希冲突并且size大于阈值threshold的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。

为什么hashMap的容量是2的幂次

我们来继续看上面提到的resize方法：

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 = newTable;
	threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1)，index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法：

void transfer(Entry[] newTable, boolean rehash) {
	int newCapacity = newTable.length;
	//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
	 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);
	         //将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
	         e.next = newTable[i];
	         newTable[i] = e;
	         e = next;
	     }
	 }
}

这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过对key值的hashcode进行hash运算后，再通过和 length-1进行位运算得到最终数组索引位置。

HashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。

从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那位为0，则新的数组索引=老数组索引，如果h对应的最左边的那位为1，则新的数组索引=老数组索引+旧的数组容量，避免了新的数组索引的计算量。

第二，数组长度保持2的次幂，这样length-1的低位都为1，会使获得的数组索引index更加均匀，减少碰撞的几率。

如上图，如果容量是2的次幂，那么length-1的低位全为1，要得到index=21这个存储位置，h的低位只有这一种组合。

如果容量不是2的次幂，那么length-1的低位也就不全为1，如下图，此时，这两个h值都会使得index=21

同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。

即，如果容量不是2的次幂，就会造成分布不均匀了，增加了碰撞的几率，减慢了查询的效率，造成空间的浪费。

get方法

public V get(Object key) {
	//如果key为null,则直接去table[0]处去检索即可。
	if (key == null)
	   return getForNullKey();
	Entry<K,V> entry = getEntry(key);
	return null == entry ? null : entry.getValue();
}

get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法：

final Entry<K,V> getEntry(Object key) {
            
	if (size == 0) {
	    return null;
	}
	//通过key的hashcode值计算hash值
	int hash = (key == null) ? 0 : hash(key);
	//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
	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;
}    

可以看出，get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。

HashMap增加新元素的主要步骤

HashMap 是如何使用 hash 函数的

首先，我们来看一下在 HashMap 中，最常用的 put() 和 get() 是怎么使用 hash() 的。以下源码均为 jdk7。

// put() 
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

// get()
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;
}

我们不难观察到，HashMap 中都是先使用 hash 函数 获取一个 hash 值，然后利用得到的 hash 值和容器长度计算存放位置（indexFor() 方法）。接下来我们就详细看一下 hash() 和 indexFor() 两个方法。

static int hash(int h) {
    return h ^ (h >>> 7) ^ (h >>> 4);
}

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

通过put() 和 get() 方法，我们可以知道，hash() 方法中的参数 h 就是 key 的 hashCode，hash() 方法对 hashCode 分别无符号右移 (>>>) 7 位和 4 位，并与自身进行异或(^)处理。 这么做的目的是什么？

由于 indexFor() 返回的是 h(hash 值) 与 length-1(容器长度-1) 进行与运算的结果，若不进行扰动，即h = hashCode，将会很容易发生冲突。如下图所示，当低位相同时， h & (length - 1) 结果也会是一样的。

在经过扰动算法后，结果如下：

可以明显看到，计算出来的 hash 值是不一样的，即二者不会再发生冲突。这就是为什么 hash() 方法中要使用扰动算法：可以有效降低冲突概率。

既然已经解决了 hash() 的计算问题，那么接下来就是计算索引了。HashMap 通过 hash 值与 length-1 (容器长度-1)进行取模（%）运算。可能有人会问：明明源码中 indexFor() 方法进行的 按位与（&）运算，而非取模运算。

实际上，HashMap 中的 indexFor() 方法就是在进行取模运算。利用位运算代替取模运算，可以大大提高程序的计算效率。位运算可以直接对内存数据进行操作，不需要转换成十进制，因此效率要高得多。

需要注意的是，只有在特定情况下，位运算才可以替换取模运算（当 b = 2^n时，a % b = a & (b - 1) ）。也是因此，HashMap 才将初始长度设置为 16，且扩容只能是以 2 的倍数扩容。

重写equals方法需同时重写hashCode方法

最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题

public class MyTest {
    private static class Person{
        int idCard;
        String name;

        public Person(int idCard, String name) {
            this.idCard = idCard;
            this.name = name;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()){
                return false;
            }
            Person person = (Person) o;
            //两个对象是否等值，通过idCard来确定
            return this.idCard == person.idCard;
        }

    }
    public static void main(String []args){
        HashMap<Person,String> map = new HashMap<Person, String>();
        Person person = new Person(1234, "乔峰");
        //put到hashmap中去
        map.put(person, "天龙八部");
        //get取出，从逻辑上讲应该能输出“天龙八部”
        System.out.println("结果:" + map.get(new Person(1234, "萧峰")));
    }
}

实际输出结果：null

如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）

所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法时要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

出现哈希冲突时，新的节点是如何插入链表的

Java8之前是使用头插法，Java8及之后使用尾插法

链表转红黑树

在Java8之前是没有红黑树的实现的，在jdk1.8中加入了红黑树，就是当链表长度为8时会将链表转换为红黑树，为6时又会转换成链表。

JDK1.8中HashMap的性能优化

假如一个数组槽位上的链表上数据过多（即拉链过长的情况）导致性能下降该怎么办？
JDK1.8在JDK1.7的基础上增加了红黑树来进行优化。即当链表长度超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

三、面试常见问题

1.说说HashMap原理

2.加载因子为什么是0.75

默认加载因子 0.75 在时间和空间开销上给出了一个较好的折衷。
如果加载因子过大，空间开销少了，但会导致查找元素效率低；而过小则会导致空间开销大，数组利用率低，分布稀疏。
具体的数值是通过牛顿二项式定理，求得了极限值（key接近无限大时） ：log2 ≈ 0.693 （这个是在Stack Overflow找到的答案）

3.为什么初始容量是16

理论上2的整数次幂都行，但是，如果是2，4或者8会有点小，添加不了多少数据就会扩容，而扩容操作很影响性能。如果是32或者更大，那就浪费空间了。16是作为一个非常合适的经验值保留下来。

4.容量为什么是2的次幂

1）使获得的数组索引index更加均匀，减少碰撞的几率。如果容量是2的次幂，那么length-1的低位全为1，要得到特定index的存储位置，hash只有一种值，如果容量不是2的次幂，多个不同的hash值都可能得到同一个index，并且数组的某些存储位置上永远不可能有元素存储。

2）如果容量是2的次幂，扩容时，新的数组索引要么=老数组索引，要么=老数组索引+旧的数组容量，避免了新的数组索引的计算量。

3）当 b = 2^n时，a % b = a & (b - 1) ，位运算代替取模运算，可以大大提高程序的计算效率

5.说说HashMap的扩容机制

1）一旦扩容，所有元素都要重新移动到新的数组。

2）加载因子loadFactor，阈值threshold
当数组中元素个数>threshold(size > threshold)时进行扩容，threshold=capacity*loadFactor

3）预估需要的节点数，new HashMap()时设置容量，从而避免扩容。比如，预估最多n个节点，则创建HashMap：

HashMap hashMap = new HashMap(n/0.75 + 1)

6.如何防止HashMap退化为单链表

7.链表转化为红黑树的阈值为什么是8

链表的查找效率为O(n)，而红黑树的查找效率为O(logn)，红黑树提高了查找效率，虽然红黑树的查找效率变高了，但是插入效率却变低了(插入元素时需要调整红黑树的结构)，因此从一开始就用红黑树并不合适，需要选择一个临界值，临界值8是根据概率论的泊松分布计算出来的，根据概率论，哈希表的每个箱子中，元素的数量遵守泊松分布，当元素的数量为8时，概率已经很低了，因此，在正常的Hash算法下，红黑树结构基本不可能被构造出来。选择临界值为8时树化，性价比会很高，既不会因为链表太长(>8)导致复杂度加大，也不会因为树化概率太高导致太多节点树化。

8.红黑树转化为链表的阈值为什么是6，而不是8

9.准备用HashMap存1w条数据，构造HashMap时传10000会触发扩容吗?

参考：
HashMap实现原理分析

Java集合之一—HashMap
详解 HashMap 中的 hash 函数

哈希冲突及四种解决方法
Hash算法解决冲突的方法一般有以下几种常用的解决方法

HashMap框架源码深入解读，面试不用愁
害怕面试被问HashMap？这一篇就搞定了！
一个HashMap跟面试官扯了半个小时

一篇让你彻底搞懂HashMap，面试再也不怕了（文末有彩蛋）

HashMap 源码理解
HashMap源码分析——put和get（一）
HashMap源码分析 —— put与get（四）
搞懂 Java HashMap 源码

面试官再问你 HashMap 底层原理，就把这篇文章甩给他看

再也不怕面试问HashMap了
【面试题】HashMap 底层实现原理是什么？JDK8 做了哪些优化？
Java面试精选（20）：你知道为什么HashMap是线程不安全的吗？
Jdk1.8中的HashMap实现原理
JDK7中HashMap存在的问题分析，你知道哪些？
阿里P7岗位面试，面试官问我：为什么HashMap底层树化标准的元素个数是8
面试官：为什么 HashMap 的加载因子是0.75？
面试官：”准备用HashMap存1w条数据，构造时传10000会触发扩容吗？“
Hash算法及HashMap底层实现原理
HashMap的泊松分布