不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）
导读：前言朋友们又见面了，你是不是还在面试时被面试官问懵HashMap？不会手写实现一个简单HashMap？看完这篇文章你再不会算我输！提示：以下是本篇文章正文内容，案例仅供参考一、HashMap介绍1.HashMap是什么？基于哈希表的 Map...
前言
朋友们又见面了，你是不是还在面试时被面试官问懵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。
2.单向链表
单向链表是链表的一种，它由节点组成，每个节点都包含下一个节点的指针。
特点：
- 新增删除节点速方便、速度快，不需要像线性结构那样移动剩下的数据
- 查询较数组慢，需要通过循环或者递归的方法访问到任意数据，平均的访 问效率低于线性表
- 只能从头到尾遍历。只能找到后继，无法找到前驱，也就是只能前进。
适用于节点的增加删除。
3.双向链表
双向链表是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
特点：
- 有两个指针，一个指向前一个节点，一个指向后一个节点
- 可以找到前驱和后继，可进可退
- 增加删除节点复杂，需要多分配一个指针存储空间
4.红黑树
红黑树是一种特定类型的二叉树，也是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树，由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法。
特点：
- 每个节点只能是红色或者黑色。
- 根节点必须是黑色。
- 红色的节点，它的叶节点只能是黑色。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树
三、HashMap源码详解
OK，了解了以上数据结构后咱们再来看看HashMap底层源码是如何实现的, 先看下HashMap的存储结构
1.PUT操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
NodeK,V>
[] tab;
NodeK,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. 存在节点
NodeK,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 = ((TreeNodeK,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操作
final NodeK,V>
getNode(int hash, Object key) {
NodeK,V>
[] tab;
NodeK,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 ((TreeNodeK,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 TreeNodeK,V>
getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNodeK,V>
find(int h, Object k, Class?>
kc) {
TreeNodeK,V>
p = this;
do {
int ph, dir;
K pk;
TreeNodeK,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 NodeK,V>
[] resize() {
NodeK,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;
NodeK,V>
[] newTab = (NodeK,V>
[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//把 oldTab 中的节点 reHash 到 newTab 中去
for (int j = 0;
j oldCap;
++j) {
NodeK,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)
((TreeNodeK,V>
)e).split(this, newTab, j, oldCap);
//若是链表，进行链表的 rehash 操作
else {
// preserve order
NodeK,V>
loHead = null, loTail = null;
NodeK,V>
hiHead = null, hiTail = null;
NodeK,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(HashMapK,V>
map, NodeK,V>
[] tab, int index, int bit) {
TreeNodeK,V>
b = this;
// Relink into lo and hi lists, preserving order
TreeNodeK,V>
loHead = null, loTail = null;
TreeNodeK,V>
hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//由于TreeNode 节点之间存在双端链表的关系，可以利用链表关系进行 rehash
for (TreeNodeK,V>
e = b, next;
e != null;
e = next) {
next = (TreeNodeK,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 HyhMapK, 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 K>
* @param V>
*/
interface EntryK, 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 HyhHashMapK, V>
implements HyhMapK, V>
, Serializable {
/**
* 默认容量
*/
static final int DEFAULT_CAPACITY = 16;
int threshold;
/**
* 当前key索引位置
*/
int keyIndex;
/**
* 负载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 保存NodeK,V>
节点的数组
*/
NodeK, V>
[] table;
/**
* 存储当前Map容量的大小
*/
int size;
@Override
public void put(K key, V value) {
NodeK, V>
node;
if (table == null) {
table = resize();
//table里面为空的情况
node = new NodeK, V>
(hash(key), key, value, null);
table[keyIndex] = node;
size++;
}
else {
table = resize();
//table不为空时
NodeK, 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 NodeK, V>
(hash(key), key, value, null);
node.next = n;
table[i] = node;
size++;
}
n = n.next;
}
}
}
}
if (!hashConflict) {
//没有hash冲突，直接put
node = new NodeK, V>
(hash(key), key, value, null);
table[++keyIndex] = node;
size++;
}
}
}
@Override
public V get(K key) {
HyhHashMap.NodeK, V>
node;
return (node = getNode(key)) == null ? null : node.value;
}
/**
* 获取Node
*
* @param key
* @return
*/
final HyhHashMap.NodeK, V>
getNode(Object key) {
if (table != null) {
for (int i = 0;
i table.length;
i++) {
NodeK, 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 NodeK, V>
[] resize() {
NodeK, V>
[] newTable;
int newCapacity, oldCapacity;
if (table == null) {
keyIndex = 0;
threshold = (int) (DEFAULT_CAPACITY * DEFAULT_LOAD_FACTOR);
table = (HyhHashMap.NodeK, V>
[]) new HyhHashMap.Node[DEFAULT_CAPACITY];
newTable = table;
}
else {
oldCapacity = table.length;
if (table.length >
threshold) {
//扩容两倍
newCapacity = threshold *= 2;
newTable = (HyhHashMap.NodeK, V>
[]) new HyhHashMap.Node[newCapacity];
//把原来的table移动到newTable
int newIndex = 0;
for (int i = 0;
i oldCapacity;
i++) {
NodeK, V>
node = table[i];
//咱们这只使用最简单的方式、不考虑其他情况、不涉及红黑树
if (node != null) {
if (node.next == null)
newTable[newIndex] = node;
else {
HyhHashMap.NodeK, 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 K>
* @param V>
*/
static class NodeK, V>
implements HyhMap.EntryK, V>
{
//hash值
final int hash;
// key
final K key;
// value
V value;
// next节点
HyhHashMap.NodeK, V>
next;
public Node(int hash, K key, V value, NodeK, 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() {
HyhHashMapString, 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() {
HyhHashMapString, String>
hyhHashMap = new HyhHashMap>
();
hyhHashMap.put("轷龚", "heyuhua1");
hyhHashMap.put("轸齻", "heyuhua2");
System.out.println("轷龚:" + hyhHashMap.get("轷龚") + ",轸齻:" + hyhHashMap.get("轸齻"));
}
}
看下执行结果
看看Map里面的东西
当然了，这花半个小时写的肯定会有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放入到新的散列表中去。
作者寄语
路漫漫其修远兮，吾愿与君上下而求索，非常感谢各位帅哥、靓妹的点赞、收藏和评论，我们下期见。
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）
本文地址： https://pptw.com/jishu/2720.html