seo 网站文章一般要多少字,应用app官方下载,vs网站开发如何发布,网站备案购买#x1f4dd;个人主页#xff1a;哈__
期待您的关注 在Java中#xff0c;HashMap结构是被经常使用的#xff0c;在面试当中也是经常会被问到的。这篇文章我给大家分享一下我对于HashMap结构源码的理解。
HashMap的存储与一般的数组不同#xff0c;HashMap的每一个元素存… 个人主页哈__
期待您的关注 在Java中HashMap结构是被经常使用的在面试当中也是经常会被问到的。这篇文章我给大家分享一下我对于HashMap结构源码的理解。
HashMap的存储与一般的数组不同HashMap的每一个元素存储的并不是一个值而是一个引用类型的Node结点这也就意味着这个Node结点有被扩充的可能因为这个Node结点可以是一个链表的Head结点也可以是一棵树的根节点。
HashMap的存储数组叫做table也可以称作“桶”试想这样的一个场景我们在一排放了3个桶同时我们有4个苹果如果我们要把所有的苹果放到桶当中那么必然有一个桶中 的苹果个数2。 这种情况在我们的HashMap中也会出现我们的HashMap结构是把很多的数据存放到一个容量达不到元素个数的数组当中就如同桶和苹果一样。
因此我们的HashMap结果会出现上图所示的一种冲突我们成为散列冲突也叫做Hash冲突 。
出现冲突不要怕解决冲突就是了我们的一个桶当中可以放两个苹果自然HashMap的table数组的一个位置也可以存放两个元素。
问题来了我们现在假设有16个桶同时间断性的向桶中放苹果而且还要能够方便我们后续去拿苹果和寻找苹果那我们这16个桶还够用吗我们这样子直接把苹果放进桶里还能够方便我们后续找苹果吗
行了解决吧现在假设你是一位苹果管理员你该怎么优化一下你看看这样子行不行不就是放苹果、找苹果嘛既然让我来管理那我希望把苹果平均放到桶当中每次我放的位置尽量不要和之前的苹果放的位置有冲突如果桶多的话你也不能一个一个桶去看吧所以我们定义了一个算法我根据这个苹果的生产ID序列号去寻找对应的桶放进去如同取余放置一样。这是个不错的思路。但序列号都是有规律的这样会影响我们的放置我们希望是一个很随机的结果因此我们给这个序列号随机变动几个位置后在选择桶。在HashMap中这样的序列号叫做hashCode值经过一个扰动函数后我们的到的扰动的值叫做hash。
如何存放的问题解决了但苹果一旦多了还是会产生冲突一个桶里放8个我还能找得到但是一个桶里放20个30个苹果那我就找不到那个序列号的苹果了。
二叉树我们都学过倘若我们把桶内的苹果以二叉树的方式进行存储那这样我们在查找的时候是不是就省了很多时间呢因此HashMap中的table内的一个元素列表长度8的时候进行树化操作。但也不是非要进行树化的毕竟树化也要浪费很多资源。当我们的桶的数量64的时候我们不进行树化操作我们进行数组扩容把table扩大2倍这样的话我们在放苹果的时候发生冲突的概率就会降低。但如果容量已经达到了64我们就考虑把链表转为红黑树也是二叉树了。
以上的过程不知道你是否理解了没放苹果的案例和HashMap存储元素的过程相似现在我们来看代码吧。
一、HashMap中的变量
1.默认容量
HashMap无参构造方法调用时我们的HashMap数组的初始容量是16。 /*** 默认初始化的容量大小且必须是2的整数倍*/static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16
2.最大容量
记录了我们HashMap所能存储的最大的元素个数。 /*** 我们的元素数组的最大的容量如果我们设定的最大容量比这个数还大* 那我们就把容量设定为这个最大的值*/static final int MAXIMUM_CAPACITY 1 30;
3.负载因子
负载因子决定了HashMap在存储更多数据时如何扩展其容量。默认情况下当负载因子达到0.75时HashMap会进行扩容。这意味着当HashMap中的元素数量达到数组容量的0.75倍时数组的大小就会翻倍以便容纳更多的数据。
为什么选择0.75作为默认的负载因子呢这并不是随意的选择而是经过深思熟虑后的优化值。负载因子实际上是一个权衡空间和时间的参数。在理想情况下如果负载因子为1这意味着每个索引位置上都有一个键值对存在。然而当两个或更多的键具有相同的哈希值时就会发生冲突这会导致查询效率降低。因此通过设置一个适当的负载因子可以平衡键值对的存储效率和查询效率。
通过将负载因子设置为0.75可以在空间和时间效率之间取得平衡。这意味着当数组接近其容量时HashMap会进行扩容以避免因哈希冲突而导致的性能下降。同时这个值也避免了因频繁扩容而产生的额外开销。在大多数情况下0.75的负载因子可以提供较好的性能。 /*** 如果我们并没有自己初始化一个平衡因子这个就是默认的平衡因子*/static final float DEFAULT_LOAD_FACTOR 0.75f;
4.列表树化的阈值 /*** 当列表的长度超过了8达到9的时候就会把列表转为红黑树*/static final int TREEIFY_THRESHOLD 8;
5.红黑树转列表的阈值
一个桶里的苹果往外拿了很多就那么几个苹果我数的清用不到树了。 /*** 当树中的结点的个数小于6的时候我们就把红黑树转为列表了*/static final int UNTREEIFY_THRESHOLD 6;
6.树化时的最小数组容量 /*** 在我们的列表转为红黑树的时候如果我们的数组长度也就是容量达不到64那我们就扩充数组* 而不是进行红黑树的转化**/static final int MIN_TREEIFY_CAPACITY 64; 7.元素数组存放我们插入的数据
这就是我们的桶。 transient NodeK,V[] table;
8.数组的大小并非容量而是实际放了多少个数据结点到table数组中 /*** 此映射中包含的键值映射数。*/transient int size;
这些变量看完了之后我们在介绍一个结点类Node我们的元素在存储的时候都是这个类型。
9.Node结点 static class NodeK,V implements Map.EntryK,V {final int hash; //hash值final K key; //keyV value; //valueNodeK,V next; //记录下一个元素
}
10.扩容阈值
当table中的元素个数达到了这个值的时候进行resize操作并非所有node节点的个数而是我们的一维table中存放元素的个数(存放的链表和树算一个元素)。 /*** table中存放的元素的个数达到了这个值进行resize操作*/int threshold;
二、HashMap的put方法
我们只以无参构造的HashMap为例。 HashMapString,Integer map new HashMap();map.put(张三,18);
我们看看这个put方法到底干了些什么。
我们点进去这个put方法发现调用的是putVal方法这个方法有五个参数第一个参数传入了一个hash方法第二个就是我们的key第三个就是value而后边的两个是默认的boolean类型的值我们不看后边的两个。
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}
hash到底是什么我们上边其实也讲到过这是一个扰动函数意在把我们要插入的这个元素更加随机、均匀的分布到table中。想了解这个过程我们先往下走到了具体的位置在讲解。
我们看看这个putVal方法。代码倒是挺多的不过没关系你就看我写的注释。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//这里初始化了一个tab用于保存我们最终的结果 还有一个临时的结点pNodeK,V[] tab; NodeK,V p; int n, i;//这种写法要弄清是赋值是判断如果我们的table还没有初始化的话if ((tab table) null || (n tab.length) 0)//我们就把这个n记录成我们这个tab初始化后的大小n (tab resize()).length;//这里就是进行位置判断的代码了如果当前遍历的结点是个空的我们直接把node放到这个桶里if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else { //如果当前位置不为空//定义一个e结点用于遍历NodeK,V e; K k;//如果这个结点的key和我们插入元素的key相同那我们把这个e指向这个结点if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//但如果不同而且这个结点还是个树形结点我们调用专门的方法遍历树else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//如果不是树那就是链表了我们进行链表遍历去插入我们的新元素for (int binCount 0; ; binCount) {//如果我们遍历到的结点已经遍历完了那我们把元素插入if ((e p.next) null) {p.next newNode(hash, key, value, null);//如果达到了树化阈值那我们进行树化操作//这里注意一下为什么是-1因为我们从0开始遍历当我们达到了7说明已经遍历了8次同时上边进行了一次插入结点数达到了9if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//如果当前结点的key就是我们插入的key我们不做操作这是e是有指向的if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//如果e不是空就说明找到了一个key相同的结点我们进行value的替换if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);//替换后就return了不对table结构做影响return oldValue;}}//如果我们对table的结构影响了我们把这个值1modCount;//看看把这个值插进去之后是否达到了扩容阈值并不是table中元素的长度满了之后才扩容的if (size threshold)resize();afterNodeInsertion(evict);return null;} 在上方的代码中你看到了这样的代码。这样代码就是判断我们元素放到哪个位置的。我们用桶的容量去和hash值进行与操作。 (p tab[i (n - 1) hash
假设当前容量是16那么你看一下这个与操作的核心部分是什么n的前28位都是0与后的结果也是0所以真正影响元素位置的只有n的最后四位和元素hashcode的最后四位。结果也一定是0~15。 h.hashCode 1101 0111 1011 1100 0101 1011 1011 1010
n-1 0000 0000 0000 0000 0000 0000 0000 1111 那么扰动函数的作用是什么呢。我们上边的与操作只算了元素hashcode的后4位不够随机我们想要让hashcode的前16位也要影响最后的结果。所以就有了扰动函数。
static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}
h.hashCode 1101 0111 1011 1100 0101 1011 1011 1010
h.hashCode 16 0000 0000 0000 0000 1101 0111 1011 1100
我们取这两个值的与结果这样我们的hashcode的高位也能扰动我们放的位置。并非单纯的低位和n-1去进行与运算了。 三、resize方法
在上边的代码中有个resize方法的调用这个方法主要的目的是扩容table。这个resize方法看起来还是非常的恐怖哈。
resize方法解释了为什么数组的容量一定是二的整数倍。
final NodeK,V[] resize() {//记录一下之前的tableNodeK,V[] oldTab table;//算一下之前table的容量int oldCap (oldTab null) ? 0 : oldTab.length;//记录一下之前table的扩容阈值int oldThr threshold;//把新的容量和扩容阈值定义出来int newCap, newThr 0;//如果已经进行过初始化了if (oldCap 0) {//如果我们之前的空间大小已经达到了最大容量 -- 很少出现if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}//否则的话 我们新的容量等于旧的容量*2 位移运算else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)//新的扩容阈值也*2newThr oldThr 1; // double threshold}//这个先不说了else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;// 这个else重要啊如果我们没有进行过初始化那我们就把新容量定位16 新的扩容阈值定为12else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//如果新的扩容阈值等于0 我们要进行处理等于新的容量×负载因子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})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.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;}}}}}return newTab;}
我们分析一下下边的代码。写了注释的直接看看就好关于树的我不说了只说链表。
NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;//如果我们之前的table不为空的话我们要进行一下元素迁移if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;//如果当前结点不为空if ((e oldTab[j]) ! null) {//清空原来的table中的位置便于垃圾回收oldTab[j] null;//如果就一个node 把他搬到新的table中if (e.next null)newTab[e.hash (newCap - 1)] e;//如果是树形结点 调用split方法else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);//如果是个链表else { // preserve order// 低链表 NodeK,V loHead null, loTail null;//高链表NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;//判断这个结点放到高链表或者低链表中if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.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;}}}}} 什么是高链表和低链表。在之前我们说到过元素是如何定位的靠的是hash和数组容量-1的与操作。但如果我们数组容量不减1呢因为我们的数组容量是2的整数倍如果不减1那么就说明只有一个位置为1其他的全为0假设容量是16。 h.hashCode 1101 0111 1011 1100 0101 1011 1011 1010
n 0000 0000 0000 0000 0000 0000 0001 0000 如同上方的例子这个元素到底分到哪里就看这个元素的hash值的倒数第五位如果是1就在高链表如果是0就在低链表。我们通过这样的方式来把元素分到低链表或者高链表当中。
for循环的最后把我们这个临时的低链表和高链表放到我们新的table中。
最后将新的table返回。
