2024年10月hashmap原理详解（HashMap详解）

　　⑴hashmap原理详解（HashMap详解

　　⑵存储键值对，实现快速存取数据；()允许键/值为null，但不允许重复的键；()非同步synchronized(比同步快)，线程不安全；注：让HashMap同步：Mapm=Collections.synchronizeMap(hashMap);()实现Map接口，对键值对进行映射，不保证有序(比如插入的顺序)注：Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。()HashMap默认的容量大小是；增加容量时，每次将容量变为“原始容量x”()HashMap添加元素时，是使用自定义的哈希算法;()不存储键值对，仅存储对象；()不允许键/值为null；()线程安全(速度慢)，采用synchronize关键字加锁原理(几乎在每个方法上都加锁)，；()实现了Set接口，不允许集合中有重复的值。注：将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，比较对象的值是否相等，以确保set中没有储存相等的对象。hashCode()可能相同，用equals()判断对象的相等性。()Hashtable默认的容量大小是；增加容量时，每次将容量变为“原始容量x+”；()Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。()Java并发包java.util.concurrent中的一个线程安全且高效的HashMap实现()不允许键/值为null；()线程安全：在JDK.中采用“分段锁”的方式，.中直接采用了CAS（无锁算法+synchronized。Entry：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry，这些Entry分散存储在一个数组当中。hashMap是在bucket中储存键对象和值对象，作为Map.Entrybucket：HashMap初始化时，创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置被称为“桶(bucket)”，每个bucket都有其指定索引，系统可以根据其索引快速访问该bucket里存储的元素。loadFactor：负载因子。默认值DEFAULT_LOAD_FACTOR=.f；capacity：容量，指的是数组的长度threshold：阈值=capacity*loadFactor。超过阈值则扩容为原来的两倍。size：HashMap的大小，它是HashMap保存的键值对的数量。HashMap是基于hashing的原理，底层使用哈希表结构(数组+链表)实现。使用put(key,value)存储对象，使用get(key)获取对象。理解为，数组中存储的是一个Entry，并且作为链表头结点，头结点之后的每个节点中储存键值对对象Entry。给put()方法传递键和值时，先对键调用hashCode()方法计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过负载因子LoadFacotr则resize为原来的倍)。扩容扩的是数组的容量，发生碰撞后当链表长度到达后，链表上升为红黑树，提高速度。根据键key的hashcode找到bucket位置，然后遍历链表节点，调用equals(用来获取值对象)方法确定键值对，找到要找的值对象。a.对key的hashCode做hash操作(高bit不变，低bit和高bit做了一个异或)b.计算下标(n-)&hash，从而获得buckets的位置//h&(length-)数字分析法、平方取中法、分段叠加法、除留余数法、伪随机数法。其他解决hash冲突办法：开放定址法、链地址法、再哈希法。根据hashcode来划分的数组，如果数组的坐标相同，则进入链表这个数据结构中，jdk.及以前为头插法，jdk.之后是尾插法，在jdk.之后，当链表长度到达的时候，jdk.上升为红黑树。存的时候按照上面的方式存，取的时候根据equals确定值对象。.常见问题：集合类、数据结构、线程安全、解决碰撞方法、hashing概念和方法、equals()和hashCode()的应用、不可变对象的好处

　　⑶hashmap扩容原理是什么

　　⑷hashmap扩容原理是HashMap的方法是使用一个新的数组代替原有的数组。对原数组的所有数据进行重新计算插入新数组，之后指向新数组，如果扩容前数组已经达到最大了，那么将直接将阈值设置成最大整形return。

　　⑸hashmap扩容的特点

　　⑹加载因子越大空间利用越高，扩容前填充的元素越多，put操作较快，但是链表容易过长，hash碰撞几率较大，get操作较慢，加载因子越小get操作较快，链表短hash碰撞几率低，但是空间利用率低，put元素过多会导致频繁扩容影响性能。

　　⑺我们在使用HashMap的时候，如果预先知道大概要操作的元素数量，最好给一个初始化值，首先尽量避免扩容，其次根据业务场景结合重要参数来设定一些值来提高使用效率，HashMap每次扩容增长一倍。

　　⑻hashmap底层实现原理

　　⑼hashmap底层实现原理是SortedMap接口能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。

　　⑽如果使用排序的映射，建议使用TreeMap。在使用TreeMap时，key必须实现parable接口或者在构造TreeMap传入自定义的parator，否则会在运行时抛出java.lang.ClassCastException类型的异常。

　　⑾Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它承自Dictionary类，并且是线程安全的，任一时间只有一个线程能写Hashtable

　　⑿从结构实现来讲，HashMap是：数组+链表+红黑树（JDK.增加了红黑树部分实现的。

　　⒀从源码可知，HashMap类中有一个非常重要的字段，就是Nodetable，即哈希桶数组。Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)，除了K，V，还包含hash和next。

　　⒁HashMap就是使用哈希表来存储的。哈希表为解决冲突，采用链地址法来解决问题，链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

　　⒂如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶数组数组很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空间成本和时间成本之间权衡，其实就是在根据实际情况确定哈希桶数组的大小，并在此基础上设计好的hash算法减少Hash碰撞。

　　⒃hashmap碰撞-拉链法

　　⒄HashMap是一个数组，数组中的每个元素是链表。put元素进去的时候，会通过计算key的hash值来获取到一个index，根据index找到数组中的位置，进行元素插入。当新来的元素映射到冲突的数组位置时，只需要插入到对应链表位置即可，新来的元素是插入到链表的头部。Java中HashMap是利用“拉链法”处理HashCode的碰撞问题。在调用HashMap的put方法或get方法时，都会首先调用hashcode方法，去查找相关的key，当有冲突时，再调用equals方法。hashMap基于hasing原理，我们通过put和get方法存取对象。当我们将键值对传递给put方法时，他调用键对象的hashCode()方法来计算hashCode，然后找到bucket（哈希桶位置来存储对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时，他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对

　　⒅hashmap底层实现原理是什么

　　⒆HashMap的实现原理：首先有一个每个元素都是链表（可能表述不准确的数组，当添加一个元素（key-value时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了。

　　⒇这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

　　⒈当链表数组的容量超过初始容量的.时，再散列将链表数组扩大倍，把原链表数组的搬移到新的数组中。

　　⒉HashMap的实例有两个参数影响其性能：

　　⒊初始容量和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。

　　⒋加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构，从而哈希表将具有大约两倍的桶数。在Java编程语言中，加载因子默认值为.，默认哈希表元为。

　　⒌hashmap的扩容机制

　　⒍hashMap扩容机制就是重新计算容量，向hashMap不停地添加元素，当hashMap无法装载新的元素，对象将需要扩大数组容量，以便装入更多的元素。

　　⒎HashMap的扩展原理是HashMap用一个新的数组替换原来的数组。重新计算原数组的所有数据并插入一个新数组，然后指向新数组。如果阵列在容量扩展前已达到最大值，阈值将直接设置为最大整数返回。

　　⒏HashMap容量扩展的特性：加载因子越大，空间利用率越高，扩容前需要填充的元素越多，put操作越快，但链表容易过长，hash碰撞概率大，get操作慢。加载因子越小，get操作越快，链表越短，hash碰撞概率低。但是，空间利用率低。put元素太多会导致频繁扩容，影响性能。

　　⒐HashMap扩容可以分为三种情况：

　　⒑使用默认构造方法初始化HashMap。从前文可以知道HashMap在一开始初始化的时候会返回一个空的table，并且thershold为。

　　⒒因此第一次扩容的容量为默认值DEFAULT_INITIAL_CAPACITY也就是。同时threshold=DEFAULT_INITIAL_CAPACITY*DEFAULT_LOAD_FACTOR=。

　　⒓指定初始容量的构造方法初始化HashMap。那么从下面源码可以看到初始容量会等于threshold，接着threshold=当前的容量（threshold*DEFAULT_LOAD_FACTOR。

　　⒔HashMap不是第一次扩容。如果HashMap已经扩容过的话，那么每次table的容量以及threshold量为原有的两倍。

　　⒕以上内容参考：百度百科-Hashmap

　　⒖HashMap底层实现原理剖析

　　⒗Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。.HashMap的数据结构：在java中数据结构，最基本也就两种一种数组一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为，.hashMap源码解析staticfinalintDEFAULT_INITIAL_CAPACITY=《《;//初始化容量大小?staticfinalintMAXIMUM_CAPACITY=《《;///容器最大值staticfinalfloatDEFAULT_LOAD_FACTOR=.f;//加载影子staticfinalEntryEMPTY_TABLE={};//null的hashMaptransientEntry)EMPTY_TABLE;///动态扩大容器时使用的一个hashMaptransientintsize;//当前数据量intthreshold;//扩大容器时的大小为?capacity*loadfactorfinalfloatloadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR存取元素：调用put方法publicVput(Kkey,Vvalue){?//判断当前table为Null第一次Put??if(table==EMPTY_TABLE){?????inflateTable(threshold);?//初始化容器的大小?}?if(key==null)??returnputForNullKey(value);//判断当前key为null将Nullkey添加到数组的第一个位置?inthash=hash(key);//将当前key进行hash详情见下方?inti=indexFor(hash,table.length);//调用完hash算法后，详情见下方?for(Entrye=table;e!=null;e=e.next){//循环判断当前数组下标为Entry的实体将当前key相同的替换为最新的值??????Objectk;??????if(e.hash==hash&&((k=e.key)==key||key.equals(k))){????????VoldValue=e.value;????????e.value=value;????????e.recordAess(this);????????returnoldValue;??????}????}????modCount++;????addEntry(hash,key,value,i);//如果key都不同则添加Entry.详情见下方????returnnull;??}hashMap的hash算法剖析finalinthash(Objectk){????inth=hashSeed;????if(!=h&&kinstanceofString){?//判断当前k是否为string和??????returnsun.misc.Hashing.stringHash((String)k);//使用stringHash算法得出key??的hash值????}????h^=k.hashCode();//调用key的hashCode得出值后使用“或“运算符?????h^=(h》》》)^(h》》》);????returnh^(h》》》)^(h》》》);前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。一个十进制数(二进制)，经过上述公式运算之后的结果是(二进制)。看出来了吗？或许这样还看不出什么，再举个数字(二进制)，运算结果是(二进制)，现在应该很明显了，它的目的是让“”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后““就变得很均匀了。我们用table位置上的Entity赋值给新的?Entity的next，这样插入结束??}indexFor返回当前数组下标，staticintindexFor(inth,intlength){????returnh&(length-);??}那么得到key之后的hash如何得到数组下标呢？把h与HashMap的承载量（HashMap的默认承载量length是，可以自动变长。在构造HashMap的时候也可以指定一个长度。这个承载量就是上图所描述的数组的长度。进行逻辑与运算，即?h&(length-)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的位置。第步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的?hashcode与length相除取余，即hash%length，这样有可能会造成index分布不均匀。首先来解释一下为什么数组大小为的幂时hashmap访问的性能最高？看下图，左边两组是数组长度为（的次方，右边两组是数组长度为。两组的hashcode均为和，但是很明显，当它们和“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，和会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到或者，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为的时候，hashcode的值会与（进行“与”，那么最后一位永远是，而，，，，，，这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！?voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){?////若HashMap的实际大小不小于“阈值”，则调整HashMap的大小????if((size》=threshold)&&(null!=table)){??????resize(*table.length);??????hash=(null!=key)?hash(key):;?????////设置“bucketIndex”位置的元素为“新Entry”，//设置“e”为“新Entry的下一个节点”??????bucketIndex=indexFor(hash,table.length);????}????createEntry(hash,key,value,bucketIndex);??}//将当前key和value添加到Entry中voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){?????Entrye=table;?//将第一个就得table复制个新的entry?????table=C；这样我们发现index=的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起????size++;//容量加??}以上就是HashMap添加元素时的过程解析那么如何get元素呢？publicVget(Objectkey){?if(key==null)returngetForNullKey();//当前key是否为null如果为null值返回table这个value??Entryentry=getEntry(key);????returnnull==entry?null:entry.getValue();??}finalEntrygetEntry(Objectkey){?if(size==){returnnull;}?//判断容量是否大于??inthash=(key==null)?:hash(key);//对当前key进行hashhash后得到一个值?for(Entrye=table;//获取当前Entry循环遍历??????e!=null;??????e=e.next){??????Objectk;??????if(e.hash==hash&&????????((k=e.key)==key||(key!=null&&key.equals(k))))????????returne;????}????returnnull;??}扩展问题:.当前我们的hashMap中越来越大的之后，“碰撞“就越来越明显，那么如何解决碰撞呢？扩容！当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为.，也就是说，默认情况下，数组大小为，那么当hashmap中元素个数超过*.=的时候，就把数组的大小扩展为*=，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有个元素newHashMap(),但是理论上来讲newHashMap()更合适，不过上面annegu已经说过，即使是，hashmap也自动会将其设置为。但是newHashMap()还不是更合适的，因为.*《,也就是说为了让.*size》,我们必须这样newHashMap()才最合适，既考虑了&的问题，也避免了resize的问题HashMap的两种遍历方式第一种Mapmap=newHashMap();Iteratoriter=map.entrySet().iterator();while(iter.hasNext()){Map.Entryentry=(Map.Entry)iter.next();Objectkey=entry.getKey();Objectval=entry.getValue();}效率高,以后一定要使用此种方式！第二种Mapmap=newHashMap();Iteratoriter=map.keySet().iterator();while(iter.hasNext()){Objectkey=iter.next();Objectval=map.get(key);}效率低,以后尽量少使用！归纳简单地说，HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。HashMap底层采用一个Entry数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

　　⒘HashMap实现原理

　　⒙HashMap在实际开发中用到的频率非常高，面试中也是热点。所以决定写一篇文章进行分析，希望对想看源码的人起到一些帮助，看之前需要对链表比较熟悉。以下都是我自己的理解，欢迎讨论，写的不好轻喷。

　　⒚HashMap中的数据结构为散列表，又名哈希表。在这里我会对散列表进行一个简单的介绍，在此之前我们需要先回顾一下数组、链表的优缺点。

　　⒛数组和链表的优缺点取决于他们各自在内存中存储的模式，也就是直接使用顺序存储或链式存储导致的。无论是数组还是链表，都有明显的缺点。而在实际业务中，我们想要的往往是寻址、删除、插入性能都很好的数据结构，散列表就是这样一种结构，它巧妙的结合了数组与链表的优点，并将其缺点弱化（并不是完全消除

　　散列表的做法是将key映射到数组的某个下标，存取的时候通过key获取到下标（index然后通过下标直接存取。速度极快，而将key映射到下标需要使用散列函数，又名哈希函数。说到哈希函数可能有人已经想到了，如何将key映射到数组的下标。

　　图中计算下标使用到了以下两个函数：

　　值得注意的是，下标并不是通过hash函数直接得到的，计算下标还要对hash值做index()处理。Ps：在散列表中，数组的格子叫做桶，下标叫做桶号，桶可以包含一个key-value对，为了方便理解，后文不会使用这两个名词。

　　以下是哈希碰撞相关的说明：

　　以下是下标冲突相关的说明：

　　很多人认为哈希值的碰撞和下标冲突是同一个东西，其实不是的，它们的正确关系是这样的，hashCode发生碰撞，则下标一定冲突；而下标冲突，hashCode并不一定碰撞

　　上文提到，在jdk.以前HashMap的实现是散列表=数组+链表，但是到目前为止我们还没有看到链表起到的作用。事实上，HashMap引入链表的用意就是解决下标冲突。

　　下图是引入链表后的散列表：

　　如上图所示，左边的竖条，是一个大小为的数组，其中存储的是链表的头结点，我们知道，拥有链表的头结点即可访问整个链表，所以认为这个数组中的每个下标都存储着一个链表。其具体做法是，如果发现下标冲突，则后插入的节点以链表的形式追加到前一个节点的后面。

　　这种使用链表解决冲突的方法叫做：拉链法（又叫链地址法。HashMap使用的就是拉链法，拉链法是冲突发生以后的解决方案。

　　Q：有了拉链法，就不用担心发生冲突吗？A：并不是！由于冲突的节点会不停的在链表上追加，大量的冲突会导致单个链表过长，使查询性能降低。所以一个好的散列表的实现应该从源头上减少冲突发生的可能性，冲突发生的概率和哈希函数返回值的均匀程度有直接关系，得到的哈希值越均匀，冲突发生的可能性越小。为了使哈希值更均匀，HashMap内部单独实现了hash()方法。

　　以上是散列表的存储结构，但是在被运用到HashMap中时还有其他需要注意的地方，这里会详细说明。

　　现在我们清楚了散列表的存储结构，细心的人应该已经发现了一个问题：Java中数组的长度是固定的，无论哈希函数是否均匀，随着插入到散列表中数据的增多，在数组长度不变的情况下，链表的长度会不断增加。这会导致链表查询性能不佳的缺点出现在散列表上，从而使散列表失去原本的意义。为了解决这个问题，HashMap引入了扩容与负载因子。

　　以下是和扩容相关的一些概念和解释：

　　Ps：扩容要重新计算下标，扩容要重新计算下标，扩容要重新计算下标，因为下标的计算和数组长度有关，长度改变，下标也应当重新计算。

　　在.及其以上的jdk版本中，HashMap又引入了红黑树。

　　红黑树的引入被用于替换链表，上文说到，如果冲突过多，会导致链表过长，降低查询性能，均匀的hash函数能有效的缓解冲突过多，但是并不能完全避免。所以HashMap加入了另一种解决方案，在往链表后追加节点时，如果发现链表长度达到，就会将链表转为红黑树，以此提升查询的性能。

　　一图了解ConcurrentHashMap底层原理

　　ConcurrentHashMap底层数据结构是一个数组table、table数组上挂着单向链表或红黑树、newConcurrentHashMap();如果没有指定长度的话，默认是，并且数组长度必须是的n次幂，若自定义初始化的长度不是的n次幂，那么在初始化数组时，会吧数组长度设置为大于自定义长度的最近的的n次幂。（如：自定义长度为，那么实际初始化数组后的长度为、底层是使用synchronized作为同步锁，并且锁的粒度是数组的具体索引位（有些人称之为分段锁。、Node节点，hash》，当hash冲突时，会形成一个单向链表挂在数组上。、ForwardindNode，继承至Node，其hash=-，表示当前索引位的数据已经被迁移到新数组上了、ReservationNode，继承至Node，其hash=-，表示当前索引位被占用了（pute方法、TreenBin，继承至Node，其hash=-，代表当前索引下挂着一颗红黑树、lockState为ConcurrentHashMap底层自己实现的基于cas的读写锁，锁粒度是具体的某颗树。当向红黑树进行增，删操作时，首先会先上sync同步锁，然后自平衡的时候会上lockState写锁，当读红黑树的时候，会上lockState读锁，然后判断此时是否有线程正持有写锁，或是否有线程正在等待获取写锁，若有，则读线程会直接去读双向链表，而不是去读红黑树。、TreeNode，hash》，为红黑树具体节点。TreeBin的root代表红黑树的根节点，first代表双向链表的第一个节点、双向链表：构建红黑树时还维护了一个双向链表，其目的为：()当并发写读同一颗红黑树的时候，读线程判断到有线程正持有写锁，那么会跑去读取双向链表，避免因为并发写读导致读线程等待或阻塞。()当扩容的时候，会去遍历双向链表，重新计算节点hash，根据新的hash判断放在新数组的高位还是地位、触发扩容的规则：添加完元素后，若判断到当前容器元素个数达到了扩容的阈值（数组长度*.，则会触发扩容添加完元素后，所在的单向链表长度》=，则会转为红黑树，不过在转红黑树之前会判断数组长度是否小于，若小于则会触发扩容、table为扩容前的数组，nextTable为扩容中创建的新数组，迁移数据完毕后需要将nextTable赋值给table、扩容后的数组是元素组长度的倍、ln，hn分别表示高位和低位的链表（高链，低链。即，扩容时，会用n&h==来判断元素应该放在新数组的i位置还是i+n位置。n：元素组长度；h：元素hash值；i：元素所在的原数组索引位；。这样就会出现有些元素会被挂在低位，有些元素会被挂在高位，从而达到打散元素的目的。、红黑树扩容时，会遍历双向链表，并且计算n&h==来判断元素放在低位（lo还是高位（ho，确定完元素的去处之后，会判断分别判断两个双向链表（lo,ho的长度是否大于，若大于则将还是以一颗红黑树的结构挂在数组上，若《=的话，则转为单向链表，挂在数组上

　　HashMap原理—扩容机制及存取原理

　　HashMap使用哈希算法得到数组中保存的位置，然后调用put方法将key-value对保存到table变量中。我们通过图来演示一下存储的过程。

　　我们关注一下这里面最重要的三个方法，hash()，putVal()，resize().

　　我们通过hash方法计算索引，得到数组中保存的位置，看一下源码

　　我们可以看到HashMap中的hash算法是通过key的hashcode值与其hashcode右移位后得到的值进行异或运算得到的，那么为什么不直接使用key.hashCode()，而要进行异或操作？我们知道hash的目的是为了得到进行索引，而hash是有可能冲突的，也就是不同的key得到了同样的hash值，这样就很容易产业碰撞，如何减少这种情况的发生呢，就通过上述的hash(Objectkey)算法将hashcode与hashcode的低位做异或运算，混合了高位和低位得出的最终hash值，冲突的概率就小多了。举个例子：

　　我们的hash(Objectkey)算法一个道理，最终的hash值混合了高位和低位的信息，掺杂的元素多了，那么最终hash值的随机性越大，而HashMap的table下标依赖于最终hash值与table.length()-的&运算，这里的&运算类似于挑包子的过程，自然冲突就小得多了。计算过程如下：

　　通过putVal方法将传递的key-value对添加到数组table中。

　　HashMap通过resize()方法进行扩容，容量规则为的幂次

　　我们先简单说一下get(Objectkey)流程，通过传入的key通过hash()算法得到hash值，在通过(n-)&hash找到数组下标，如果数组下标所对应的node值正好key一样就返回，否则找到node.next找到下一个节点，看是否是treenNode，如果是，遍历红黑树找到对应node，如果不是遍历链表找到node。我们看一下源码

　　这几个方法是核心，虽然HashMap还有很多常用方法，不过大体和这几个方法有关，或者实现逻辑相似，这里就不再多说了。

　　本文在上一章基本概念和底层结构的基础上，从源码的角度讲解了扩容机制以及存取原理，主要分析了put方法和get方法，put方法的核心为hash()，putVal()，resize()，get方法的核心为getNode()。