HashMap简介

HashMap底层数据结构采用数组+ 链表 + 红黑树。数组是HashMap的主体，链表是为了解决Hash冲突的问题、红黑树是为了解决Hash冲突达到一定程度后影响查询效率问题。其通过散列映射来存储键值对数据，所以根据key的哈希值取模数组长度可以以O(1)的时间复杂度快速查询到键值对数据。另外，它是非线程安全的，并且因为散列hash的缘故，它是无序的。

HashMap继承于AbstractMap，实现了Map、cloneable、Serializable接口；是线程不安全的；key、value允许为null，但只允许一个key值为null

一、源码分析

1. 成员变量

/**
     * 初始容量默认为16，并且必须为2的n次幂.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * 最大容量，MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 链表转红黑树阈值
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 红黑树转链表阈值.
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 链表想转红黑树的前提必须是HashMap的table数组容量大于64，否者table两倍扩容
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
/**
     * HashMap的主体：数组，容量可以为0，为了允许当前不需要的引导机制
     */
    transient Node<K,V>[] table;

    /**
     * 将数据转成Set结构，供迭代器使用：keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 元素数量.
     */
    transient int size;

    /**
     * HashMap被修改的次数，在iterators中使用，其可以理解为一个乐观锁，用于快速失败(ConcurrentModificationException).
     */
    transient int modCount;

    /**
     * 下一次要扩容的元素数量阈值，当元素数量达到threshold =（capacity * load factor）时，进行2倍扩容。
     */
    int threshold;

    /**
     * 负载因子
     */
    final float loadFactor;

1）面试题1：为了链表转红黑树的阈值是8？

因为链表中的节点遵循泊松分布，并且链接表的节点数是8的概率接近千分之一，此时链表的查询性能已经很差了。在这种情况下，将链表转为红黑树可以挽回分布查询性能，而树节点所占空间是普通节点的二倍也不再是主要矛盾了。

2）面试题2：为什么负载因子默认是0.75？

负载因子表示一个散列表的空间使用程度，HashMap的容量 = capacity * loadFactory。loadFactory的默认值是0.75是为了在时间和空间上追求一种折中。

• 如果负载因子过高，虽然会扩大散列表的装填程度，使HashMap能容纳更多的元素；但是Hash碰撞的概率也会更高。
• 如果负载因子过低，虽然会降低hash碰撞的概率，提高数据检索的效率；但会造成空间上的浪费。

3）面试题3：为什么HashMap的容量是2的n次幂？

1. 提高与运算的效率。与运算的效率高于取模运算，计算数组容量为2^n的下标时，与运算和取模运算的结果一样。并且与运算可以减少hash碰撞的概率。
2. 进行数据迁移时，可以快速定位到索引位置。

顺带一提扰动函数：为了减少Hash碰撞的概率，尽量让不同的key对应不同的hash值。在hash()中的高16位与低16位异或就可以理解为是一种扰动函数。

4）面试题4：什么时候链表会转为红黑树（细节坑）？

这里说白了就是为了看你是否真的看过源码，因为HashMap中有个MIN_TREEIFY_CAPACITY变量，表示允许执行treeifyBin()操作HashMap的最小元素个数。
所以我们只答链表的长度达到8是不全对的，还要说出元素数量大于64。

5）面试题5：HashMap什么时候扩容？如何扩容？

当Map的元素个数size超过threshold（capacity * loadFactory）时，进行扩容。
扩容的时候：

• 会先创建一个原HashMap两倍大小的Node数组，然后将原Node数组的元素rehash到新的Node数组。
• 键值对的数组位置位置有可能是原数组下标位置、可有可能是原下标+原容量的位置。
• 也就是原本只取key-hash值的低四位，扩容后取第五位，然后与0X7FFFFF取模。取模后如果第五位是1，下标就在原下标+原容量的位置。
• 扩容时，JDK1.7采用头插法；JDK1.8之后采用尾插法。

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

    /**
     * 设置初始容量，并使用默认的加载因子
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 空参构造函数，使用默认的加载因子0.75
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    /**
     * Constructs a new <tt>HashMap</tt> with the same mappings as the
     * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
     * default load factor (0.75) and an initial capacity sufficient to
     * hold the mappings in the specified <tt>Map</tt>.
     *
     * @param   m the map whose mappings are to be placed in this map
     * @throws  NullPointerException if the specified map is null
     */
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

我们着重看一下最后一个构造函数：通过接收map对象进行初始化。

    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    	// 获取Map的size
        int s = m.size();
        if (s > 0) {
        	// 数组还未初始化。
            if (table == null) { // pre-size
            	// Map的Capacity，为数组容量 / loadFactor , +1是为了向上取整，因为除法很难得到整数。
                float ft = ((float)s / loadFactor) + 1.0F;
                // 计算最大容量
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                	// 容量转为2的n次幂
                    threshold = tableSizeFor(t);
            }
            // 大于扩容阈值则扩容
            else if (s > threshold)
                resize();
            // 将m中的数据复制到HashMap中。
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

3.put()方法

HashMap的核心基本都体现在put方法，从put方法我们可以理解到HashMap的工作原理。

put方法流程图如下：

在聊put方法之前，我们先看看hash方法，HashMap是怎么计算key的哈希值的。

static final int hash(Object key) {
        int h;
        // 使用到了上述提到的扰动函数，高十六位与低十六位异或
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

下面来看看put()方法：

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

	/**
     * put()方法真正逻辑所在
     *
     * @param hash key的hash值
     * @param key key
     * @param value value值
     * @param onlyIfAbsent true表示不更新现有值
     * @param evict 如果为false，则表处于创建模式。HashMap中暂未使用
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        // tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果数组还没初始化，进行数组初始化。使用懒加载机制，table一开始是没有加载的，等put后才开始加载
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果根据key计算出的数组位置没有数据
        if ((p = tab[i = (n - 1) & hash]) == null)
        	// 新建一个Node节点插入到相应数据位置。
            tab[i] = newNode(hash, key, value, null);
        // key的hash值对应的数组下标位置不为空的情况
        else {
            // e 临时节点 ，k 当前节点的key
            Node<K,V> e; K k;
            //第一种，数组hash槽首节点的key与当前节点的相等，将当前节点赋值给临时节点e = p
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // hash槽的数据结构为红黑树
            else if (p instanceof TreeNode)
                // 在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），用与判断put操作是否成功，如果添加成功返回null
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 链表节点
            else {
                // 遍历链表
                for (int binCount = 0; ; ++binCount) {
                    // 如果在链表尾部还没有找到当前key值，则在链表尾部新增节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 判断是否转红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中有重复的key，e则为当前重复的节点，并结束链表的循环遍历
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果key值以前已经存在，则对value进行覆盖，并返回value的旧值。
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 将红黑树的root节点放到链表队首，并将root Node存储在table数组中。
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 走到这说明新增了一个Node节点，对Map的修改次数进行+1
        ++modCount;
        // Map的元素容量+1，如果大于扩容阈值，进行扩容
        if (++size > threshold)
            resize();
        // 模板方法，后置处理器
        afterNodeInsertion(evict);
        return null;
    }

1）面试题6：HashMap中的数组什么时候初始化？

从HashMap的构造方法中我们可以看到，它只是指定一些成员变量（使用Map对象的构造方法除外）。
所以可以这样聊：

• 正常情况下，我们使用HashMap的构造方法之后只是指定一些成员变量、比如loadFactor、threshold。真正的初始化发生在给Map添加第一个元素时。
• 而使用map参数的构造方法时，初始化发生在构造方法中。但是本质上还是通过putVal()方法添加元素对数组进行初始化。

2）面试题7：多线程环境下，put方法存在哪些问题？

1、数据被覆盖

• 两个线程A/B同时进行put操作，并且hash函数计算出要插入数组下标相同时，A线程刚计算完hash值还没来得及插入数据，CPU时间片耗尽被挂起。
• 线程B接着执行完了全部操作，然后线程A恢复，那么最终线程B插入的数据就被A覆盖了。

2、size偏小

• ++size操作是非原子性操作，存在线程安全问题。
• 加入两个线程A/B同时进入++size操作，获取到原size的值一样，进行赋值操作时，它俩就等于是只给size+了1。

3）面试题8：HashMap工作原理？

• HashMap基于数组+ 链表 + 红黑树的数据结构。数组是HashMap的主体，链表是为了解决Hash冲突的问题、红黑树是为了解决Hash冲突达到一定程度后影响查询效率问题。使用Node来存储键值对。
• 通过散列映射来存储键值对数据，所以根据key的哈希值取模数组长度可以以O(1)的时间复杂度快速查询到键值对数据。
• 接着聊一下负载因子的作用。
• 最后讲一讲put()方法流程。其中建议提到扰动函数、rehash等词汇。具体话术请读者参考put()方法流程图梳理。
• get()、remove()方法捎带一提。

4）面试题9：当两个对象的hashcode相同会发生什么？

• 发生hash碰撞
• 因为hashCode相同，所以它们的bucket位置相同，‘碰撞’就发生了。
• 因为HashMap使用链表存储对象，这个Node对象会存储在链表中。当链表长度达到8时，链表将转为红黑树。

5）面试题10：HashMap的hash是如何实现的？

• JDK1.8中，在hash()方法将hashCode的高16位与低16位做异或操作。
• 我们可以把它看做是一种扰动函数，hashCode的高16位和低16位都参与了数组下标的计算，减少了hash碰撞的概率。

4. get()方法

获取数据流程如下：

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * get()方法核心逻辑
     *
     * @param hash hash for key
     * @param key the key
     */
    final Node<K,V> getNode(int hash, Object key) {
        // tab 数组，first 头结点，e 临时变量，n 长度,k 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;
    }

5. resize()方法

HashMap扩容逻辑：

final Node<K,V>[] resize() {
    // 阶段一：计算newCap、newThr
    // 没插入数据之前的哈希数组oldTab
    Node<K,V>[] oldTab = table;
    // old数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // old扩容阈值
    int oldThr = threshold;
    // 新的数组容量和扩容阈值
    int newCap, newThr = 0;
    // oldCap > 0表示不是首次初始化，因为hashMap用的是懒加载
    if (oldCap > 0) {
        // 老数组容量大于最大容量（1 << 30）时
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 扩容阈值为整数的最大值
            threshold = Integer.MAX_VALUE;
            // 然后就不扩容了
            return oldTab;
        }
        // 两倍扩容，并且扩容后的长度要小于最大值、old容量要大于等于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 扩容阈值变为原扩容阈值的2倍
            newThr = oldThr << 1; 
    }

    // 处理情况：溢出越界
    else if (oldThr > 0) 
        newCap = oldThr;
    // 新的HashMap首次初始化时，设置数组容量
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 扩容阈值等于容量*加载因子
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 未指定HashMap容量初始化时，newThr没有赋值
    if (newThr == 0) {
        // 扩容阈值
        float ft = (float)newCap * loadFactor;
        // 判断新数组容量是否大于最大值，扩容阈值是否大于最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 扩容阈值赋值
    threshold = newThr;
    // 表示忽略该警告
    @SuppressWarnings({"rawtypes","unchecked"})
        // 初始化数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // rehash操作，
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            // 临时变量
            Node<K,V> e;
            // 当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突
            if ((e = oldTab[j]) != null) {
                // 把已经赋值之后的变量置位null，当然是为了便于回收，释放内存
                oldTab[j] = null;
                // 如果下标处的节点没有下一个元素，也就是普通节点
                if (e.next == null)
                    // 把该变量的值存入newCap中，数组下标为e.hash & (newCap - 1)
                    newTab[e.hash & (newCap - 1)] = e;
                // 该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
                else if (e instanceof TreeNode)
                    // 把此树进行转移到newCap中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 此处表示为链表结构，同样把链表转移到newCap中；
                    // 则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置；
                    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;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回扩容后的hashMap
    return newTab;
}

6. remove()方法

    public V remove(Object key) {
        //临时变量
        Node<K,V> e;
        /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    /**第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，不删除key,第四个如果为false，则表示删除后，不移动节点**/
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            //nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value
            Node<K,V> node = null, e; K k; V v;
            //如果数组下标的节点正好是要删除的节点，把值赋给临时变量node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //也就是要删除的节点，在链表或者红黑树上，先判断是否为红黑树的节点
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    //遍历红黑树，找到该节点并返回
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { //表示为链表节点，一样的遍历找到该节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        //如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果删除的节点是红黑树结构，则去红黑树中删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //删除的节点为数组下标节点，也就是头结点，直接让当前节点的next节点作为头节点（可能为 null）
                else if (node == p)
                    tab[index] = node.next;
                else 
                    // 删除的节点在链表中，把要删除的下一个结点设为上一个结点的下一个节点
                    p.next = node.next;
                //修改计数器
                ++modCount;
                //长度减一
                --size;
                //模板方法，后置处理器
                afterNodeRemoval(node);
                //返回删除的节点
                return node;
            }
        }
        //返回null则表示没有该节点，删除失败
        return null;
    }

常见其他面试题

1）面试题11：HashMap的几种遍历方式？

1. map.keySet() – 建议在只需要key值时使用。

for (String key : map.keySet()) {
    map.get(key);
}

2. map.values() – 建议在需要使用value值时使用。

for (String value:map.values()){
     System.out.println("value:"+value);
}

3. map.entrySet() – 建议在需要同时使用k-v时使用。

Set<Map.Entry<String, String>> entrySet = map.entrySet();
    for (Map.Entry<String, String> entry : entrySet) {
        entry.getKey();
        entry.getValue();
}

4. map.entrySet().iterator() – 迭代器方式，需要对map的元素进行remove操作时。

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> next = iterator.next();
    if (next.getValue() % 2 == 1) {
        iterator.remove();
        System.out.println("To delete key " + next.getKey());
    }
}
for(String k : map.keySet()) {
    System.out.println(k);
}

2）面试题12：HashMap、LinkedHashMap、TreeMap的区别和使用场景？

1. 一般情况下HashMap当做Hash散列表使用。
   在 Map 中进行插入、删除和定位元素操作时，使用HashMap。
2. TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）
   在需要按自然顺序或自定义顺序遍历键的情况下使用TreeMap。
3. LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢；
   在需要输出的顺序和输入的顺序相同的情况下使用LinkedHashMap。

3）面试题13：HashMap和HashTable的区别？

• HashMap允许key和value为null，Hashtable不允许。
• HashTable在写入时会比较慢。HashMap速度比较快。
• Hashtable是线程安全的，HashMap不是的。所以HashMap适用于单线程，HashTable多线程。
• Hashtable的初始容量为11，扩容为原来的2n+1；HashMap的初始容量为16，扩容为2n。
• HashMap提供了对key的Set进行遍历，因此HashMap是fast-fail的。HashTable提供了对key的Enumeration（列举）进行遍历，它不支持fast-fail。
• Hashtable被认为是一个遗留的类，想要在迭代的时候修改Map，应该使用ConcurrentHashMap。