Hashmap面试题Hashmap原理Hashmap源码（史

　　HashMap作为我们日常使用最频繁的容器之一，相信你一定不陌生了。今天我们就从HashMap的底层实现讲起，深度了解下它的设计与优化。常用的数据结构
　　我在05讲分享List集合类的时候，讲过ArrayList是基于数组的数据结构实现的，LinkedList是基于链表的数据结构实现的，而我今天要讲的HashMap是基于哈希表的数据结构实现的。
　　我们不妨一起来温习下常用的数据结构，这样也有助于你更好地理解后面地内容。
　　数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O（1），但在数组中间以及头部插入数据时，需要复制移动后面的元素。
　　链表：一种在物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
　　链表由一系列结点（链表中每一个元素）组成，结点可以在运行时动态生成。每个结点都包含存储数据单元的数据域和存储下一个结点地址的指针域这两个部分。
　　由于链表不用必须按顺序存储，所以链表在插入的时候可以达到O（1）的复杂度，但查找一个结点或者访问特定编号的结点需要O（n）的时间。
　　哈希表：根据关键码值（Keyvalue）直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组就叫做哈希表。
　　树：由n（n1）个有限结点组成的一个具有层次关系的集合，就像是一棵倒挂的树。什么是哈希表
　　从根本上来说，一个哈希表包含一个数组，通过特殊的关键码（也就是key）来访问数组中的元素。
　　哈希表的主要思想是：存放Value的时候，通过一个哈希函数，通过关键码（key）进行哈希运算得到哈希值，然后得到映射的位置，去寻找存放值的地方，读取Value的时候，也是通过同一个哈希函数，通过关键码（key）进行哈希运算得到哈希值，然后得到映射的位置，从那个位置去读取。
　　最直接的例子就是字典，例如下面的字典图，如果我们要找啊这个字，只要根据拼音a去查找拼音索引，查找a在字典中的位置啊，这个过程就是哈希函数的作用，用公式来表达就是：f（key），而这样的函数所建立的表就是哈希表。
　　哈希表的优势：加快了查找的速度。
　　比起数组和链表查找元素时需要遍历整个集合的情况来说，哈希表明显方便和效率的多。常见的哈希算法
　　哈希表的组成取决于哈希算法，也就是哈希函数的构成，下面列举几种常见的哈希算法。1）直接定址法取关键字或关键字的某个线性函数值为散列地址。即f（key）key或f（key）akeyb，其中a和b为常数。2）除留余数法取关键字被某个不大于散列表长度m的数p求余，得到的作为散列地址。即f（key）keyp，pm。这是最为常见的一种哈希算法。3）数字分析法当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。4）平方取中法先计算出关键字值的平方，然后取平方值中间几位作为散列地址。随机分布的关键字，得到的散列地址也是随机分布的。5）随机数法选择一个随机函数，把关键字的随机函数值作为它的哈希值。通常当关键字的长度不等时用这种方法。什么是哈希冲突（hash碰撞）
　　哈希表因为其本身的结构使得查找对应的值变得方便快捷，但也带来了一些问题，
　　以上面的字典图为例，key中的一个拼音对应一个字，那如果字典中有两个字的拼音相同呢？
　　例如，我们要查找按这个字，根据字母拼音就会跳到安的位置，这就是典型的哈希冲突问题。
　　哈希冲突问题，用公式表达就是：key1key2，f（key1）f（key2）
　　一般来说，哈希冲突是无法避免的，
　　如果要完全避免的话，那么就只能一个字典对应一个值的地址，也就是一个字就有一个索引（安和按就是两个索引），
　　这样一来，空间就会增大，甚至内存溢出。
　　需要想尽办法，减少哈希冲突（hash碰撞）为啥呢？Hash碰撞的概率就越小，map的存取效率就会越高哈希冲突的解决办法
　　常见的哈希冲突解决办法有两种：开放地址法链地址法。一、开放地址法
　　开发地址法的做法是，当冲突发生时，使用某种探测算法在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。
　　按照探测序列的方法，一般将开放地址法区分为线性探查法、二次探查法、双重散列法等。
　　这里为了更好的展示三种方法的效果，我们用以一个模为8的哈希表为例，采用除留余数法，
　　往表中插入三个关键字分别为26，35，36的记录，分别除8取模后，在表中的位置如下：
　　这个时候插入42，那么正常应该在地址为2的位置里，但因为关键字30已经占据了位置，
　　所以就需要解决这个地址冲突的情况，接下来就介绍三种探测方法的原理，并展示效果图。1）线性探查法：
　　fi（f（key）i）m，0im1
　　探查时从地址d开始，首先探查T〔d〕，然后依次探查T〔d1〕，，直到T〔m1〕，此后又循环到T〔0〕，T〔1〕，，直到探查到有空余的地址或者到T〔d1〕为止。
　　插入42时，探查到地址2的位置已经被占据，接着下一个地址3，地址4，直到空位置的地址5，所以39应放入地址为5的位置。
　　缺点：需要不断处理冲突，无论是存入还是査找效率都会大大降低。
　　2）二次探查法
　　fi（f（key）di）m，0im1
　　探查时从地址d开始，首先探查T〔d〕，然后依次探查T〔ddi〕，di为增量序列12，12，22，22，，q2，q2且q12（m1），直到探查到有空余地址或者到T〔d1〕为止。
　　缺点：无法探查到整个散列空间。
　　所以插入42时，探查到地址2被占据，就会探查T〔212〕也就是地址3的位置，被占据后接着探查到地址7，然后插入。
　　3）双哈希函数探测法
　　fi（f（key）ig（key））m（i1，2，，m1）
　　其中，f（key）和g（key）是两个不同的哈希函数，m为哈希表的长度
　　步骤：
　　双哈希函数探测法，先用第一个函数f（key）对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数g（key）确定移动的步长因子，最后通过步长因子序列由探测函数寻找空的哈希地址。
　　比如，f（key）a时产生地址冲突，就计算g（key）b，则探测的地址序列为f1（ab）modm，f2（a2b）modm，，fm1（a（m1）b）m，假设b为3，那么关键字42应放在5的位置。
　　开发地址法的问题：
　　开发地址法，通过持续的探测，最终找到空的位置。
　　上面的例子中，开发地址方虽然解决了问题，但是26和42，占据了一个数组同一个元素，42只能向下，此时再来一个取余为2的值呢，只能向下继续寻找，同理，每一个来的值都只能向下寻找。
　　为了解决这个问题，引入了链地址法。二、链地址法：
　　在哈希表每一个单元中设置链表，某个数据项对的关键字还是像通常一样映射到哈希表的单元中，而数据项本身插入到单元的链表中。
　　链地址法简单理解如下：
　　来一个相同的数据，就将它插入到单元对应的链表中，在来一个相同的，继续给链表中插入。
　　链地址法解决哈希冲突的例子如下：
　　（1）采用除留余数法构造哈希函数，而冲突解决的方法为链地址法。
　　（2）具体的关键字列表为（19，14，23，01，68，20，84，27，55，11，10，79），则哈希函数为H（key）keyMOD13。则采用除留余数法和链地址法后得到的预想结果应该为：
　　（3）哈希造表完成后，进行查找时，首先是根据哈希函数找到关键字的位置链，然后在该链中进行搜索，如果存在和关键字值相同的值，则查找成功，否则若到链表尾部仍未找到，则该关键字不存在。哈希表性能
　　哈希表的特性决定了其高效的性能，大多数情况下查找元素的时间复杂度可以达到O（1），时间主要花在计算hash值上，
　　然而也有一些极端的情况，最坏的就是hash值全都映射在同一个地址上，这样哈希表就会退化成链表，例如下面的图片：
　　当hash表变成图2的情况时，查找元素的时间复杂度会变为O（n），效率瞬间低下，
　　所以，设计一个好的哈希表尤其重要，如HashMap在jdk1。8后引入的红黑树结构就很好的解决了这种情况。HashMap的类结构类继承关系
　　Java为数据结构中的映射定义了一个接口java。util。Map，此接口主要有四个常用的实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap，
　　类继承关系如下图所示：
　　下面针对各个实现类的特点做一些说明：（1）HashMap：
　　它根据键的hashCode值存储数据，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。
　　HashMap最多只允许一条记录的键为null，允许多条记录的值为null。
　　HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。
　　如果需要满足线程安全，可以用：Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。（2）Hashtable：
　　Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的。
　　这个是老古董，Hashtable不建议在代码中使用，
　　不需要线程安全的场合可以用HashMap替换，需要线程安全的场合可以用ConcurrentHashMap替换。
　　为何不建议用呢？
　　任一时间只有一个线程能写Hashtable，并发性不如ConcurrentHashMap。后者使用了分段保护机制，也就是分而治之的思想。（3）LinkedHashMap：
　　LinkedHashMap是HashMap的一个子类，其优点在于：保存了记录的插入顺序，
　　在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。（4）TreeMap：
　　TreeMap实现SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，
　　当用Iterator遍历TreeMap时，得到的记录是排过序的。
　　如果使用排序的映射，建议使用TreeMap。
　　在使用TreeMap时，key必须实现Comparable接口，或者在构造TreeMap传入自定义的Comparator，
　　否则会在运行时抛出java。lang。ClassCastException类型的异常。
　　注意：
　　对于上述四种Map类型的类，要求映射中的key是不可变的。
　　在创建内部的Entry后，key的哈希值不会被改变。
　　为啥呢？
　　如果对象的哈希值发生变化，Map对象很可能就定位不到映射的位置了。staticclassNodeK，VimplementsMap。EntryK，V｛key的哈希值不会被改变finalK映射中的key是不可变的VNodeK，VHashMap存储结构
　　通过上面的比较，我们知道了HashMap是Java的Map家族中一个普通成员，鉴于它可以满足大多数场景的使用条件，所以是使用频度最高的一个。
　　下文我们主要结合源码，从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。HashMap的重要属性：table桶数组
　　从HashMap的源码中，我们可以发现，HashMap有一个非常重要的属性table，
　　这是由一个Node类型的元素构成的数组：transientNodeK，V〔〕
　　table也叫哈希数组，哈希槽位数组，table桶数组，散列表，数组中的一个元素，常常被称之为一个槽位slot
　　Node类作为HashMap中的一个内部类，每个Node包含了一个keyvalue键值对。staticclassNodeK，VimplementsMap。EntryK，V｛finalKVNodeK，VNode（inthash，Kkey，Vvalue，NodeK，Vnext）｛this。this。this。this。｝publicfinalinthashCode（）｛returnObjects。hashCode（key）Objects。hashCode（value）；｝。。。。。。。。。。｝
　　Node类作为HashMap中的一个内部类，除了key、value两个属性外，还定义了一个next指针。
　　next指针的作用：链地址法解决哈希冲突。
　　当有哈希冲突时，HashMap会用之前数组当中相同哈希值对应存储的Node对象，通过指针指向新增的相同哈希值的Node对象的引用。JDK1。8的table结构图
　　从结构实现来讲，HashMap是数组链表红黑树（JDK1。8增加了红黑树部分）实现的，如下如所示。
　　问题：
　　HashMap的有什么特点呢？HashMap的有什么特点（1）HashMap采用了链地址法解决冲突
　　HashMap就是使用哈希表来存储的。
　　Node是HashMap的一个内部类，实现了Map。Entry接口，本质是就是一个映射（键值对）。
　　上图中的每个黑色圆点就是一个Node对象。
　　Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。
　　在每个数组元素上都一个链表结构，当数据被Hash后，首先得到数组下标，然后，把数据放在对应下标元素的链表上。
　　例如程序执行下面代码：map。put（keyA，value1）；map。put（keyB，value2）；
　　对于第一句，系统将调用keyA的hashCode（）方法得到其hashCode，然后再通过Hash算法来定位该键值对的存储位置，然后将构造entry后加入到存储位置指向的链表中
　　对于第一句，系统将调用keyB的hashCode（）方法得到其hashCode，然后再通过Hash算法来定位该键值对的存储位置，然后将构造entry后加入到存储位置指向的链表中
　　有时两个key会定位到相同的位置，表示发生了Hash碰撞。
　　Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。（2）HashMap有较好的Hash算法和扩容机制
　　哈希桶数组的大小，在空间成本和时间成本之间权衡，时间和空间之间进行权衡：如果哈希桶数组很大，即使较差的Hash算法也会比较分散，空间换时间如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，时间换空间
　　所以，就需要在空间成本和时间成本之间权衡，
　　其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。
　　那么通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node〔〕table）占用空间又少呢？
　　答案就是好的Hash算法和扩容机制。HashMap的重要属性：加载因子（loadFactor）和边界值（threshold）
　　HashMap还有两个重要的属性：加载因子（loadFactor）边界值（threshold）。
　　在初始化HashMap时，就会涉及到这两个关键初始化参数。
　　loadFactor和threshold的源码如下：所能容纳的keyvalue对极限finalfloatloadF负载因子
　　Node〔〕table的初始化长度length（默认值是16），
　　loadFactor为负载因子（默认值是0。75），
　　threshold是HashMap所能容纳的最大数据量的Node个数。threshold、length、loadFactor三者之间的关系：thresholdlengthLoadfactor。
　　默认情况下threshold160。7512。
　　threshold就是允许的哈希数组最大元素数目，超过这个数目就重新resize（扩容），扩容后的哈希数组容量length是之前容量length的两倍。
　　threshold是通过初始容量和LoadFactor计算所得，在初始HashMap不设置参数的情况下，默认边界值为12。
　　如果HashMap中Node的数量超过边界值，HashMap就会调用resize（）方法重新分配table数组。
　　这将会导致HashMap的数组复制，迁移到另一块内存中去，从而影响HashMap的效率。HashMap的重要属性：loadFactor属性
　　为什么loadFactor默认是0。75这个值呢？
　　loadFactor也是可以调整的，默认是0。75，但是，如果loadFactor负载因子越大，在数组定义好length长度之后，所能容纳的键值对个数越多。
　　LoadFactor属性是用来间接设置Entry数组（哈希表）的内存空间大小，在初始HashMap不设置参数的情况下，默认LoadFactor值为0。75。
　　为什么loadFactor默认是0。75这个值呢？
　　这是由于加载因子的两面性导致的
　　加载因子越大，对空间的利用就越充分，碰撞的机会越高，这就意味着链表的长度越长，查找效率也就越低。
　　因为对于使用链表法的哈希表来说，查找一个元素的平均时间是O（1n），这里的n指的是遍历链表的长度，
　　如果设置的加载因子太小，那么哈希表的数据将过于稀疏，对空间造成严重浪费。
　　当然，加载因子小，碰撞的机会越低，查找的效率就搞，性能就越好。
　　默认的负载因子0。75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下。
　　分为两种情况：如果内存空间很多而又对时间效率要求很高，可以降低负载因子Loadfactor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。HashMap的重要属性：size属性
　　size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。
　　注意：size和table的长度length的区别，length是哈希桶数组table的长度
　　在HashMap中，哈希桶数组table的长度length大小必须为2的n次方，这是一定是一个合数，这是一种反常规的设计。
　　常规的设计是把桶数组的大小设计为素数。相对来说素数导致冲突的概率要小于合数，
　　比如，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。
　　HashMap采用这种非常规设计，主要是为了方便扩容。
　　而HashMap为了减少冲突，采用另外的方法规避：计算哈希桶索引位置时，哈希值的高位参与运算。HashMap的重要属性：modCount属性
　　我们能够发现，在集合类的源码里，像HashMap、TreeMap、ArrayList、LinkedList等都有modCount属性，字面意思就是修改次数，
　　首先看一下源码里对此属性的注释
　　HashMap部分源码：ThenumberoftimesthisHashMaphasbeenstructurallymodifiedStructuralmodificationsarethosethatchangethenumberofmappingsintheHashMaporotherwisemodifyitsinternalstructure（e。g。，rehash）。ThisfieldisusedtomakeiteratorsonCollectionviewsoftheHashMapfailfast。（SeeConcurrentModificationException）。transientintmodC
　　汉译：此哈希表已被结构性修改的次数，结构性修改是指哈希表的内部结构被修改，比如桶数组被修改或者拉链被修改。
　　那些更改桶数组或者拉链的操作如，重新哈希。此字段用于HashMap集合迭代器的快速失败。
　　所以，modCount主要是为了防止在迭代过程中某些原因改变了原集合，导致出现不可预料的情况，从而抛出并发修改异常，
　　这可能也与FailFast机制有关：在可能出现错误的情况下提前抛出异常终止操作。
　　HashMap的remove方法源码（部分截取）：if（node！null（！matchValue（vnode。value）value（value！nullvalue。equals（v））））｛if（nodeinstanceofTreeNode）（（TreeNodeK，V）node）。removeTreeNode（this，tab，movable）；elseif（nodep）tab〔index〕node。elsep。nextnode。modC进行了modCount自增操作afterNodeRemoval（node）；
　　remove方法则进行了modCount自增操作，
　　然后来看一下HashMap的put方法源码（部分截取）：if（e！null）｛existingmappingforkeyVoldValuee。if（！onlyIfAbsentoldValuenull）e。afterNodeAccess（e）；returnoldV｝｝modC对于之前不存在的key进行put的时候，对modCount有修改if（sizethreshold）resize（）；afterNodeInsertion（evict）；
　　对于已经存在的key进行put修改value的时候，对modCount没有修改，
　　对于之前不存在的key进行put的时候，对modCount有修改，
　　通过比较put方法和remove方法可以看出，所以只有当对HashMap元素个数产生影响的时候才会修改modCount。
　　也是是说：modCount表示HashMap集合的元素个数，导致集合的结构发生变化。
　　那么修改modCount有什么用呢？
　　这里用HashMap举例，大家知道当用迭代器遍历HashMap的时候，调用HashMap。remove方法时，
　　会产并发修改的异常ConcurrentModificationException
　　这是因为remove改变了HashMap集合的元素个数，导致集合的结构发生变化。publicstaticvoidmain（Stringargs〔〕）｛MapString，StringmapnewHashMap（）；map。put（1，zhangsan）；map。put（2，lisi）；map。put（3，wangwu）；IteratorStringiteratormap。keySet（）。iterator（）；while（iterator。hasNext（））｛Stringnameiterator。next（）；map。remove（1）；｝｝
　　执行结果：抛出ConcurrentModificationException异常Exceptioninthreadmainjava。util。ConcurrentModificationExceptionatjava。util。HashMapHashIterator。nextNode（HashMap。java：1442）atjava。util。HashMapKeyIterator。next（HashMap。java：1466）atcom。cesec。springboot。system。service。Test。main（Test。java：14）
　　我们看一下抛出异常的KeyIterator。next（）方法源码：finalclassKeyIteratorextendsHashIteratorimplementsIteratorK｛publicfinalKnext（）｛returnnextNode（）。｝｝finalNodeK，VnextNode（）｛NodeK，V〔〕t；NodeK，Vif（modCount！expectedModCount）判断modCount和expectedModCount是否一致thrownewConcurrentModificationException（）；if（enull）thrownewNoSuchElementException（）；if（（next（currente）。next）null（ttable）！null）｛do｛｝while（indext。length（nextt〔index〕）null）；｝｝
　　在迭代器初始化时，会赋值expectedModCount，
　　在迭代过程中判断modCount和expectedModCount是否一致，如果不一致则抛出异常，
　　可以看到KeyIterator。next（）调用了nextNode（）方法，nextNode（）方法中进行了modCount与expectedModCount判断。
　　这里更详细的说明一下，在迭代器初始化时，赋值expectedModCount，
　　假设与modCount相等，都为0，在迭代器遍历HashMap每次调用next方法时都会判断modCount和expectedModCount是否相等，
　　当进行remove操作时，modCount自增变为1，而expectedModCount仍然为0，再调用next方法时就会抛出异常。需要通过迭代器的删除方法进行删除
　　所以迭代器遍历时，如果想删除元素，需要通过迭代器的删除方法进行删除，这样下一次迭代操作，才不会抛出并发修改的异常ConcurrentModificationException
　　那么为什么通过迭代器删除就可以呢？
　　HashIterator的remove方法源码：publicfinalvoidremove（）｛NodeK，Vif（pnull）thrownewIllegalStateException（）；if（modCount！expectedModCount）thrownewConcurrentModificationException（）；Kkeyp。removeNode（hash（key），key，null，false，false）；expectedModCountmodC｝
　　通过迭代器进行remove操作时，会重新赋值expectedModCount。
　　这样下一次迭代操作，才不会抛出并发修改的异常ConcurrentModificationExceptionhashmap属性总结
　　HashMap通过哈希表数据结构的形式来存储键值对，这种设计的好处就是查询键值对的效率高。
　　我们在使用HashMap时，可以结合自己的场景来设置初始容量和加载因子两个参数。当查询操作较为频繁时，我们可以适当地减少加载因子；如果对内存利用率要求比较高，我可以适当的增加加载因子。
　　我们还可以在预知存储数据量的情况下，提前设置初始容量（初始容量预知数据量加载因子）。这样做的好处是可以减少resize（）操作，提高HashMap的效率。
　　HashMap还使用了数组链表这两种数据结构相结合的方式实现了链地址法，当有哈希值冲突时，就可以将冲突的键值对链成一个链表。
　　但这种方式又存在一个性能问题，如果链表过长，查询数据的时间复杂度就会增加。HashMap就在Java8中使用了红黑树来解决链表过长导致的查询性能下降问题。以下是HashMap的数据结构图：HashMap源码分析HashMap构造方法：
　　HashMap有两个重要的属性：加载因子（loadFactor）和边界值（threshold）。
　　loadFactor属性是用来间接设置Entry数组（哈希表）的内存空间大小，在初始HashMap不设置参数的情况下，默认loadFactor为0。75。
　　为什么是0。75这个值呢？
　　这是因为对于使用链表法的哈希表来说，查找一个元素的平均时间是O（1n），这里的n指的是遍历链表的长度，
　　因此加载因子越大，对空间的利用就越充分，这就意味着链表的长度越长，查找效率也就越低。
　　如果设置的加载因子太小，那么哈希表的数据就过于稀疏，对空间造成严重浪费。
　　有什么办法可以来解决因链表过长而导致的查询时间复杂度高的问题呢？
　　在JDK1。8后就使用了将链表转换为红黑树来解决这个问题。
　　Entry数组（哈希槽位数组）的threshold阈值是通过初始容量和loadFactor计算所得，
　　在初始HashMap不设置参数的情况下，默认边界值为12（160。75）。
　　如果我们在初始化时，设置的初始化容量较小，HashMap中Node的数量超过边界值，HashMap就会调用resize（）方法重新分配table数组。
　　这将导致HashMap的数组复制，迁移到另一块内存中去，从而影响HashMap的效率。publicHashMap（）｛默认初始容量为16，加载因子为0。75this。loadFactorDEFAULTLOADFACTOR；allotherfieldsdefaulted｝publicHashMap（intinitialCapacity）｛指定初始容量为initialCapacitythis（initialCapacity，DEFAULTLOADFACTOR）；｝staticfinalintMAXIMUMCAPACITY130；最大容量当size到达threshold这个阈值时会扩容，下一次扩容的值，根据capacityloadfactor进行计算，由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）通过5次无符号移位运算以及或运算得到：n第一次右移一位时，相当于将最高位的1右移一位，再和原来的n取或，就将最高位和次高位都变成1，也就是两个1；第二次右移两位时，将最高的两个1向右移了两位，取或后得到四个1；依次类推，右移16位再取或就能得到32个1；最后通过加一进位得到2n。比如initialCapacity10，那就返回16，initialCapacity17，那么就返回3210的二进制是1010，减1就是1001第一次右移取或：100101001101；第二次右移取或：110100111111；第三次右移取或：111100001111；第四次第五次同理最后得到n1111，返回值是n12416；让cap1再赋值给n的目的是另找到的目标值大于或等于原值。这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。例如十进制数值8，二进制为1000，如果不对它减1而直接操作，将得到答案10000，即16。显然不是结果。减1后二进制为111，再进行操作则会得到原来的数值1000，即8。问题：tableSizeFor（）最后赋值给threshold，但threshold是根据capacityloadfactor进行计算的，这是不是有问题？注意：在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在put方法中会对threshold重新计算。问题：既然put会重新计算threshold，那么在构造初始化threshold的作用是什么？答：在put时，会对table进行初始化，如果threshold大于0，会把threshold当作数组的长度进行table的初始化，否则创建的table的长度为16。staticfinalinttableSizeFor（intcap）｛intncap1；nn1；nn2；nn4；nn8；nn16；return（n0）？1：（nMAXIMUMCAPACITY）？MAXIMUMCAPACITY：n1；｝publicHashMap（intinitialCapacity，floatloadFactor）｛指定初始容量和加载因子if（initialCapacity0）thrownewIllegalArgumentException（Illegalinitialcapacity：initialCapacity）；if（initialCapacityMAXIMUMCAPACITY）大于最大容量，设置为最大容量initialCapacityMAXIMUMCAPACITY；if（loadFactor0Float。isNaN（loadFactor））加载因子小于等于0或为NaN抛出异常thrownewIllegalArgumentException（Illegalloadfactor：loadFactor）；this。loadFactorloadFthis。thresholdtableSizeFor（initialCapacity）；边界值｝put方法源码：
　　当将一个keyvalue对添加到HashMap中，首先会根据该key的hashCode（）返回值，再通过hash（）方法计算出hash值，再除留余数法，取得余数，这里通过位运算来完成。putVal方法中的（n1）hash就是hash值除以n留余数，n代表哈希表的长度。余数（n1）hash决定该Node的存储位置，哈希表习惯将长度设置为2的n次方，这样可以恰好保证（n1）hash计算得出的索引值总是位于table数组的索引之内。publicVput（Kkey，Vvalue）｛returnputVal（hash（key），key，value，false，true）；｝hash计算：
　　key的hash值高16位不变，低16位与高16位异或，作为key的最终hash值。staticfinalinthash（Objectkey）｛return（keynull）？0：（hkey。hashCode（））（h16）；｝要点1：h16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。要点2：异或的运算法则为：000，101，011，110（同为0，异为1）
　　即取int类型的一半，刚好可以将该二进制数对半切开，
　　利用异或运算（如果两个数对应的位置相反，则结果为1，反之为0），这样可以避免哈希冲突。
　　底16位与高16位异或，其目标：
　　尽量打乱hashCode真正参与运算的低16位，减少hash碰撞。
　　之所以要无符号右移16位，是跟table的下标有关，位置计算方式是：
　　（n1）hash计算Node的存储位置
　　假如n16，从下图可以看出：
　　table的下标仅与hash值的低n位有关，hash值的高位都被与操作置为0了，只有hash值的低4位参与了运算。
　　putVal方法源码
　　putVal：
　　而当链表长度太长（默认超过8）时，链表就进行转换红黑树的操作。
　　这里利用红黑树快速增删改查的特点，提高HashMap的性能。
　　当红黑树结点个数少于6个的时候，又会将红黑树转化为链表。
　　因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。
　　finalVputVal（inthash，Kkey，Vvalue，booleanonlyIfAbsent，booleanevict）｛NodeK，V〔〕NodeK，Vp；intn，i；此时table尚未初始化，通过resize方法得到初始化的tableif（（tabtable）null（ntab。length）0）n（tabresize（））。（n1）hash计算Node的存储位置，如果判断Node不在哈希表中（链表的第一个节点位置），新增一个Node，并加入到哈希表中if（（ptab〔i（n1）hash〕）null）tab〔i〕newNode（hash，key，value，null）；else｛hash冲突了NodeK，Ve；Kk；if（p。hashhash（（kp。key）key（key！nullkey。equals（k））））判断key的条件是key的hash相同和eqauls方法符合，p。key等于插入的key，将p的引用赋给eelseif（pinstanceofTreeNode）p是红黑树节点，插入后仍然是红黑树节点，所以直接强制转型p后调用putTreeVal，返回的引用赋给ee（（TreeNodeK，V）p）。putTreeVal（this，tab，hash，key，value）；else｛链表循环，直到链表中的某个节点为null，或者某个节点hash值和给定的hash值一致且key也相同，则停止循环。for（intbinCount0；；binCount）｛binCount是一个计数器，来计算当前链表的元素个数if（（ep。next）null）｛next为空，将添加的元素置为nextp。nextnewNode（hash，key，value，null）；插入成功后，要判断是否需要转换为红黑树，因为插入后链表长度1，而binCount并不包含新节点，所以判断时要将临界阀值1。【链表长度达到了阀值TREEIFYTHRESHOLD8，即链表长度达到了7】if（binCountTREEIFYTHRESHOLD1）1for1st如果链表长度达到了8，且数组长度小于64，那么就重新散列resize（），如果大于64，则创建红黑树，将链表转换为红黑树treeifyBin（tab，hash）；结束循环｝节点hash值和给定的hash值一致且key也相同，停止循环if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））如果给定的hash值不同或者key不同。将next值赋给p，为下次循环做铺垫。即结束当前节点，对下一节点进行判断｝｝如果e不是null，该元素存在了（也就是key相等）if（e！null）｛existingmappingforkey取出该元素的值VoldValuee。如果onlyIfAbsent是true，就不用改变已有的值；如果是false（默认），或者value是null，将新的值替换老的值if（！onlyIfAbsentoldValuenull）e。什么都不做afterNodeAccess（e）；返回旧值returnoldV｝｝修改计数器1，为迭代服务modC达到了边界值，需要扩容if（sizethreshold）resize（）；什么都不做afterNodeInsertion（evict）；返回｝get方法源码：
　　当HashMap只存在数组，而数组中没有Node链表时，是HashMap查询数据性能最好的时候。
　　一旦发生大量的哈希冲突，就会产生Node链表，这个时候每次查询元素都可能遍历Node链表，从而降低查询数据的性能。
　　特别是在链表长度过长的情况下，性能明显下降，使用红黑树就很好地解决了这个问题，
　　红黑树使得查询的平均复杂度降低到了O（log（n）），链表越长，使用红黑树替换后的查询效率提升就越明显。
　　publicVget（Objectkey）｛NodeK，Ve；return（egetNode（hash（key），key））null？null：e。｝finalNodeK，VgetNode（inthash，Objectkey）｛NodeK，V〔〕NodeK，Vfirst，e；Kk；数组不为null，数组长度大于0，根据hash计算出来的槽位的元素不为nullif（（tabtable）！null（ntab。length）0（firsttab〔（n1）hash〕）！null）｛查找的元素在数组中，返回该元素if（first。hashhashalwayscheckfirstnode（（kfirst。key）key（key！nullkey。equals（k））））if（（efirst。next）！null）｛查找的元素在链表或红黑树中if（firstinstanceofTreeNode）元素在红黑树中，返回该元素return（（TreeNodeK，V）first）。getTreeNode（hash，key）；do｛遍历链表，元素在链表中，返回该元素if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））｝while（（ee。next）！null）；｝｝找不到返回｝remove方法源码：
　　publicVremove（Objectkey）｛NodeK，Ve；return（eremoveNode（hash（key），key，null，false，true））null？null：e。｝finalNodeK，VremoveNode（inthash，Objectkey，Objectvalue，booleanmatchValue，booleanmovable）｛NodeK，V〔〕NodeK，Vp；intn，数组不为null，数组长度大于0，要删除的元素计算的槽位有元素if（（tabtable）！null（ntab。length）0（ptab〔index（n1）hash〕）！null）｛NodeK，Vnodenull，e；Kk；Vv；当前元素在数组中if（p。hashhash（（kp。key）key（key！nullkey。equals（k））））元素在红黑树或链表中elseif（（ep。next）！null）｛if（pinstanceofTreeNode）是树节点，从树种查找节点node（（TreeNodeK，V）p）。getTreeNode（hash，key）；else｛do｛hash相同，并且key相同，找到节点并结束if（e。hashhash（（ke。key）key（key！nullkey。equals（k））））｛｝｝while（（ee。next）！null）；遍历链表｝｝找到节点了，并且值也相同if（node！null（！matchValue（vnode。value）value（value！nullvalue。equals（v））））｛if（nodeinstanceofTreeNode）是树节点，从树中移除（（TreeNodeK，V）node）。removeTreeNode（this，tab，movable）；elseif（nodep）节点在数组中，tab〔index〕node。当前槽位置为null，node。next为nullelse节点在链表中p。nextnode。将节点删除modC修改计数器1，为迭代服务数量1afterNodeRemoval（node）；什么都不做返回删除的节点｝｝｝containsKey方法：publicbooleancontainsKey（Objectkey）｛returngetNode（hash（key），key）！查看上面的get的getNode｝containsValue方法：publicbooleancontainsValue（Objectvalue）｛NodeK，V〔〕Vv；数组不为null并且长度大于0if（（tabtable）！nullsize0）｛for（inti0；itab。i）｛对数组进行遍历for（NodeK，Vetab〔i〕；e！ee。next）｛当前节点的值等价查找的值，返回trueif（（ve。value）value（value！nullvalue。equals（v）））｝｝｝找不到返回false｝putAll方法：
　　publicvoidputAll（M？extendsK，？extendsVm）｛putMapEntries（m，true）；｝finalvoidputMapEntries（M？extendsK，？extendsVm，booleanevict）｛intsm。size（）；获得插入整个m的元素数量if（s0）｛if（tablenull）｛presize，当前map还没有初始化数组floatft（（float）sloadFactor）1。0F；m的容量判断容量是否大于最大值MAXIMUMCAPACITYintt（（ft（float）MAXIMUMCAPACITY）？（int）ft：MAXIMUMCAPACITY）；容量达到了边界值，比如插入的m的定义容量是16，但当前map的边界值是12，需要对当前map进行重新计算边界值if（tthreshold）thresholdtableSizeFor（t）；重新计算边界值｝elseif（sthreshold）存放的数量达到了边界值，扩容resize（）；对m进行遍历，放到当前map中for（Map。E？extendsK，？extendsVe：m。entrySet（））｛Kkeye。getKey（）；Vvaluee。getValue（）；putVal（hash（key），key，value，false，evict）；｝｝｝clear方法：publicvoidclear（）｛NodeK，V〔〕modC修改计数器1，为迭代服务if（（tabtable）！nullsize0）｛size0；将数组的元素格式置为0，然后遍历数组，将每个槽位的元素置为nullfor（inti0；itab。i）tab〔i〕｝｝replace方法：publicbooleanreplace（Kkey，VoldValue，VnewValue）｛NodeK，Ve；Vv；根据hash计算得到槽位的节点不为null，并且节点的值等于旧值if（（egetNode（hash（key），key））！null（（ve。value）oldValue（v！nullv。equals（oldValue））））｛e。valuenewV覆盖旧值afterNodeAccess（e）；｝｝publicVreplace（Kkey，Vvalue）｛NodeK，Ve；根据hash计算得到槽位的节点不为nullif（（egetNode（hash（key），key））！null）｛VoldValuee。节点的旧值e。覆盖旧值afterNodeAccess（e）；returnoldV返回旧值｝找不到key对应的节点｝HashMap要点分析HashMap允许键值对为
　　HashMap允许键值对为
　　HashTable则不允许，会报空指针异常；HashMapString，StringmapnewHashMap（2）；map。put（null，null）；map。put（1，null）；HashMap是由一个Node数组组成的，每个Node包含了一个keyvalue键值对：transientNodeK，V〔〕
　　Node类作为HashMap中的一个内部类，除了key、value两个属性外，还定义了一个next指针，当有哈希冲突时，
　　HashMap会用之前数组当中相同哈希值对应存储的Node对象，通过指针指向新增的相同哈希值的Node对象的引用。staticclassNodeK，VimplementsMap。EntryK，V｛finalKVNodeK，VNode（inthash，Kkey，Vvalue，NodeK，Vnext）｛this。this。this。this。｝publicfinalinthashCode（）｛returnObjects。hashCode（key）Objects。hashCode（value）；｝。。。。。。。。。。｝HashMap初始容量是16，扩容方式为2N：
　　在JDK1。7中，HashMap整个扩容过程就是：
　　分别取出数组元素，一般该元素是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的hash值计算其在新数组中的下标，然后进行交换。
　　这样的扩容方式，会将原来哈希冲突的单向链表尾部，变成扩容后单向链表的头部。
　　而在JDK1。8后，HashMap对扩容操作做了优化。
　　由于扩容数组的长度是2倍关系，
　　所以对于假设初始tableSize4要扩容到8来说就是0100到1000的变化（左移一位就是2倍），
　　在扩容中只用判断原来的hash值和oldCap（旧数组容量）按位与操作是0或1就行：0的话索引不变，1的话索引变成原索引加扩容前数组。
　　之所以能通过这种与运算来重新分配索引，
　　是因为hash值本来是随机的，而hash按位与上oldCap得到的0和1也是随机的，
　　所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。
　　staticfinalintDEFAULTINITIALCAPACITY14；aka16，默认大小元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置finalNodeK，V〔〕resize（）｛NodeK，V〔〕oldT原先的数组，旧数组intoldCap（oldTabnull）？0：oldTab。旧数组长度intoldT阀值intnewCap，newThr0；if（oldCap0）｛数组已经存在不需要进行初始化if（oldCapMAXIMUMCAPACITY）｛旧数组容量超过最大容量限制，不扩容直接返回旧数组thresholdInteger。MAXVALUE；returnoldT｝进行2倍扩容后的新数组容量小于最大容量和旧数组长度大于等于16elseif（（newCapoldCap1）MAXIMUMCAPACITYoldCapDEFAULTINITIALCAPACITY）newThroldThr1；doublethreshold，重新计算阀值为原来的2倍｝初始化数组elseif（oldThr0）initialcapacitywasplacedinthreshold，有阀值，初始容量的值为阀值newCapoldTelse｛zeroinitialthresholdsignifiesusingdefaults，没有阀值newCapDEFAULTINITIALCAPACITY；初始化的默认容量newThr（int）（DEFAULTLOADFACTORDEFAULTINITIALCAPACITY）；重新计算阀值｝有阀值，定义了新数组的容量，重新计算阀值if（newThr0）｛floatft（float）newCaploadFnewThr（newCapMAXIMUMCAPACITYft（float）MAXIMUMCAPACITY？（int）ft：Integer。MAXVALUE）；｝thresholdnewT赋予新阀值SuppressWarnings（｛rawtypes，unchecked｝）NodeK，V〔〕newTab（NodeK，V〔〕）newNode〔newCap〕；创建新数组tablenewTif（oldTab！null）｛如果旧数组有数据，进行数据移动，如果没有数据，返回一个空数组for（intj0；joldCj）｛对旧数组进行遍历NodeK，Ve；if（（eoldTab〔j〕）！null）｛oldTab〔j〕将旧数组的所属位置的旧元素清空if（e。nextnull）当前节点是在数组上，后面没有链表，重新计算槽位newTab〔e。hash（newCap1）〕e；elseif（einstanceofTreeNode）当前节点是红黑树，红黑树重定位（（TreeNodeK，V）e）。split（this，newTab，j，oldCap）；else｛preserveorder，当前节点是链表NodeK，VloHeadnull，loTNodeK，VhiHeadnull，hiTNodeK，V遍历链表do｛nexte。if（（e。hasholdCap）0）｛不需要移位if（loTailnull）头节点是空的loH头节点放置当前遍历到的元素elseloTail。当前元素放到尾节点的后面loT尾节点重置为当前元素｝else｛需要移位if（hiTailnull）头节点是空的hiH头节点放置当前遍历到的元素elsehiTail。当前元素放到尾节点的后面hiT尾节点重置为当前元素｝｝while（（enext）！null）；if（loTail！null）｛不需要移位loTail。newTab〔j〕loH原位置｝if（hiTail！null）｛hiTail。newTab〔joldCap〕hiH移动到当前hash槽位oldCap的位置，即在原位置再移动2次幂的位置｝｝｝｝｝returnnewT｝
　　当前节点是数组，后面没有链表，重新计算槽位：位与操作的效率比效率高定位槽位：e。hash（newCap1）我们用长度16，待插入节点的hash值为21举例：（1）取余：21165（2）位与：21：0001010115：000011115：00000101
　　遍历链表，对链表节点进行移位判断：（e。hasholdCap）0比如oldCap8，hash是3，11，19，27时，（1）JDK1。8中（e。hasholdCap）的结果是0，8，0，8，这样3，19组成新的链表，index为3；而11，27组成新的链表，新分配的index为38；（2）JDK1。7中是（e。hashnewCap1），newCap是oldCap的两倍，也就是3，11，19，27对（161）与计算，也是0，8，0，8，但由于是使用了单链表的头插入方式，即同一位置上新元素总会被放在链表的头部位置；这样先放在一个索引上的元素终会被放到Entry链的尾部（如果发生了hash冲突的话），这样index为3的链表是19，3，index为38的链表是27，11。也就是说1。7中经过resize后数据的顺序变成了倒叙，而1。8没有改变顺序。HashMap总结
　　HashMap通过哈希表数据结构的形式存储键值对，这种设计的好处就是查询键值对的效率高；
　　我们在编码中可以优化HashMap的性能，例如重写key的hashCode方法，降低哈希冲突，从而减少链表的产生，高效利用哈希表，达到提高性能的效果。
　　我们在使用HashMap时，可以结合自己的场景来设置初始容量和加载因子两个参数。当查询操作较为频繁时，可以适当地减少加载因子；如果对内存利用率要求比较高，可以适当的增加加载因子；
　　我们可以在预知存储数据量的情况下，提前设置初始容量（初始容量预知数据量加载因子），这样做的好处是可以减少resize（）操作，提高HashMap的效率；
　　HashMap使用了数组链表这两种数据结构相结合的方式实现了链地址法，当有哈希值冲突时，就可以将冲突的键值对链成一个链表。但这种方式存在一个性能问题，如果链表过长，查询数据的时间复杂度就会增加。所以HashMap在JDK1。8中使用了红黑树来解决链表过长导致的查询性能下降问题。HashMap的面试题
　　hash的基本概念就是把任意长度的输入通过一个hash算法之后，映射成固定长度的输出问：hash冲突可以避免么？
　　理论上是没有办法避免的，就类比抽屉原理，
　　比如说一共有10个苹果，但是咱一共有9个抽屉，最终一定会有一个抽屉里的数量是大于1的，
　　所以hash冲突没有办法避免，只能尽量避免。问：好的hash算法考虑的点，应该是哪些呢？
　　首先这个hash算法，它一定效率得高，要做到长文本也能高效计算出hash值，
　　这二点就是hash值不能让它逆推出原文吧；
　　两次输入，只要有一点不同，它也得保证这个hash值是不同的。
　　其次，就是尽可能的要分散吧，因为，在table中slot中slot大部分都处于空闲状的，要尽可能降低hash冲突。问：HashMap中存储数据的结构，长什么样啊？
　　JDK1。7是数组链表；
　　JDK1。8是数组链表红黑树，每个数据单元都是一个Node结构，Node结构中有key字段、有value字段、还有next字段、还有hash字段。
　　Node结构next字段就是发生hash冲突的时候，当前桶位中node与冲突的node连成一个链表要用的字段。问：hashmap中的这个散列表数组长度，那初始长度是多少啊？
　　初始长度默认是16问：那这个散列表，newHashMap（）的时候就创建了，还是说在什么时候创建的？
　　散列表是懒加载机制，
　　只有第一次put数据的时候，它才创建的问：默认的负载因子是多少？并且这个负载因子有啥用？
　　默认负载因子0。75，就是75，
　　负载因子它的作用就是计算扩容阈值用的，
　　比如使用无参构造方法创建的hashmap对象，它默认情况下扩容阈值就160。7512问：链表它转化为这个红黑树需在达到什么条件？
　　链表转红黑树，主要是有两个指标，其中一个就是链表长度达到8，还有一个指标就是当前散列表数组长度它已经达到64。
　　如果前散列表数组长度它已经达到64，就算slot内部链表长度到了8，它也不会链转树，
　　它仅仅会发生一次resize，散列表扩容。问：Node对象hash值与key对象的hashcode（）有什么关系？
　　Node对象hash值是key。hashcode二次加工得到的。
　　加工原则是：
　　key的hashcode高16位低16位，得到的一个新值。问：hashCode值为什么需要高16位低16位
　　主要为了优化hash算法，近可能的分散得比较均匀，尽可能的减少碰撞
　　因为hashmap内部散列表，它大多数场景下，它不会特别大。
　　hashmap内部散列表的长度，也就是说length1对应的二进制数，实际有效位很有限，一般都在（低）16位以内，
　　注意：2的16次方为64K
　　这样的话，key的hash值高16位就等于完全浪费了，没起到作用。
　　所以，node的hash字段才采用了高16位异或低16位这种方式来增加随机的概率，近可能的分散得比较均匀，尽可能的减少碰撞问：hashmapPut写数据的具体流程，尽可能的详细点去说
　　主要为4种情况：
　　前面这个，寻址算法是一样的，都是根据key的hashcode经过高低位异或之后的值，然后再按位与（table。length1），得到一个槽位下标，然后根据这个槽内状况，状况不同，情况也不同，大概就是4种状态，
　　第一种是slotnull，直接占用slot就可以了，然后把当前put方法传进来的key和value包状成一个Node对象，放到这个slot中就可以了
　　第二种是slot！null并且它引用的node还没有链化；需要对比一下，node的key与当前put对象的key是否完全相等；
　　如果完全相等的话，这个操作就是replace操作，就是替换操作，把那个新的value替换当前slotnode。value就可以了；
　　否则的话，这次put操作就是一个正儿八经的hash冲突了，slotnode后面追加一个node就可以了，采用尾插法。
　　第三种就是slot内的node已经链化了；
　　这种情况和第二种情况处理很相似，首先也是迭代查找node，看看链表上的元素的key，与当前传来的key是不是完全一致。如果一致的话，还是repleace操作，替换当前node。value，否则的话就是我们迭代到链表尾节点也没有匹配到完全一致的node，把put数据包装成node追加到链表尾部；
　　这块还没完，还需要再检查一下当前链表长度，有没有达到树化阈值，如果达到阈值的话，就调用一个树化方法，树化操作都在这个方法里完成
　　第四种就是冲突很严重的情况下，就是那个链已经转化成红黑树了问：jdk8HashMap为什么要引入红黑树呢？
　　其实主要就是解决hash冲突导致链化严重的问题，如果链表过长，查找时间复杂度为O（n），效率变慢。
　　本身散列表最理想的查询效率为O（1），但是链化特别严重，就会导致查询退化为O（n）。
　　严重影响查询性能了，为了解决这个问题，JDK1。8它才引入的红黑树。红黑树其实就是一颗特殊的二叉排序树，这个时间复杂度是log（N）问：那为什么链化之后性能就变低了呀？
　　因为链表它毕竟不是数组，它从内存角度来看，它没有连续着。
　　如果我们要往后查询的话，要查询的数据它在链表末尾，那只能从链表一个节点一个节点Next跳跃过去，非常耗费性能。问：再聊聊hashmap的扩容机制吧？你说一下，什么情况下会触发这个扩容呢？
　　在写数据之后会触发扩容，可能会触发扩容。hashmap结构内，我记得有个记录当前数据量的字段，这个数据量字段达到扩容阈值的话，下一个写入的对象是在列表才会触发扩容问：扩容后会扩容多大呢？这块算法是咋样的呢？
　　因为table数组长度必须是2的次方数嘛，扩容其实，每次都是按照上一次的tableSize位移运算得到的。就是做一次左移1位运算，假设当前tableSize是16的话，16132问：这里为什么要采用位移运算呢？咋不直接tableSize乘以2呢？
　　主要是因为性能，因为cpu毕竟它不支持乘法运算，所有乘法运算它最终都是在指令层面转化为加法实现的。
　　效率很低，如果用位运算的话对cpu来说就非常简洁高效问：创建新的扩容数组，老数组中的这个数据怎么迁移呢？
　　迁移其实就是，每个桶位推进迁移，就是一个桶位一个桶位的处理；
　　主要还是看当前处理桶位的数据状态吧聊聊：HashMap为什么从链表换成了树？为啥不用AVL树？
　　上一节我们在阅读源码的时候，发现这样一句话：if（binCountTREEIFYTHRESHOLD1）1for1sttreeifyBin（tab，hash）；
　　当链表节点的计数超过TREEIFYTHRESHOLD1则将该链表树化，为什么要这样呢？
　　其实比较一下链表和树的优缺点就能大致明白该优化的目的。
　　我们假设一条链表上有10个节点，在查询时，最坏情况需要查询10次，N（10）。
　　对于树而言不同的树复杂度不同，但是对于最基本的二叉树：
　　左子树一定比root小，右子树一定比root大，
　　相当于是通过二分法在进行查找，查询速度绝大部分时候比链表要快。完美的情况下二叉搜索树BST
　　一般人们理解的二叉树（又叫二叉搜索树BST）会出现一个问题，完美的情况下，它是这样的：
　　但是也有可能出现这样一种情况：
　　树的节点正好从大到小的插入，此时树的结构也类似于链表结构，这时候的查询或写入耗时与链表相同。退化成为了链表的特殊BST
　　一颗特殊BST，退化成为了链表，如下图：
　　为了避免这种特殊的情况发生，引入了平衡二叉树（AVL）和红黑树（redblacktree）。
　　它们都是通过本身的建树原则来控制树的层数和节点位置，因为rbtree是由AVL演变而来，所以我们从了解AVL开始。从平衡二叉树到红黑树平衡二叉树
　　平衡二叉树也叫AVL（发明者名字简写），也属于二叉搜索树的一种，与其不同的是AVL通过机制保证其自身的平衡。
　　平衡二叉树的原则有以下几点：对于根结点而言，它的左子树任何节点的key一定比其小而右子树任何节点的key一定比其大；对于AVL树而言，其中任何子树仍然是AVL树；每个节点的左右子节点的高度之差的绝对值最多为1；
　　在插入、删除树节点的时候，如果破坏了以上的原则，AVL树会自动进行调整使得以上三条原则仍然成立。
　　举个例子，下左图为AVL树最长的2节点与最短的8节点高度差为1；
　　当插入一个新的节点后，根据上面第一条原则，它会出现在2节点的左子树，但这样一来就违反了原则3。
　　此时AVL树会通过节点的旋转进行调整，AVL调整的过程称之为左旋和右旋，
　　旋转之前，首先确定旋转点，
　　这个旋转点就是失去平衡这部分树，在自平衡之后的根节点pivot，
　　因为我们要根据它来进行旋转。
　　我们在学习AVL树的旋转时，不要将失衡问题扩大到整个树来看，这样会扰乱你的思路，
　　我们只关注失衡子树的根结点及它的子节点和孙子节点即可。
　　事实上，AVL树的旋转，我们权且叫AVL旋转是有规律可循的，因为只要聚焦到失衡子树，那么场景就是有限的4个：场景1左左结构（右旋）：
　　场景2右右结构（左旋）
　　场景3左右结构（左旋右旋）：
　　场景4右左结构（右旋左旋）：
　　可见无论哪种情况的失衡，都可以通过旋转来调整。
　　不难看出，旋转在图上像是将pivot节点向上提（将它提升为root节点），而后两边的节点会物理的分布在新root节点的两边，
　　接下来按照二叉树的要求：
　　左子树小于root，右子树大于root进行调整。
　　从图左左结构可以看出，当右旋时原来pivot（7）的右子树会转变到用root点（9）的左子树处；
　　从图右右结构可见，当左旋时，原来pivot（18）的左子树会分布到原root点（9）的右子树。
　　对于左右结构和右左结构无非是经过多次旋转达到稳定，旋转的方式并没有区别，AVL树平衡总结
　　既然AVL树可以保证二叉树的平衡，这就意味着它最坏情况的时间复杂度O（logn）要低于普通二叉树和链表的最坏情况O（n）。
　　那么HashMap就直接使用AVL树来替换链表就好了，为什么选择用红黑树呢？
　　我们会发现，由于AVL树必须保证Max（最大树高最小树高）1所以在插入的时候很容易出现不平衡的情况，一旦这样，就需要进行旋转以求达到平衡。
　　正是由于这种严格的平衡条件，导致需要花大量时间在调整上，故AVL树一般使用场景在于查询而弱于增加删除。
　　红黑树继承了AVL可自平衡的优点，同时在查询速率和调整耗时中寻找平衡，放宽了树的平衡条件，在实际应用中，红黑树的使用要多得多。红黑树（RBTree）
　　红黑树也是一种自平衡二叉查找树，它与AVL树类似，都在添加和删除的时候通过旋转操作保持二叉树的平衡，以求更高效的查询性能。
　　与AVL树相比，红黑树牺牲了部分平衡性以换取插入删除操作时少量的旋转操作，整体来说性能要优于AVL树。
　　红黑树的原则有以下几点：节点非黑即红整个树的根节点一定是黑色叶子节点（包括空叶子节点）一定是黑色每个红色节点的两个子节点都为黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
　　基于上面的原则，我们一般在插入红黑树节点的时候，会将这个节点设置为红色，原因参照最后一条原则，红色破坏原则的可能性最小，如果是黑色很可能导致这条支路的黑色节点比其它支路的要多1。
　　一旦红黑树上述原则有不满足的情况，我们视为平衡被打破，红黑树会通过变色、左旋、右旋的方式恢复平衡。
　　前文已经详细解释过什么是左旋和右旋，这里就不赘述；变色这个概念很好理解，就是红变黑或黑变红。红黑树的平衡过程
　　但是我们会好奇，红黑树的平衡会不会和上文的AVL树一样，也有可以归纳的平衡场景呢？
　　答案是肯定的：
　　场景1第一次插入：
　　RBTree第一次插入节点时，新节点会是红色，违背了原则二，直接将颜色变黑即可。场景2父节点为黑色：
　　当插入时节点为红色且父节点为黑色，满足RBTree所有原则，已经平衡。场景3父节点为红色且叔叔节点为红色：
　　父节点叔叔节点都为红色
　　在平衡的过程中，要注意红黑树的规定原则。
　　插入红节点，不能仅仅将父节点由红变黑，因为这样会增加这条支路的黑节点数，从而违反从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
　　将父节点和叔叔节点都变黑，再将祖父节点由黑变红，这样一来，以13为root的红黑树对外黑色节点数没变，对内各条支路节点数一致。场景4父节点为红色，叔叔节点为黑色且新节点为右子树：
　　节点8的父节点为红，叔叔节点为黑，且通过左旋的方式，让整个情况变成下一个场景：父节点红色，叔叔节点为黑色且新节点为左子树。场景5父节点为红色，叔叔节点为黑色且新节点为左子树：
　　问：红黑树写入操作，是如何找到它的父节点的？
　　说清楚红黑树，的节点TreeNode它就是继承Node结构，
　　TreeNode在Node基础上加了几个字段，分别指向父节点parent，然后指向左子节点left，还有指向右子节点的right，然后还有表示颜色redblack，这个就是TreeNode的基本结构
　　红黑树的插入操作：
　　首先是找到一个合适的插入点，就是找到插入节点的父节点，然后这个红黑树它又满足二叉树的所有排序特性（满足二叉排序树的所有特性），这个找父节点的操作和二叉树是完全一致的。
　　二叉查找树，左子节点小于当前节点，右子节点大于当前节点，然后每一次向下查找一层就可以排除掉一半的数据，插入效率在log（N）
　　查找的过程也是分情况的，
　　第一种情况就是一直向下探测，直到查询到左子树或者右子树为null，
　　说明整个树中，它没有发现node。key与当前putkey一致的这个TreeNode。此时探测节点就是插入父节点所在了，这就找到了父节点；将当前插入节点插入到父节点的左子树或者右子树，，
　　当然，插入后会破坏平衡，还需要一个红黑树的平衡算法。
　　第二种情况就是根节点向下探测过程中，发现这个TreeNode。key与当前put。key完全一致。这就不需要插入，替换value就可以了，父节点就是当前节点的父节点红黑树那几个原则，你还记得么？节点非黑即红整个树的根节点一定是黑色叶子节点（包括空叶子节点）一定是黑色每个红色节点的两个子节点都为黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。问：红黑树的有那些内部操作变色
　　把一个红色的节点变成黑色，或者把一个黑色的节点变成红色，就是对这个节点的变色。左旋
　　与平衡二叉树的旋转操作类似。问：什么是AVL左旋和右旋？
　　加入节点后，左旋和右旋，维护AVL平衡性
　　右旋转
　　场景：插入的元素在不平衡元素的左侧的左侧x。righty
　　y。leftxxx（原x。right）对节点y进行向右旋转操作，返回旋转后新的根节点xyxxT4向右旋转（y）zyzT3T1T2T3T4T1T2场景：插入的元素在不平衡元素的右侧的右侧
　　向左旋转过程
　　x。
　　y。right（原x。left）对节点y进行向左旋转操作，返回旋转后新的根节点xyxT1x向左旋转（y）yzT2zT1T2T3T4T3T4问：聊下ConcurrentHashMap
　　首先它的数据结构在JDK1。7版本底层是个分片数组
　　为了保证线程安全它有个Segment分片锁，这个Segment继承于ReentrantLock，来保证它的线程安全的，它每次只能一段加速来保证它的并发度。
　　在JDK1。8版本，它改成了与HashMap一样的数据结构，
　　数组单链表或者红黑树的数据结构，
　　在1。8它逐渐放弃这种Segment分片锁机制，而使用Synchronized和CAS来操作。
　　因为在1。6版本的时候JVM对Synchronized的优化非常大。
　　现在也是用这种方法保证它的线程安全。
　　问：说说HashMap底层原理，ConcurrentHashMap与HashMap的区别HashMap结构及原理
　　HashMap是基于哈希表的Map接口的非同步实现。实现HashMap对数据的操作，允许有一个null键，多个null值。
　　HashMap底层就是一个数组结构，数组中的每一项又是一个链表。数组链表结构，新建一个HashMap的时候，就会初始化一个数组。
　　Entry就是数组中的元素，每个Entry其实就是一个keyvalue的键值对，它持有一个指向下一个元素的引用，这就构成了链表，HashMap底层将keyvalue当成一个整体来处理，这个整体就是一个Entry对象。
　　HashMap底层采用一个Entry数组来保存所有的keyvalue键值对，当需要存储一个Entry对象时，会根据hash算法来决定在其数组中的位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；
　　当需要取出一个Entry对象时，也会根据hash算法找到其在数组中的存储位置，在根据equals方法从该位置上的链表中取出E
　　ConcurrentHashMap与HashMap的区别
　　1。HashMap
　　我们知道HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100，所以在并发情况下不能使用HashMap。
　　2。HashTable
　　HashTable和HashMap的实现原理几乎一样，差别无非是
　　HashTable不允许key和value为null
　　HashTable是线程安全的
　　但是HashTable线程安全的策略实现代价却太大了，简单粗暴，getput所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
　　多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。
　　3。ConcurrentHashMap
　　主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lockfree技术来减少锁竞争对于性能的影响。
　　我们都知道Map一般都是数组链表结构（JDK1。8该为数组红黑树）。
　　ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度，由于ConcurrentHashMap在JDK1。7和1。8中的实现非常不同，接下来我们谈谈JDK在1。7和1。8中的区别。JDK1。7版本的CurrentHashMap的实现原理
　　1）在JDK1。7中ConcurrentHashMap采用了数组Segment分段锁的方式实现。
　　1。Segment（分段锁）
　　ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表，同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
　　2。内部结构
　　ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：
　　从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
　　第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。
　　3。该结构的优劣势
　　坏处
　　这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长
　　好处
　　写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。
　　所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。JDK1。8版本的CurrentHashMap的实现原理
　　JDK8中ConcurrentHashMap参考了JDK8HashMap的实现，采用了数组链表红黑树的实现方式来设计，内部大量采用CAS操作，这里我简要介绍下CAS。
　　CAS是compareandswap的缩写，即我们所说的比较交换。cas是一种基于锁的操作，而且是乐观锁。
　　在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。
　　而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。
　　CAS操作包含三个操作数内存位置（V）、预期原值（A）和新值（B）。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。
　　CAS是通过无限循环来获取数据的，若果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。
　　JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1。7中的分段锁思想。
　　Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。staticclassNodeK，VimplementsMap。EntryK，V｛finalKvolatileVvolatileNodeK，V
　　Java8ConcurrentHashMap结构基本上和Java8的HashMap一样，不过保证线程安全性。
　　在JDK8中ConcurrentHashMap的结构，由于引入了红黑树，使得ConcurrentHashMap的实现非常复杂，
　　我们都知道，红黑树是一种性能非常好的二叉查找树，其查找性能为O（logN），但是其实现过程也非常复杂，而且可读性也非常差，
　　DougLea的思维能力确实不是一般人能比的，早期完全采用链表结构时Map的查找时间复杂度为O（N），
　　JDK8中ConcurrentHashMap在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。总结
　　其实可以看出JDK1。8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1。7版本的ReentrantLockSegmentHashEntry，到JDK1。8版本中synchronizedCASHashEntry红黑树。
　　1。数据结构：取消了Segment分段锁的数据结构，取而代之的是数组链表红黑树的结构。
　　2。保证线程安全机制：JDK1。7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1。8采用CASSynchronized保证线程安全。3。锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。4。链表转化为红黑树：定位结点的hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。5。查询时间复杂度：从原来的遍历链表O（n），变成遍历红黑树O（logN）。最后（求关注，别白嫖我）
　　如果这篇文章对您有所帮助，或者有所启发的话，欢迎关注我的公众号：程序员黑哥