1.前言HashMap顾名思义，是利用哈希表原理实现的Map接口容器对象，那么什么是哈希表呢？我们都熟悉数组。数组是一种占用连续内存的数据结构。学过C的朋友，想必对此影响更深远。既然是连续内存，数组的特点就很明显了。一旦知道要检查哪些数据，时间复杂度就是O(1)，但是插入操作就非常困难了；还有一种数据结构你一定也非常熟悉。如果你熟悉它，它就是一个链表。链表是由一组指向（单向或双向）节点连接的数据结构。它的特点是内存不连续，不易查找，但易于插入和删除。有没有一种方便查找、插入、删除、查找的数据结构？是的，它是一个哈希表。在这篇文章中，我们来讨论一下：HashMap的数据结构实现方法。HashMap如何为get和put操作提供稳定的时间复杂度？为什么初始化树型HashMap的时候要给定一个自定义的初始容量。HashMap如何保证容量永远是2的幂？为什么HashMap保证容量永远是2的幂？如何计算HashMap的哈希值？源代码。2、HashMap的基本元素磨刀不误砍柴工。要想理解HashMap的原理，必须绕过HashMap源码中的以下变量：DEFAULT_INITIAL_CAPACITY：初始容量1<<4is16MAXIMUM_CAPACITY：最大容量1<<30。DEFAULT_LOAD_FACTOR：负载因子，默认为0.75。这是什么意思？比如你定义了一个初始容量为16的HashMap，当你继续往里面添加元素，直到达到初始容量的0.75时，HashMap就会触发一次扩容操作。threshold：下一个触发扩容操作的阈值，threshold=CAPACITY*LOAD_FACTOR。TREEIFY_THRESHOLD：链表转红黑树的阈值。默认8个，超过8个就会执行链表转红黑树的方法。但是注意，链表转红黑树的方法中，会判断当前size是否大于64，只有大于64才能转红黑树。否则，执行resize()操作。UNTREEIFY_THRESHOLD：红黑树转链表的阈值，默认为6，顾名思义，小于6的红黑树节点会转为链表。Node实现Map.EntryHashMap是存储数据的基本单元，包含hashvalue、key、value、next。Node[]表：存放Node节点的数组，HashMap的底层数组，数组元素可以是单节点Node、多节点链表或多节点红黑树。对以上内容有个印象就好了，没必要全部记住。但是这些概念对于理解HashMap是至关重要的。3.正文3.1HashMap数据结构HashMap的数据结构非常简单。是一个Node类型的数组，每个元素可以是单节点，也可以是多节点链表，也可以是多节点红黑树。关键问题是，这么简单的结构，怎么能这么快的实现put和get呢？什么时候单节点转链表，什么时候链表转红黑树？3.1.1HashMap是如何实现时间复杂度为O(1)~O(n)的put和get操作的？我们知道当我们不知道一个数组元素的索引时，复杂度是非常高的，但是当我们知道索引时，复杂度是O(1)级别的。HashMap就是利用了这个原理。对于get操作，首先根据key计算出hash值，hash值执行操作(n-1)&hash之后就是它所在的索引。在最好的情况下，索引恰好只有一个节点并且哈希值和key的哈希值相同，那么时间复杂度就是O(1)。当结点是链表或者红黑树时，时间复杂度会增加，但是由于HashMap的优化（链表长度和红黑树的长度不同容量HashMap会太长，太长会触发resize操作），所以最坏的情况是O(n)，有可能小于这个值。对于put操作，我们知道在数组中插入元素的代价是很高的。HashMap巧妙地使用了链表和红黑树来代替移动后续元素向数组插入元素的消耗。这样，在最好的情况下，插入一个元素，如果index位置没有元素，时间复杂度为O(1)，当该位置有元素，并且是链表或者red-黑树，时间复杂度会增加，但最坏情况下是O(n)。3.1.2HashMap什么时候从单节点转成链表，什么时候从链表转成红黑树？将单个节点转换为链表非常简单。当根据新增值计算出的索引处有元素时，如果该元素为单节点，则将该节点转为链表。链表转红黑树有两个条件：链表长度大于TREEIFY_THRESHOLD，默认阈值为8。HashMap的长度大于64。当满足这两个条件时同时会触发链表转红黑树的操作。3.2为什么初始化HashMap的时候需要给定一个自定义的初始容量？为什么前人要求在定义HashMap时，必须使用构造函数HashMap(intinitialCapacity)指定初始容量？在阿里的《Java开发手册》中有解释：【建议】在初始化集合的时候，指定集合的??初始值。注意：HashMap是用HashMap(intinitialCapacity)初始化的，正例：initialCapacity=(要存储的元素个数/加载因子)+1。注意加载因子(即加载因子)默认为0.75，如果初始值不能暂时确定，请设置为16（即默认值）。反例：HashMap需要放置1024个元素。由于容量的初始大小没有设置，随着元素的不断增加，容量被强制扩大7倍。resize需要重建哈希表，严重影响性能。这个问题在HashMap源码中表现的很明显。put函数每次检查当前大小是否大于阈值，如果大于则扩容，新容量是原来容量的2倍。那么问题来了。当你想在HashMap中存储大量数据而不指定初始容量时，扩容会陆续触发，性能消耗很大。关于初始容量和负载因子，如果日常开发中不需要，建议不要更改负载因子，而是根据要使用的HashMap的大小来确定初始容量。这并不意味着初始容量越大，越能避免膨胀。应用内存越大，内存越大。如果您没有那么多数据要存储，哈希值将过于离散。3.3HashMap如何保证容量总是2的幂HashMap使用tableSizeFor()方法来保证不管你给什么值，返回的值一定是2的幂：staticfinalinttableSizeFor(intcap){intn=上限-1；//功能：保证当cap是2的幂时，返回原值而不是double，比如8返回8而不是16n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16；返回（n<0）？1:(n>=MAXIMUM_CAPACITY)?最大容量：n+1；:n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16假设n=01000000,n|=n>>>1,n=01100000,n|=n>>>2,n=01111000,n|=n>>>4；在n=01111111之后，我们可以发现上面5步可以将一个首位为1的32位数字后面的所有位都变成1。这样，执行n+1操作后，这个数一定是一个幂of2。比如01111111+1=10000000。那为什么要保证一定是2的幂呢？这不是不可能吗？3.3.1HashMap为什么保证容量总是2的幂说到这个问题，就不得不说到执行put()方法时如何根据hash值在表中定位。finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){......if((p=tab[i=(n-1)&hash])==null)tab[i]=newNode(散列，键，值，空);...可以看到，它使用了一个(n-1)&hash操作，n是当前hashmap的容量，容量必须是2的n-1次方是1，例如：16=0000000000010000,15=0000000000001111,这样处理的好处是在进行(n-1)&hash操作时，元素的位置只取决于低位，与高位无关（这种无关性随着hashMap的容量），这样做的逻辑好处就是无论你的hash值有多大，我都锁定了你的取值范围小于当前的容量，这样做就避免了hash值过于离散的情况，而当HashMap扩展，同时可以增加哈希值的取值范围。缺点是增加了哈希冲突的可能性。为了解决这个问题，HashMap修改了哈希值的计算方式，增加了低哈希复杂度。3.3.2HashMap计算hash值废话不多说，直接上传源码：staticfinalinthash(Objectkey){inth;返回（键==空）？0:(h=key.hashCode())^(h>>>16);}hash方法使用key的hash值对key的hash值的高16位进行XOR。你为什么这么做？首先，h>>>16的值的高16位全为0，所以当h^(h>>>16)时，高16位的值不会改变，但是低16位的值与key16位值的高值混合，增加了hash值的复杂度，进一步降低了hash值相同的概率。3.4为什么HashMap不是线程安全的在Jdk1.7中，HashMap不是线程安全的原因之一就是传递函数。该函数使用headersearch的方式，在多线程的情况下很容易产生闭环链表，导致死循环。同时也存在数据丢失的问题。Jdk1.8中没有传递函数，而是在resize函数中完成HashMap扩容或初始化操作。resize使用尾部插入的方式解决了闭环链表的问题，但是依然无法避免数据覆盖。问题。在HashMap的put操作中：finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;节点p;诠释n,我;如果((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;......执行完if((tab=table)==null||(n=tab.length)==0)如果判断为真，则直接赋值，但是在多线程中环境，当两个线程同时完成判断时，线程1刚刚赋值完成后，线程2再次赋值，造成数据覆盖的问题。这只是最简单的现象。要想线程安全，首先要有多线程安全的处理逻辑。很明显，HashMap是没有这样的逻辑的，那么多为单线程设计的逻辑很可能会出问题，那么HashMap为什么是线程不安全的呢？本身设计不支持多线程运行，所以应该不会有这个问题。如果想以线程安全的方式使用基于哈希表的map，可以使用ConcurrentHashMap，它实现了一个无锁的get操作，对put操作实现了段锁，性能不错。因此，技术行业有分工，每种容器的实现都有其相应的优缺点。我们需要学习的是分析我们面临的每一种情况，合理使用不同的容器来解决问题。HashMap的基本原理和相应的实现就到此为止。红黑树插入节点、平衡红黑树、??遍历红黑树等更深入的话题，可以直接看红黑树对应的原理和实现。如果需要源码评论，请点这里源码分析最后，最近很多朋友找我要一份Linux学习路线图，于是结合自己的经验，利用业余时间熬夜一个月，整理了一份e-书。无论你是面试还是自我提升，相信都会对你有所帮助！免费送给大家，只求大家给我点个赞！电子书|LinuxDevelopmentLearningRoadmap也希望有小伙伴可以和我一起把这本电子书做得更完美！获得？希望老铁们来个三连击，让更多人看到这篇文章。推荐阅读：干货|程序员和高级架构师免费发送工件的必备资源|支持搜索的资源网站
