不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）

矫情吗；* 2022-11-01 04:29 150阅读 0赞

前言  
朋友们又见面了，你是不是还在面试时被面试官问懵HashMap？不会手写实现一个简单HashMap？看完这篇文章你再不会算我输！

提示：以下是本篇文章正文内容，案例仅供参考

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
一、HashMap介绍  
1.HashMap是什么？

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap类与Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。 --摘自百度百科

二、HashMap底层原理  
首先要明白在JDK1.7时HashMap的底层是由数组+链表实现的，到了JDK1.8后改成了数组+链表+红黑树实现，接下来我将对这几种数据结构详细讲解，并且

1.数组

特点：

数组是相同数据类型的元素的集合。  
数组中的各元素的存储是有先后顺序的，它们在内存中按照这个先后顺序连续存放在一起。  
数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如，a\[0\]表示名字为a的数组中的第一个元素，a\[1\]代表数组a的第二个元素，以此类推。  
下标可以是常量，变量，或表达式，但其值必须是整数（如果是小数将四舍五入为整数)。  
下标必须为一段连续的整数，其最小值成为下界，其最大值成为上界。不加说明时下界值默认为1。  
不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
2.单向链表

单向链表是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
特点：

新增删除节点速方便、速度快，不需要像线性结构那样移动剩下的数据  
查询较数组慢，需要通过循环或者递归的方法访问到任意数据，平均的访 问效率低于线性表  
只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。  
适用于节点的增加删除。

3.双向链表

双向链表是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
特点：

有两个指针，一个指向前一个节点，一个指向后一个节点  
可以找到前驱和后继，可进可退  
增加删除节点复杂，需要多分配一个指针存储空间  
4.红黑树

红黑树是一种特定类型的二叉树，也是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树，由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法。

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
特点：

每个节点只能是红色或者黑色。  
根节点必须是黑色。  
红色的节点，它的叶节点只能是黑色。  
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。  
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树

三、HashMap源码详解  
OK，了解了以上数据结构后咱们再来看看HashMap底层源码是如何实现的, 先看下HashMap的存储结构

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
1.PUT操作

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  
boolean evict) \{  
Node<K,V>\[\] tab; Node<K,V> p; int n, i;  
//1. 如果当前table为空，新建默认大小的table  
if ((tab = table) == null || (n = tab.length) == 0)  
n = (tab = resize()).length;  
//2. 获取当前key对应的节点  
if ((p = tab\[i = (n - 1) & hash\]) == null)  
//3. 如果不存在，新建节点  
tab\[i\] = newNode(hash, key, value, null);  
else \{  
//4. 存在节点  
Node<K,V> e; K k;  
//5. key的hash相同，key的引用相同或者key equals，则覆盖  
if (p.hash == hash &&  
((k = p.key) == key || (key != null && key.equals(k))))  
e = p;  
//6. 如果当前节点是一个红黑树树节点，则添加树节点  
else if (p instanceof TreeNode)  
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
//7. 不是红黑树节点，也不是相同节点，则表示为链表结构  
else \{  
for (int binCount = 0; ; ++binCount) \{  
//8. 找到最后那个节点  
if ((e = p.next) == null) \{  
p.next = newNode(hash, key, value, null);  
//9. 如果链表长度超过8转成红黑树  
if (binCount >= TREEIFY\_THRESHOLD - 1) // -1 for 1st  
treeifyBin(tab, hash);  
break;  
\}  
//10.如果链表中有相同的节点，则覆盖  
if (e.hash == hash &&  
((k = e.key) == key || (key != null && key.equals(k))))  
break;  
p = e;  
\}  
\}  
if (e != null) \{ // existing mapping for key  
V oldValue = e.value;  
//是否替换掉value值  
if (!onlyIfAbsent || oldValue == null)  
e.value = value;  
afterNodeAccess(e);  
return oldValue;  
\}  
\}  
//记录修改次数  
\++modCount;  
//是否超过容量，超过需要扩容  
if (++size > threshold)  
resize();  
afterNodeInsertion(evict);  
return null;  
\}  
1.计算关于key的hashcode值

2.如果散列表为空时，调用resize()初始化散列表

3.如果没有发生碰撞，直接添加元素到散列表中去

4.如果发生了碰撞(hashCode值相同)，进行三种判断

1:若key地址相同或者equals后内容相同，则替换旧值

2:如果是红黑树结构，就调用树的插入方法

3:链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。  
5.如果桶满了大于阀值，则resize进行扩容

2.GET操作

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
final Node<K,V> getNode(int hash, Object 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)  
　　　　　　　　　　　　//若定位到的节点是　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;  
\}  
final TreeNode<K,V> getTreeNode(int h, Object k) \{  
return ((parent != null) ? root() : this).find(h, k, null);  
\}  
final TreeNode<K,V> find(int h, Object k, Class<?> kc) \{  
TreeNode<K,V> p = this;  
do \{  
int ph, dir; K pk;  
TreeNode<K,V> pl = p.left, pr = p.right, q;  
//首先进行hash 值的比较，若不同令当前节点变为它的左孩子或者右孩子  
if ((ph = p.hash) > h)  
p = pl;  
else if (ph < h)  
p = pr;  
//hash 值相同，进行 key值的比较  
else if ((pk = p.key) == k || (k != null && k.equals(pk)))  
return p;  
else if (pl == null)  
p = pr;  
else if (pr == null)  
p = pl;  
/hash 值相同，key 值不同 ,若k 是可比较的并且k.compareTo(pk) 返回结果不 为０可进入下面else if  
else if ((kc != null ||  
(kc = comparableClassFor(k)) != null) &&  
(dir = compareComparables(kc, k, pk)) != 0)  
p = (dir < 0) ? pl : pr;  
若 k 是不可比较的　或者　k.compareTo(pk) 返回结果为０则在整棵树中进行查找，先找右子树，右子树没有再找左子树  
else if ((q = pr.find(h, k, kc)) != null)  
return q;  
else  
p = pl;  
\} while (p != null);  
return null;  
\}  
对key的hashCode进行hashing  
与运算计算下标获取bucket位置，如果在桶的首位上就可以找到就直接返回，否则在树中找或者链表中遍历找  
如果有hash冲突，则利用equals方法去遍历链表查找节点  
3.RESIZE操作

扩容的时候，HashMap是把长度扩为原来2倍，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

final Node<K,V>\[\] resize() \{  
Node<K,V>\[\] oldTab = table;  
int oldCap = (oldTab == null) ? 0 : oldTab.length;  
int oldThr = threshold;  
int newCap, newThr = 0;  
　　/\*  
1、resize（）函数在size　> threshold时被调用。  
oldCap大于 0 代表原来的 table 表非空， oldCap 为原表的大小，  
oldThr（threshold） 为 oldCap × load\_factor  
　*/  
if (oldCap > 0) \{  
if (oldCap >= MAXIMUM\_CAPACITY) \{  
threshold = Integer.MAX\_VALUE;  
return oldTab;  
\}  
else if ((newCap = oldCap << 1) < MAXIMUM\_CAPACITY &&  
oldCap >= DEFAULT\_INITIAL\_CAPACITY)  
newThr = oldThr << 1; // double threshold  
\}  
　　　　/*  
2、resize（）函数在table为空被调用。  
oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为  
HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)  
或 HashMap(Map<? extends K, ? extends V> m)，导致 oldTab 为 null，oldCap 为0，  
oldThr 为用户指定的 HashMap的初始容量。  
　　*/  
else if (oldThr > 0) // initial capacity was placed in threshold  
newCap = oldThr;  
　　　　　/*  
3、resize（）函数在table为空被调用。  
oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的　HashMap，所有值均采用默认值，  
　　 oldTab（Table）表为空，oldCap为0，oldThr等于0，  
　　\*/  
else \{ // zero initial threshold signifies using defaults  
newCap = DEFAULT\_INITIAL\_CAPACITY;  
newThr = (int)(DEFAULT\_LOAD\_FACTOR \* DEFAULT\_INITIAL\_CAPACITY);  
\}  
if (newThr == 0) \{  
float ft = (float)newCap \* loadFactor;  
newThr = (newCap < MAXIMUM\_CAPACITY && ft < (float)MAXIMUM\_CAPACITY ?  
(int)ft : Integer.MAX\_VALUE);  
\}  
threshold = newThr;  
Node<K,V>\[\] newTab = (Node<K,V>\[\])new Node\[newCap\];  
table = newTab;  
if (oldTab != null) \{  
　　　　　　　//把　oldTab 中的节点　reHash 到　newTab 中去  
for (int j = 0; j < oldCap; ++j) \{  
Node<K,V> e;  
if ((e = oldTab\[j\]) != null) \{  
oldTab\[j\] = null;  
　　　　　　　　　　　　//若节点是单个节点，直接在 newTab　中进行重定位  
if (e.next == null)  
newTab\[e.hash & (newCap - 1)\] = e;  
　　　　　　　　　　　　//若节点是　TreeNode 节点，要进行 红黑树的 rehash　操作  
else if (e instanceof TreeNode)  
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);  
　　　　　　　　　　　　//若是链表，进行链表的 rehash　操作  
else \{ // preserve order  
Node<K,V> loHead = null, loTail = null;  
Node<K,V> hiHead = null, hiTail = null;  
Node<K,V> next;  
do \{  
　　 next = e.next;  
　　　　　　　　　　　　　　　　　　//根据算法　e.hash & oldCap　判断节点位置　rehash　后是否发生改变  
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;  
　　　　　　　　　　　　　　　　// rehash　后节点新的位置一定为原来基础上加上　oldCap  
newTab\[j + oldCap\] = hiHead;  
\}  
\}  
\}  
\}  
\}  
return newTab;  
\}  
//这个函数的功能是对红黑树进行　rehash 操作  
final void split(HashMap<K,V> map, Node<K,V>\[\] tab, int index, int bit) \{  
TreeNode<K,V> b = this;  
// Relink into lo and hi lists, preserving order  
TreeNode<K,V> loHead = null, loTail = null;  
TreeNode<K,V> hiHead = null, hiTail = null;  
int lc = 0, hc = 0;  
//由于TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash  
for (TreeNode<K,V> e = b, next; e != null; e = next) \{  
next = (TreeNode<K,V>)e.next;  
e.next = null;  
if ((e.hash & bit) == 0) \{  
if ((e.prev = loTail) == null)  
loHead = e;  
else  
loTail.next = e;  
loTail = e;  
\++lc;  
\}  
else \{  
if ((e.prev = hiTail) == null)  
hiHead = e;  
else  
hiTail.next = e;  
hiTail = e;  
\++hc;  
\}  
\}

//rehash 操作之后注意对根据链表长度进行　untreeify　或　treeify　操作
           if (loHead != null) {
               if (lc <= UNTREEIFY_THRESHOLD)
                 tab[index] = loHead.untreeify(map);
             else {
                  tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                       loHead.treeify(tab);
                }
         }
          if (hiHead != null) {
              if (hc <= UNTREEIFY_THRESHOLD)
                  tab[index + bit] = hiHead.untreeify(map);
              else {
                  tab[index + bit] = hiHead;
                 if (loHead != null)
                    hiHead.treeify(tab);
         }
        }//end if
      }//end split

复制代码  
四、HashMap简单手写实现  
HyhMap接口

package com.hyh.core.test.map;

/\*\*

*  手写实现Map接口
 *  
 *  @Author heyuhua
 *  @create 2021/2/9 15:29  
    \*/  
    public interface HyhMap<K, V> \{
    
    /\*\*
    
     *  PUT接口
     *  
     *  @param k
     *  @param v  
        \*/  
        void put(K k, V v);
    
    /\*\*
    
     *  GET接口
     *  
     *  @param k
     *  @return  
        \*/  
        V get(K k);
    
    /\*\*
    
     *  获取map大小接口
     *  
     *  @return  
        \*/  
        int size();
    
    /\*\*
    
     *  Entry 接口
     *  
     *  @param
     *  @param  
        */  
        interface Entry<K, V> \{  
        /*\*
        
         *  获取KEY值
         *  
         *  @return  
            \*/  
            K getKey();
        
        /\*\*
        
         *  获取Value值
         *  
         *  @return  
            \*/  
            V getValue();  
            \}

\}  
HyhHashMap实现类

package com.hyh.core.test.map;

import java.io.Serializable;

/\*\*

*  手写实现HashMap
 *  
 *  @Author heyuhua
 *  @create 2021/2/9 15:31  
    \*/  
    public class HyhHashMap<K, V> implements HyhMap<K, V>, Serializable \{
    
    /\*\*
    
     *  默认容量  
        \*/  
        static final int DEFAULT\_CAPACITY = 16;
    
    int threshold;  
    /\*\*
    
     *  当前key索引位置  
        \*/  
        int keyIndex;
    
    /\*\*
    
     *  负载因子  
        */  
        static final float DEFAULT\_LOAD\_FACTOR = 0.75f;  
        /*\*
     *  保存Node<K,V>节点的数组  
        */  
        Node<K, V>\[\] table;  
        /*\*
     *  存储当前Map容量的大小  
        \*/  
        int size;
    
    @Override  
    public void put(K key, V value) \{  
    Node<K, V> node;  
    if (table == null) \{  
    table = resize();  
    //table里面为空的情况  
    node = new Node<K, V>(hash(key), key, value, null);  
    table\[keyIndex\] = node;  
    size++;  
    \} else \{  
    table = resize();  
    //table不为空时  
    Node<K, V> n;  
    //是否hash冲突  
    boolean hashConflict = false;  
    for (int i = 0; i < table.length; i++) \{  
    n = table\[i\];  
    if (n != null) \{  
    if (n.hash == hash(key)) \{  
    hashConflict = true;  
    //hash相等时  
    while (n != null) \{  
    if (n.key.equals(key)) \{  
    //hash相等并且key也相等，直接替换原来的值就行了  
    n.value = value;  
    table\[i\] = n;  
    size++;  
    \} else \{  
    node = new Node<K, V>(hash(key), key, value, null);  
    node.next = n;  
    table\[i\] = node;  
    size++;  
    \}  
    n = n.next;  
    \}  
    \}  
    \}
    
        }
             if (!hashConflict) {
                 //没有hash冲突，直接put
                 node = new Node<K, V>(hash(key), key, value, null);
                 table[++keyIndex] = node;
                 size++;
        
             }
         }
    
    \}
    
    @Override  
    public V get(K key) \{  
    HyhHashMap.Node<K, V> node;  
    return (node = getNode(key)) == null ? null : node.value;  
    \}
    
    /\*\*
    
     *  获取Node
     *  
     *  @param key
     *  @return  
        \*/  
        final HyhHashMap.Node<K, V> getNode(Object key) \{  
        if (table != null) \{  
        for (int i = 0; i < table.length; i++) \{  
        Node<K, V> node = table\[i\];  
        if (node != null) \{  
        //hash相等  
        if (node.hash == hash(key)) \{  
        while (node != null) \{  
        if (node.key.equals(key)) \{  
        //hash和key都相等时\`  
        return node;  
        \}  
        node = node.next;  
        \}  
        \}  
        \}
        
            }
        
        \}  
        return null;  
        \}
    
    /\*\*
    
     *  扩容
     *  
     *  @return  
        \*/  
        final Node<K, V>\[\] resize() \{  
        Node<K, V>\[\] newTable;  
        int newCapacity, oldCapacity;  
        if (table == null) \{  
        keyIndex = 0;  
        threshold = (int) (DEFAULT\_CAPACITY \* DEFAULT\_LOAD\_FACTOR);  
        table = (HyhHashMap.Node<K, V>\[\]) new HyhHashMap.Node\[DEFAULT\_CAPACITY\];  
        newTable = table;  
        \} else \{  
        oldCapacity = table.length;  
        if (table.length > threshold) \{  
        //扩容两倍  
        newCapacity = threshold \*= 2;  
        newTable = (HyhHashMap.Node<K, V>\[\]) new HyhHashMap.Node\[newCapacity\];  
        //把原来的table移动到newTable  
        int newIndex = 0;  
        for (int i = 0; i < oldCapacity; i++) \{  
        Node<K, V> node = table\[i\];  
        //咱们这只使用最简单的方式、不考虑其他情况、不涉及红黑树  
        if (node != null) \{  
        if (node.next == null)  
        newTable\[newIndex\] = node;  
        else \{  
        HyhHashMap.Node<K, V> loHead = null, loTail = null, hiHead = null, hiTail = null, next;  
        do \{  
        next = node.next;  
        if (node.hash == 0) \{  
        if (loTail == null)  
        loHead = node;  
        else  
        loTail.next = node;  
        loTail = node;  
        \} else \{  
        if (hiTail == null)  
        hiHead = node;  
        else  
        hiTail.next = node;  
        hiTail = node;  
        \}  
        \} while ((node = next) != null);  
        if (loTail != null) \{  
        loTail.next = null;  
        newTable\[newIndex\] = loHead;  
        \}  
        if (hiTail != null) \{  
        hiTail.next = null;  
        newTable\[newIndex + oldCapacity\] = hiHead;  
        \}  
        \}  
        \}  
        newIndex++;  
        \}  
        \} else \{  
        newTable = table;  
        \}  
        \}
        
        return newTable;  
        \}
    
    /\*\*
    
     *  计算Hash值
     *  
     *  @param key
     *  @return  
        */  
        /*\*
     *  计算Hash值
     *  
     *  @param key
     *  @return  
        \*/  
        static final int hash(Object key) \{  
        int h;  
        return (key == null) ? 0 : Math.abs((h = key.hashCode()) ^ (h >>> 16));  
        \}
    
    @Override  
    public int size() \{  
    return size;  
    \}
    
    /\*\*
    
     *  Node 实现HyhMap Entry接口
     *  
     *  @param
     *  @param  
        \*/  
        static class Node<K, V> implements HyhMap.Entry<K, V> \{  
        //hash值  
        final int hash;  
        // key  
        final K key;  
        // value  
        V value;  
        // next节点  
        HyhHashMap.Node<K, V> next;
        
        public Node(int hash, K key, V value, Node<K, V> next) \{  
        this.hash = hash;  
        this.key = key;  
        this.value = value;  
        this.next = next;  
        \}
        
        public final K getKey() \{  
        return key;  
        \}
        
        public final V getValue() \{  
        return value;  
        \}
    
    \}  
    \}  
    五、单元测试  
    OK，不废话，直接测试一下我花了半个小时写的HashMap，当然我这里并没有加入红黑树，性能和JDK的HashMap肯定没得比，所以兄弟们，别喷我哈！

package com.hyh.core.test.map;

import org.junit.Test;

/\*\*

*  HyhHasMap Test
 *  
 *  @Author heyuhua
 *  @create 2021/2/9 17:54  
    \*/  
    public class HyhHashMapTest \{
    
    /\*\*
    
     *  普通测试  
        \*/  
        @Test  
        public void test() \{  
        HyhHashMap<String, String> hyhHashMap = new HyhHashMap<>();  
        hyhHashMap.put(“name”, “heyuhua”);  
        hyhHashMap.put(“height”, “180cm”);  
        hyhHashMap.put(“name”, “hyh”);  
        hyhHashMap.put(“height”, “180”);  
        System.out.println(“name:” + hyhHashMap.get(“name”) + “,height:” + hyhHashMap.get(“height”));  
        \}
    
    /\*\*
    
     *  Hash冲突测试  
        \*/  
        @Test  
        public void testHashConfilct() \{  
        HyhHashMap<String, String> hyhHashMap = new HyhHashMap<>();  
        hyhHashMap.put(“轷龚”, “heyuhua1”);  
        hyhHashMap.put(“轸齻”, “heyuhua2”);  
        System.out.println(“轷龚:” + hyhHashMap.get(“轷龚”) + “,轸齻:” + hyhHashMap.get(“轸齻”));  
        \}  
        \}  
        看下执行结果

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
看看Map里面的东西

不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）  
当然了，这花半个小时写的肯定会有bug，代码仅供参考，旨在让大家能够更加深入的了解HashMap原理。

六、HashMap常见面试题  
OK，大致的了解一下底层源码后，我们对HashMap有了一定深入的了解，接下来列举一些HashMap面试常问的问题

1.  HashMap的特性？

实现快速存储键值对，允许为null，key值不可重复，若key值重复则覆盖。  
线程不安全。  
底层是Hash表，不保证有顺序  
2. HashMap底层原理？

jdk7时采用数组+链表，jdk8后采用数组+链表+红黑树的数据结构。  
3. HashMap put原理？

当我们给put()方法传递键和值时，先对键做一个hashCode()的计算来得到它在bucket数组中的位置来存储Entry对象。  
4. HashMap get原理？

当获取对象时，通过get获取到bucket的位置，再通过键对象的equals()方法找到正确的键值对，然后再返回值对象。  
5. HashMap扩容机制？

扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。  
6. HashMap默认初始化长度为16，并且每次自动扩展或者是手动初始化容量时，为什么必须是2的次幂？

为了数据的均匀分布，减少哈希碰撞。因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。  
输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字  
7. HashMap大小超过了负载因子(load factor)定义的容量，怎么办？

超过阙值会进行扩容操作，概括的讲就是扩容后的数组大小是原数组的2倍，将原来的元素重新hashing放入到新的散列表中去。  
作者寄语  
路漫漫其修远兮，吾愿与君上下而求索，非常感谢各位帅哥、靓妹的点赞、收藏和评论，我们下期见。

作者：消灭知识盲区  
链接：https://juejin.cn/post/6927211419918319630  
来源：掘金