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

您所在的位置：网站首页 › 矿工生存3d内置功能菜单 › 不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）

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

#不怕面试再问HashMap，一次彻底地梳理（原理+手写实现）| 来源: 网络整理| 查看: 265

前言

朋友们又见面了，你是不是还在面试时被面试官问懵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) { Node[] tab; Node 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 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)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 Node getNode(int hash, Object 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) 　　　　　　　　　　　　//若定位到的节点是　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; } final TreeNode getTreeNode(int h, Object k) { return ((parent != null) ? root() : this).find(h, k, null); } final TreeNode find(int h, Object k, Class kc) { TreeNode p = this; do { int ph, dir; K pk; TreeNode 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[] resize() { Node[] 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 = DEFAULT_INITIAL_CAPACITY) newThr = oldThr

【本文地址】

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

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

今日新闻

推荐新闻