JDK1.8 HashMap源码解析+最全面试题

JDK1.8 HashMap源码解析+最全面试题

目录

​​HashMap简介​​​​一、源码分析​​

​​1. 成员变量​​

​​1）面试题1：为了链表转红黑树的阈值是8？​​​​2）面试题2：为什么负载因子默认是0.75？​​​​3）面试题3：为什么HashMap的容量是2的n次幂？​​​​4）面试题4：什么时候链表会转为红黑树（细节坑）？​​​​5）面试题5：HashMap什么时候扩容？如何扩容？​​

​​2.构造方法​​​​3.put()方法​​

​​1）面试题6：HashMap中的数组什么时候初始化？​​​​2）面试题7：多线程环境下，put方法存在哪些问题？​​​​3）面试题8：HashMap工作原理？​​​​4）面试题9：当两个对象的hashcode相同会发生什么？​​​​5）面试题10：HashMap的hash是如何实现的？​​

​​4. get()方法​​​​5. resize()方法​​​​6. remove()方法​​

​​常见其他面试题​​

​​1）面试题11：HashMap的几种遍历方式？​​​​2）面试题12：HashMap、LinkedHashMap、TreeMap的区别和使用场景？​​​​3）面试题13：HashMap和HashTable的区别？​​

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[] table; /** * 将数据转成Set结构，供迭代器使用：keySet() and values(). */ transient Set> 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次幂？

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

顺带一提扰动函数：为了减少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 HashMap with the same mappings as the * specified Map. The HashMap is created with * default load factor (0.75) and an initial capacity sufficient to * hold the mappings in the specified Map. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public HashMap(Map m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

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

final void putMapEntries(Map 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 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[] tab; Node 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 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)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 e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * get()方法核心逻辑 * * @param hash hash for key * @param key the key */ final Node getNode(int hash, Object key) { // tab 数组，first 头结点，e 临时变量，n 长度,k key Node[] tab; Node 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)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[] resize() { // 阶段一：计算newCap、newThr // 没插入数据之前的哈希数组oldTab Node[] 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[] newTab = (Node[])new Node[newCap]; table = newTab; // rehash操作， if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { // 临时变量 Node 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)e).split(this, newTab, j, oldCap); else { // 此处表示为链表结构，同样把链表转移到newCap中； // 则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置； Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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 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 removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标 Node[] tab; Node 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 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)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)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的几种遍历方式？

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

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

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

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

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

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

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

Map map = new HashMap<>();map.put("a", 1);map.put("b", 2);map.put("c", 3);Iterator> iterator = map.entrySet().iterator();while (iterator.hasNext()) { Map.Entry 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的区别和使用场景？

一般情况下HashMap当做Hash散列表使用。在 Map 中进行插入、删除和定位元素操作时，使用HashMap。TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）在需要按自然顺序或自定义顺序遍历键的情况下使用TreeMap。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。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。