1.HashMap以及HashMap的基本原理

1.1什么是HashMap？

HashMap是Java集合框架中Map容器的一个实现类，它的底层是使用哈希表实现的，更加具体地说在jdk7中采用数组+链表实现，在jdk8中采用数组+链表+红黑树实现。

Map代表具有映射关系（key-value）的集合，其所有的key是一个Set集合（key值不能重复），即key无序且不能重复，而HashMap就是Map接口下的一个实现类，HashMap是一个储存键值对（EntrySet）的集合，并且支持储存key/value为 null 的元素。

下面我们基于jdk8来说一说HashMap的基本原理。

1.2HashMap的属性

HashMap对象被构造时，初始的默认容量为 1<<4 ，也就是 16 ，并且必须是2的幂（这与哈希函数有关）。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

HashMap最大的容量为 1<<30 ，也就是 2 30 2^{30} 2 30 。

static final int MAXIMUM_CAPACITY = 1 << 30;

HashMap默认的负载因子为 0.75 。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

链表树化的最小链表大小阈值 8 ，当HashMap中数组大于 64 ，数组所挂链表的大小超过 8 才会将数组所挂的链表转换为红黑树。

static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;

红黑树链表化的的阈值是 6 ，当红黑树结点个数小于 6 时，就会转换为链表。

static final int UNTREEIFY_THRESHOLD = 6;

HashMap底层的数组，是一个链表数组：

transient Node<K,V>[] table;

元素个数阈值，当HashMap的size大于threshold时会执行resize操作， threshold=capacity*loadFactor ，其中capacity表示数组的容量。

int threshold;

1.3HashMap的构造方法

HashMap最常用的构造方法，一个是无参的构造方法，使用无参构造方法构造HashMap时，默认的构造容量是 16 ，但是此时不会真的去申请一个大小为 16 的数组，还有一个指定容量的构造方法也是如此，并且所取容量为大于或等于指定容量的一个最接近的2次幂数，日指定容量为 19 ，那实际数组容量为 32 。

源码：

public HashMap(int initialCapacity) {
 
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

public HashMap() {
 
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

除此之外，还有指定容量和负载因子的构造方法，其中 tableSizeFor(initialCapacity) 方法会生成比 initialCapacity 大并最接近 initialCapacity 的一个 2 次幂。

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对象构造HashMap的构造方法，使用这种方式构造，只要传入的参数有元素，那么数组空间肯定已经申请好了，否则也是没有去申请的。

public HashMap(Map<? extends K, ? extends V> m) {
 
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

所以我们可以得到一个结论：当HashMap对象创建时，内部的数组并没有分配内存。

1.4HashMap开辟数组的时机

真正为数组分配内存是在第一次 put 操作的时候，其中源码如下：

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

意思就是通过哈希函数 hash 生成对应数组的下标值，找到对应的位置进制插入。

如果是第一次插入，就会对链表数组进行扩容，也是正式地为数组初始化：

我们就不继续深入看了，在resize方法中，会为数组分配内存，并且大小为2的幂，至于为什么是这个值，这与HashMap中的哈希函数有关。

1.5HashMap中的put

如果是首次扩容，先判断数组是否为空，若数组为空则进行第一次扩容（resize），会为HashMap对象申请一个默认容量大小 16 的数组。

第一步，通过hash()方法计算索引，通过hash算法，计算键值对在数组中的索引，并通过索引找到在数组中的位置。

第二步，插入数据，分以下几种情况：

• 如果当前位置元素为空，则直接插入数据；
• 如果当前位置元素非空，遍历链表或红黑树，如果key已存在，则直接覆盖其value；
• 如果当前位置元素非空，遍历链表或红黑树，如果key不存在，则将数据链尾插（jdk7是头插）到链表；
• 若链表长度达到8，并且HashMap中的 table 数组大小达到 64 ，则将链表转换成红黑树，并将数据插入树中，如果链表长度达到 8 但是 table 数组大小没有 64 则将数组扩容；

第三步，检查存储的元素个数，如果超过阈值 threshold ，则扩容。这一步其实也就是检查负载因子是否超过默认值，超过就扩容。

1.6HashMap中的哈希函数

前面我们说到了hash方法，HashMap中的hash方法是与我们直接根据 key 生成hashCode值再取模的方式不同，在HashMap中的hash算法中，首先会 key 计算出hashCode值，然后再将hashCode值与右移 16 为的hashCode值进行按位异或操作，得到一个新的哈希值，这样做的目的其实就是为了增强哈希值的随机性，这个方法也叫做“扰动方法”。

static final int hash(Object key) {
 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

在进行put等需要找到某个 key 所对应的数组索引的时候，HashMap不是通过直接取数组长度的模来得到对应的下标，取而代之的是使用按位与 & 运算来进行下标的计算，毕竟位运算的效率是大于取模 % 操作的。假设HashMap底层数组 table 的长度为 length ，不妨记 n=length-1 ， key 对应的哈希值为 h 。

在jdk8源码中，使用 h&(n-1) 来获取对应 table 数组的索引（下标）,这也解释了为什么HashMap当中的数组长度一定是 2 的幂。

因为使用 2 的幂再减去一个 1 ，得到的数 n 它的所有有效二进制位均为 1 ，如 64 的二进制数为 1000000 ，减去 1 得到 n ，它的值为 0111111 ，数组的长度的二进制有效位是 7 位，因为数组长度是二的幂，数组下标最大下标有效位一定是 6 位，并且全为 1 ，我们知道 0 与任何数按位与得到的均为 0 ，而 1 与任何数运算得到的结果可能是 1 也可能是 0 ，这就保证了在使用 & 操作时，每一位有效位的值都有可能是 0 或 1 ，进一步就保证了数组 table 的所有下标均有可能被映射到，反之如果存在含有 0 的二进制有效位，则那一位按位与的操作结果一定是 0 ，这样的话，一定存在数组 table 中某些下标无法被映射，增大了哈希冲突的可能性。

做个小总结，HashMap中计算的哈希值是通过hashCode值与右移16位hashCode值按位异或的结果，这个目的就是为了增强哈希值的随机性。HashMap确定索引的方法是将 n&h ，毕竟按位与的效率大于取模，为了数组每个下标都可能被映射到，则 n 的每一位二进制有效位均得为 1 ，所以数组的长度必须为 2 的幂，因为只有 2 的幂减 1 得到的有效二进制位均为 1 。

其中 n 表示数组长度减去一个 1 ， h 表示通过hash方法得到的哈希值。

1.7HashMap的扩容机制

HashMap中 table 数组初始默认大小为 16 ，根据上述对hash方法的分析，数组 table 长度一定得是 2 的幂，从这里就不难猜出，HashMap极有可能是 2 倍扩容，毕竟 2 倍扩容比较合理，并且它能够保证扩容后的数组大小也是 2 的幂。

在jdk8中，HashMap的扩容，确实是采用了 2 倍扩容。

当HashMap对象中元素个数 size 大于 threshold 或者数组为 null 时会触发扩容 resize 。

为了解决哈希冲突，jdk8采用了数组+链表+红黑树的方式实现，当数组中某链表的长度大于 8 ，并且数组 table 的长度达到 64 ，就会将链表转换为红黑树来提高效率，当数组中某链表长度大于 8 但是数组 table 长度没有达到 64 ，此时就会进行扩容。

当红黑树结点个数小于 6 时，就会将红黑树转换回链表。

在扩容的时候，会将所有的元素遍历，全部重新计算哈希值并全部重新确定在数组中的位置。

2.HashSet的基本实现原理

HashSet是基于HashMap实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的HashMap。它封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存，而 HashMap 的 value 则存储了一个 PRESENT，它是一个静态的 Object 对象。

3.有关HashMap其他的面试题

3.1HashMap是否是线程安全的？有没有线程安全的"HashMap"？

HashMap不能保证线程安全，因为在并发的情况下进行 put 操作，可能会导致数组中链表死循环。

线程安全的“HashMap”有HashTable，它相比于HashMap，给关键的方法加上了锁，那么给方法加锁本质上就是给对象加锁，那么每种操作都需要拿对象锁，这样会造成激烈的锁竞争。

相比于HashTable，更推荐使用CurrentHashMap，在jdk7中，它是给每一个数组中的元素都加上了锁，或者说创建了一个新的数组 Segment ，这个数组用于实现加锁操作，每个 Segment 里包含一个 HashEntry 数组，Segment 中元素的结构和 HashMap 类似，是一个数组和链表结构。

在jdk8中，已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap，简单说，在HashMap的基础上，就是给每个数组中的元素加锁，来保证线程安全，并且由于每个数组元素都有锁，所以相比于HashTable锁竞争的激烈程度小得多。

3.2HashMap有什么特点？

1. HashMap是线程不安全的，支持序列化。
2. HashMap可以使用null作为key或value。
3. HashMap查找的效率可达到O(1)。
4. HashMap遍历方式比较单一，主要使用EntrySet 和 KeySet进行遍历，遍历方式有增强for循环和迭代器。
5. HashMap是Map容器的一种实现，是无序的键值对集合。