hashmap设计源码

㈠ hashmap底层实现原理

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

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

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

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

(1)hashmap设计源码扩展阅读

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

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

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

㈡ HashMap源码分析

HashMap（jdk 1.8）
  使用哈希表存储键值对，底层是一个存储Node的table数组。其基本的运行逻辑是，table数组的每一个元素是一个槽，用于存储Node对象，向Hash表中插入键值对时，首先计算键的hash值，并对数组容量（即数组长度）取余，定位该键值对应放在哪个槽中，若槽中已经存在元素（即哈希冲突），将Node节点插入到冲突链表尾端，当该槽中结点超过一定数量（默认为8）并且哈希表容量超过一定值（默认为64）时，对该链表进行树化。低于一定数量（默认为6）后进行resize时，树形结构又会链表化。当哈希表的总节点数超过阈值时，对哈希表进行扩容，容量翻倍。

由于哈希表需要用到key的哈希函数，因此对于自定义类作为key使用哈希表时，需要重写哈希函数，保证相等的key哈希值相同。

由于扩容或树化过程Node节点的位置会发生改变，因此哈希表是无序的，不同时期遍历同一张哈希表，得到的节点顺序会不同。

成员变量

    Hash表的成员变量主要有存储键值对的table数组，size，装载因子loadFactory，阈值theshold，容量capacity。

table数组：

哈希表的实质就是table数组，它用来存储键值对。哈希表中内部定义了Node类来封装键值对。

 Node类实现了Map的Entry接口。包括key，value，下一个Node指针和key的hash值。

 容量Capacity：

HashMap中没有专门的属性存储容量，容量等于table.lenth，即数组的长度，默认初始化容量为16。初始化时，可以指定哈希表容量，但容量必须是2的整数次幂，在初始化过程中，会调用tableSizeFor函数，得到一个不小于指定容量的2的整数次幂，暂时存入到threshold中。

注意，若容量设置过大，那么遍历整个哈希表需要耗费更多的时间。

    阈值threshold：

指定当前hash表最多存储多少个键值对，当size超过阈值时，hash表进行扩容，扩容后容量翻倍。

   loadFactory：

threshold=capacity*loadFactory。

装填因子的大小决定了哈希表存储键值对数量的能力，它直接影响哈希表的查找性能。初始化时可以指定loadFactory的值，默认为0.75。

 初始化过程

哈希表有3个构造函数，用户可以指定哈希表的初始容量和装填因子，但初始化过程只是简单填入这两个参数，table数组并没有初始化。注意，这里的initialCapacity会向上取2的整数次幂并暂时保存到threshold中。

table数组的初始化是在第一次插入键值对时触发，实际在resize函数中进行初始化。

hash过程与下标计算

哈希表是通过key的哈希值决定Node放入哪个槽中， 在java8中 ，hash表没有直接用key的哈希值，而是自定义了hash函数。

哈希表中的key可以为null，若为null，哈希值为0，否则哈希值（一共32位）的高16位不变，低16位与高16位进行异或操作，得到新的哈希值。（h >>> 16，表示无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。）

之所以这样处理，是与table的下标计算有关

因为，table的长度都是2的幂，因此index仅与hash值的低n位有关（n-1为0000011111的形式），hash值的高位都被与操作置为0了，相当于hash值对n取余。

由于index仅与hash值的低n位有关，把哈希值的低16位与高16位进行异或处理，可以让Node节点能更随机均匀得放入哈希表中。

get函数：

V  get(Object key) 通过给定的key查找value

先计算key的哈希值，找到对应的槽，遍历该槽中所有结点，如果结点中的key与查找的key相同或相等，则返回value值，否则返回null。

注意，如果返回值是null，并不一定是没有这种KV映射，也有可能是该key映射的值value是null，即key-null的映射。也就是说，使用get方法并不能判断这个key是否存在，只能通过containsKey方法来实现。

put函数

V put(K key, V value) 存放键值对

计算key的哈希值，找到哈希表中对应的槽，遍历该链表，如果发现已经存在包含该key的Node，则把新的value放入该结点中，返回该结点的旧value值（旧value可能是null），如果没有找到，则创建新结点插入到 链表尾端 （java7使用的是头插法），返回null。插入结点后需要判断该链表是否需要树化，并且判断整个哈希表是否需要扩容。

由该算法可以看出，哈希表中不会有两个key相同的键值对。

resize函数

    resize函数用来初始化或扩容table数组。主要做了两件事。

1.根据table数组是否为空判断初始化还是扩容，计算出相应的newCap和newThr，新建table数组并设置新的threshold。

2.若是进行扩容，则需要将原数组中的Node移植到新的数组中。

由于数组扩容，原来键值对可能存储在新数组不同的槽中。但由于键值对位置是对数组容量取余（index=hash(key)&(Capacity-1)）,由于Capacity固定为2的整数次幂，并新的Capacity（newCap）是旧的两倍（oldCap）。因此，只需要判断每个Node中的hash值在oldCap二进制那一位上是否为0(hash&oldCap==0)，若为0，对newCap取余值与oldCap相同，Node在新数组中槽的位置不变，若为1，新的位置是就得位置加一个oldCap值。

因此hashMap的移植算法是，遍历旧的槽：

若槽为空，跳过。

若槽只有一个Node，计算该Node在新数组中的位置，放入新槽中。

若槽是一个链表，则遍历这个链表，分别用loHead，loTail,hiHead,hiTail两组指针建立两个链表，把hash值oldCap位为0的Node节点放入lo链表中，hash值oldCap位为1的节点放入hi链表中，之后将两个链表分别插入到新数组中，实现原键值对的移植。

lo链表放入新数组原来位置，hi链表放入新数组原来位置+oldCap中

树化过程 ：

当一个槽中结点过多时，哈希表会将链表转换为红黑树，此处挖个坑。

[总结] java8中hashMap的实现原理与7之间的区别：

1.hash值的计算方法不同 2.链表采用尾插法，之前是头插法 3.加入了红黑树结构

㈢ 怎么看hashmap和hashtable的源码

HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap准许空（Null）键值（Key），由于非线程安全，效率上可能高于Hashtable。我回答的通俗易懂把！！！

㈣ concurrenthashmap线程安全吗

ConcurrentHashMap 是 Java 并发包中提供的一个线程安全且高效的 HashMap 实现，以弥补 HashMap 不适合在并发环境中操作使用的不足，本文就来分析下 ConcurrentHashMap 的实现原理，并对其实现原理进行分析！

一、摘要
在之前的集合文章中，我们了解到 HashMap 在多线程环境下操作可能会导致程序死循环的线上故障！

既然在多线程环境下不能使用 HashMap，那如果我们想在多线程环境下操作 map，该怎么操作呢？

想必阅读过小编之前写的《HashMap 在多线程环境下操作可能会导致程序死循环》一文的朋友们一定知道，其中有一个解决办法就是使用 java 并发包下的 ConcurrentHashMap 类！

今天呢，我们就一起来聊聊 ConcurrentHashMap 这个类！

二、简介
众所周知，在 Java 中，HashMap 是非线程安全的，如果想在多线程下安全的操作 map，主要有以下解决方法：

第一种方法，使用Hashtable线程安全类；

第二种方法，使用Collections.synchronizedMap方法，对方法进行加同步锁；

第三种方法，使用并发包中的ConcurrentHashMap类；

在之前的文章中，关于 Hashtable 类，我们也有所介绍，Hashtable 是一个线程安全的类，Hashtable 几乎所有的添加、删除、查询方法都加了synchronized同步锁！

相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞等待需要的锁被释放，在竞争激烈的多线程场景中性能就会非常差，所以 Hashtable 不推荐使用！


再来看看第二种方法，使用Collections.synchronizedMap方法，我们打开 JDK 源码，部分内容如下：


可以很清晰的看到，如果传入的是 HashMap 对象，其实也是对 HashMap 做的方法做了一层包装，里面使用对象锁来保证多线程场景下，操作安全，本质也是对 HashMap 进行全表锁！

使用Collections.synchronizedMap方法，在竞争激烈的多线程环境下性能依然也非常差，所以不推荐使用！

上面 2 种方法，由于都是对方法进行全表锁，所以在多线程环境下容易造成性能差的问题，因为** hashMap 是数组 + 链表的数据结构，如果我们把数组进行分割多段，对每一段分别设计一把同步锁，这样在多线程访问不同段的数据时，就不会存在锁竞争了，这样是不是可以有效的提高性能？**

再来看看第三种方法，使用并发包中的ConcurrentHashMap类！

ConcurrentHashMap 类所采用的正是分段锁的思想，将 HashMap 进行切割，把 HashMap 中的哈希数组切分成小数组，每个小数组有 n 个 HashEntry 组成，其中小数组继承自ReentrantLock（可重入锁），这个小数组名叫Segment， 如下图：



当然，JDK1.7 和 JDK1.8 对 ConcurrentHashMap 的实现有很大的不同！

JDK1.8 对 HashMap 做了改造，当冲突链表长度大于 8 时，会将链表转变成红黑树结构，上图是 ConcurrentHashMap 的整体结构，参考 JDK1.7！

我们再来看看 JDK1.8 中 ConcurrentHashMap 的整体结构，内容如下：


JDK1.8 中 ConcurrentHashMap 类取消了 Segment 分段锁，采用 CAS + synchronized 来保证并发安全，数据结构跟 jdk1.8 中 HashMap 结构类似，都是数组 + 链表（当链表长度大于 8 时，链表结构转为红黑二叉树）结构。

ConcurrentHashMap 中 synchronized 只锁定当前链表或红黑二叉树的首节点，只要节点 hash 不冲突，就不会产生并发，相比 JDK1.7 的 ConcurrentHashMap 效率又提升了 N 倍！

说了这么多，我们再一起来看看 ConcurrentHashMap 的源码实现。

三、JDK1.7 中的 ConcurrentHashMap
JDK 1.7 的 ConcurrentHashMap 采用了非常精妙的分段锁策略，打开源码，可以看到 ConcurrentHashMap 的主存是一个 Segment 数组。


我们再来看看 Segment 这个类，在 ConcurrentHashMap 中它是一个静态内部类，内部结构跟 HashMap 差不多，源码如下：


存放元素的 HashEntry，也是一个静态内部类，源码如下：


HashEntry和HashMap中的 Entry非常类似，唯一的区别就是其中的核心数据如value ，以及next都使用了volatile关键字修饰，保证了多线程环境下数据获取时的可见性！

从类的定义上可以看到，Segment 这个静态内部类继承了ReentrantLock类，ReentrantLock是一个可重入锁，如果了解过多线程的朋友们，对它一定不陌生。

ReentrantLock和synchronized都可以实现对线程进行加锁，不同点是：ReentrantLock可以指定锁是公平锁还是非公平锁，操作上也更加灵活，关于此类，具体在以后的多线程篇幅中会单独介绍。

因为ConcurrentHashMap的大体存储结构和HashMap类似，所以就不对每个方法进行单独分析介绍了，关于HashMap的分析，有兴趣的朋友可以参阅小编之前写的《深入分析 HashMap》一文。

ConcurrentHashMap 在存储方面是一个 Segment 数组，一个 Segment 就是一个子哈希表，Segment 里维护了一个 HashEntry 数组，其中 Segment 继承自 ReentrantLock，并发环境下，对于不同的 Segment 数据进行操作是不用考虑锁竞争的，因此不会像 Hashtable 那样不管是添加、删除、查询操作都需要同步处理。

理论上 ConcurrentHashMap 支持 concurrentLevel（通过 Segment 数组长度计算得来） 个线程并发操作，每当一个线程独占一把锁访问 Segment 时，不会影响到其他的 Segment 操作，效率大大提升！

上面介绍完了对象属性，我们继续来看看 ConcurrentHashMap 的构造方法，源码如下：


this调用对应的构造方法，源码如下：


从源码上可以看出，ConcurrentHashMap 初始化方法有三个参数，initialCapacity（初始化容量）为 16、loadFactor（负载因子）为 0.75、concurrentLevel（并发等级）为 16，如果不指定则会使用默认值。

其中，值得注意的是 concurrentLevel 这个参数，虽然 Segment 数组大小 ssize 是由 concurrentLevel 来决定的，但是却不一定等于 concurrentLevel，ssize 通过位移动运算，一定是大于或者等于 concurrentLevel 的最小的 2 的次幂！

通过计算可以看出，按默认的 initialCapacity 初始容量为 16，concurrentLevel 并发等级为 16，理论上就允许 16 个线程并发执行，并且每一个线程独占一把锁访问 Segment，不影响其它的 Segment 操作！

从之前的文章中，我们了解到 HashMap 在多线程环境下操作可能会导致程序死循环，仔细想想你会发现，造成这个问题无非是 put 和扩容阶段发生的！

那么这样我们就可以从 put 方法下手了，来看看 ConcurrentHashMap 是怎么操作的？

3.1、put 操作
ConcurrentHashMap 的 put 方法，源码如下：


从源码可以看出，这部分的 put 操作主要分两步：

定位 Segment 并确保定位的 Segment 已初始化；

调用 Segment 的 put 方法；

真正插入元素的 put 方法，源码如下：



从源码可以看出，真正的 put 操作主要分以下几步：

第一步，尝试获取对象锁，如果获取到返回 true，否则执行scanAndLockForPut方法，这个方法也是尝试获取对象锁；

第二步，获取到锁之后，类似 hashMap 的 put 方法，通过 key 计算所在 HashEntry 数组的下标；

第三步，获取到数组下标之后遍历链表内容，通过 key 和 hash 值判断是否 key 已存在，如果已经存在，通过标识符判断是否覆盖，默认覆盖；

第四步，如果不存在，采用头插法插入到 HashEntry 对象中；

第五步，最后操作完整之后，释放对象锁；

我们再来看看，上面提到的scanAndLockForPut这个方法，源码如下：


scanAndLockForPut这个方法，操作也是分以下几步：

当前线程尝试去获得锁，查找 key 是否已经存在，如果不存在，就创建一个 HashEntry 对象；

如果重试次数大于最大次数，就调用lock()方法获取对象锁，如果依然没有获取到，当前线程就阻塞，直到获取之后退出循环；

在这个过程中，key 可能被别的线程给插入，所以在第 5 步中，如果 HashEntry 存储内容发生变化，重置重试次数；

通过scanAndLockForPut()方法，当前线程就可以在即使获取不到segment锁的情况下，完成需要添加节点的实例化工作，当获取锁后，就可以直接将该节点插入链表即可。

这个方法还实现了类似于自旋锁的功能，循环式的判断对象锁是否能够被成功获取，直到获取到锁才会退出循环，防止执行 put 操作的线程频繁阻塞，这些优化都提升了 put 操作的性能。

3.2、get 操作
get 方法就比较简单了，因为不涉及增、删、改操作，所以不存在并发故障问题，源码如下：



由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以不会读取到过期数据。

3.3、remove 操作
remove 操作和 put 方法差不多，都需要获取对象锁才能操作，通过 key 找到元素所在的 Segment 对象然后移除，源码如下：


与 get 方法类似，先获取 Segment 数组所在的 Segment 对象，然后通过 Segment 对象去移除元素，源码如下：


先获取对象锁，如果获取到之后执行移除操作，之后的操作类似 hashMap 的移除方法，步骤如下：

先获取对象锁；

计算 key 的 hash 值在 HashEntry[]中的角标；

根据 index 角标获取 HashEntry 对象；

循环遍历 HashEntry 对象，HashEntry 为单向链表结构；

通过 key 和 hash 判断 key 是否存在，如果存在，就移除元素，并将需要移除的元素节点的下一个，向上移；

最后就是释放对象锁，以便其他线程使用；

四、JDK1.8 中的 ConcurrentHashMap
虽然 JDK1.7 中的 ConcurrentHashMap 解决了 HashMap 并发的安全性，但是当冲突的链表过长时，在查询遍历的时候依然很慢！

在 JDK1.8 中，HashMap 引入了红黑二叉树设计，当冲突的链表长度大于 8 时，会将链表转化成红黑二叉树结构，红黑二叉树又被称为平衡二叉树，在查询效率方面，又大大的提高了不少。


因为 HashMap 并不支持在多线程环境下使用， JDK1.8 中的 ConcurrentHashMap 和往期 JDK 中的 ConcurrentHashMa 一样支持并发操作，整体结构和 JDK1.8 中的 HashMap 类似，相比 JDK1.7 中的 ConcurrentHashMap， 它抛弃了原有的 Segment 分段锁实现，采用了 CAS + synchronized 来保证并发的安全性。

JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量，和 JDK1.7 一样，使用volatile关键字，保证多线程操作时，变量的可见行！


其他的细节，与 JDK1.8 中的 HashMap 类似，我们来具体看看 put 方法！

4.1、put 操作
打开 JDK1.8 中的 ConcurrentHashMap 中的 put 方法，源码如下：



当进行 put 操作时，流程大概可以分如下几个步骤：

首先会判断 key、value 是否为空，如果为空就抛异常！

接着会判断容器数组是否为空，如果为空就初始化数组；

进一步判断，要插入的元素f，在当前数组下标是否第一次插入，如果是就通过 CAS 方式插入；

在接着判断f.hash == -1是否成立，如果成立，说明当前f是ForwardingNode节点，表示有其它线程正在扩容，则一起进行扩容操作；

其他的情况，就是把新的Node节点按链表或红黑树的方式插入到合适的位置；

节点插入完成之后，接着判断链表长度是否超过8，如果超过8个，就将链表转化为红黑树结构；

最后，插入完成之后，进行扩容判断；

put 操作大致的流程，就是这样的，可以看的出，复杂程度比 JDK1.7 上了一个台阶。

4.1.1、initTable 初始化数组
我们再来看看源码中的第 3 步 initTable()方法，如果数组为空就初始化数组，源码如下：


sizeCtl 是一个对象属性，使用了 volatile 关键字修饰保证并发的可见性，默认为 0，当第一次执行 put 操作时，通过Unsafe.compareAndSwapInt()方法，俗称CAS，将 sizeCtl修改为 -1，有且只有一个线程能够修改成功，接着执行 table 初始化任务。

如果别的线程发现sizeCtl<0，意味着有另外的线程执行 CAS 操作成功，当前线程通过执行Thread.yield()让出 CPU 时间片等待 table 初始化完成。

4.1.2、helpTransfer 帮组扩容
我们继续来看看 put 方法中第 5 步helpTransfer()方法，如果f.hash == -1成立，说明当前f是ForwardingNode节点，意味有其它线程正在扩容，则一起进行扩容操作，源码如下：



这个过程，操作步骤如下：

第 1 步，对 table、node 节点、node 节点的 nextTable，进行数据校验；

第 2 步，根据数组的 length 得到一个标识符号；

第 3 步，进一步校验 nextTab、tab、sizeCtl 值，如果 nextTab 没有被并发修改并且 tab 也没有被并发修改，同时 sizeCtl < 0，说明还在扩容；

第 4 步，对 sizeCtl 参数值进行分析判断，如果不满足任何一个判断，将sizeCtl + 1, 增加了一个线程帮助其扩容;

4.1.3、addCount 扩容判断
我们再来看看源码中的第 9 步 addCount()方法，插入完成之后，扩容判断，源码如下：



这个过程，操作步骤如下：

第 1 步，利用 CAS 将方法更新 baseCount 的值

第 2 步，检查是否需要扩容，默认 check = 1，需要检查；

第 3 步，如果满足扩容条件，判断当前是否正在扩容，如果是正在扩容就一起扩容；

第 4 步，如果不在扩容，将 sizeCtl 更新为负数，并进行扩容处理；

put 的流程基本分析完了，可以从中发现，里面大量的使用了CAS方法，CAS 表示比较与替换，里面有 3 个参数，分别是目标内存地址、旧值、新值，每次判断的时候，会将旧值与目标内存地址中的值进行比较，如果相等，就将新值更新到内存地址里，如果不相等，就继续循环，直到操作成功为止！

虽然使用的了CAS这种乐观锁方法，但是里面的细节设计的很复杂，阅读比较费神，有兴趣的朋友们可以自己研究一下。

4.2、get 操作
get 方法操作就比较简单了，因为不涉及并发操作，直接查询就可以了，源码如下：


从源码中可以看出，步骤如下：

第 1 步，判断数组是否为空，通过 key 定位到数组下标是否为空；

第 2 步，判断 node 节点第一个元素是不是要找到，如果是直接返回；

第 3 步，如果是红黑树结构，就从红黑树里面查询；

第 4 步，如果是链表结构，循环遍历判断；

4.3、reomve 操作
reomve 方法操作和 put 类似，只是方向是反的，源码如下：


replaceNode 方法，源码如下：



从源码中可以看出，步骤如下：

第 1 步，循环遍历数组，接着校验参数；

第 2 步，判断是否有别的线程正在扩容，如果是一起扩容；

第 3 步，用 synchronized 同步锁，保证并发时元素移除安全；

第 4 步，因为 check= -1，所以不会进行扩容操作，利用 CAS 操作修改 baseCount 值；

五、总结
虽然 HashMap 在多线程环境下操作不安全，但是在 java.util.concurrent 包下，java 为我们提供了 ConcurrentHashMap 类，保证在多线程下 HashMap 操作安全！

在 JDK1.7 中，ConcurrentHashMap 采用了分段锁策略，将一个 HashMap 切割成 Segment 数组，其中 Segment 可以看成一个 HashMap， 不同点是 Segment 继承自 ReentrantLock，在操作的时候给 Segment 赋予了一个对象锁，从而保证多线程环境下并发操作安全。

但是 JDK1.7 中，HashMap 容易因为冲突链表过长，造成查询效率低，所以在 JDK1.8 中，HashMap 引入了红黑树特性，当冲突链表长度大于 8 时，会将链表转化成红黑二叉树结构。

在 JDK1.8 中，与此对应的 ConcurrentHashMap 也是采用了与 HashMap 类似的存储结构，但是 JDK1.8 中 ConcurrentHashMap 并没有采用分段锁的策略，而是在元素的节点上采用 CAS + synchronized 操作来保证并发的安全性，源码的实现比 JDK1.7 要复杂的多。

㈤ hashmap和concurrenthashmap的区别，hashmap的底层源码

你好。 有并发访问的时候用ConcurrentHashMap，效率比用锁的HashMap好 功能上可以，但是毕竟ConcurrentHashMap这种数据结构要复杂些，如果能保证只在单一线程下读写，不会发生并发的读写，那么就可以试用HashMap。ConcurrentHashMap读不加锁，写...

㈥ HashMap底层实现原理剖析

Hashmap是一种非常常用的、应用广泛的数据类型，最近研究到相关的内容，就正好复习一下。网上关于hashmap的文章很多，但到底是自己学习的总结，就发出来跟大家一起分享，一起讨论。

1.HashMap的数据结构：在java 中 数据结构，最基本 也就两种 一种数组 一种模拟指针。所有的数据结构都可以用这两个基本结构来构造的，hashmap也不例外。Hashmap实际上是一个数组和链表的结合体。数组的默认长度为16，

2.hashMap源码解析

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 初始化容量大小 

static final int MAXIMUM_CAPACITY = 1 << 30; ///容器最大值

static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载影子

static final Entry[] EMPTY_TABLE = {}; //null 的hashMap

transient Entry[] table = (Entry[]) EMPTY_TABLE;///动态扩大容器时使用的一个hashMap

transient int size;//当前数据量

int threshold;//扩大容器时的大小 为 capacity * load factor

final float loadFactor;//使用率阀值，默认为：DEFAULT_LOAD_FACTOR

存取元素 ：调用put方法

public V put(K key, V value) { 

//判断当前table 为Null 第一次Put 

 if (table == EMPTY_TABLE) {

     inflateTable(threshold);  //初始化容器的大小

 }

 if (key == null) 

 return putForNullKey(value); //判断当前key 为null 将Null key添加到数组的第一个位置

 int hash = hash(key); //将当前key进行hash 详情见下方

 int i = indexFor(hash, table.length); //调用完hash算法后，详情见下方

 for (Entry e = table[i]; e != null; e = e.next) { //循环判断当前数组下标为Entry的实体 将当前key相同的替换为最新的值

            Object k;

            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {

                V oldValue = e.value;

                e.value = value;

                e.recordAccess(this);

                return oldValue;

            }

        }

        modCount++;

        addEntry(hash, key, value, i); //如果key都不同 则添加Entry.详情见下方

        return null;

    }

hashMap的hash算法剖析

final int hash(Object k) {

        int h = hashSeed;

        if (0 != h && k instanceof String) {  //判断当前k是否为string 和

            return sun.misc.Hashing.stringHash32((String) k); //使用stringHash32算法得出key   的hash值

        }

        h ^= k.hashCode(); //调用key的hashCode 得出值 后使用"或"运算符 

        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

一个十进制数32768(二进制1000 0000 0000 0000)，经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗？或许这样还看不出什么，再举个数字61440(二进制1111 0000 0000 0000)，运算结果是65263(二进制1111 1110 1110 1111)，现在应该很明显了，它的目的是让“1”变的均匀一点，散列的本意就是要尽量均匀分布。使用上述算法后 "1"就变得很均匀了。

我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素（这个元素是HashMap内部定义的一个类Entity， 基本结构它包含三个类，key，value和指向下一个Entity的next）,没有的话就创建一个Entity对象，在 table[index]位置上插入，这样插入结束；如果有的话，通过链表的遍历方式去逐个遍历，看看有没有已经存在的key，有的话用新的value替 换老的value；如果没有，则在table[index]插入该Entity，把原来在table[index]位置上的Entity赋值给新的 Entity的next，这样插入结束

    }

indexFor 返回当前数组下标 ，

static int indexFor(int h, int length) {

        return h & (length-1);

    }

那么得到key 之后的hash如何得到数组下标呢 ？把h与HashMap的承载量（HashMap的默认承载量length是16，可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。）进行逻辑与运算，即 h & (length-1)，这样得到的结果就是一个比length小的正数，我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index，这是HashTable的改进，HashTable中的算法只是把key的 hashcode与length相除取余，即hash % length，这样有可能会造成index分布不均匀。

首先来解释一下为什么数组大小为2的幂时hashmap访问的性能最高？

看下图，左边两组是数组长度为16（2的4次方），右边两组是数组长度为15。两组的hashcode均为8和9，但是很明显，当它们和1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hashcode的值会与14（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！ 

void addEntry(int hash, K key, V value, int bucketIndex) {

  //// 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);

            hash = (null != key) ? hash(key) : 0;

          //// 设置“bucketIndex”位置的元素为“新Entry”，// 设置“e”为“新Entry的下一个节点”

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

//将当前key 和value添加到Entry[]中

void createEntry(int hash, K key, V value, int bucketIndex) { 

        Entry e = table[bucketIndex];  //将第一个就得table 复制个新的entry 

        table[bucketIndex] = new Entry<>(hash, key, value, e); //将当前新的Entry 复制个table[bucketIndex]  旧的table[bucketIndex] 和新的table[buckIndex]之间用next关联。第一个键值对A进来，通过计算其key的hash得到的index=0，记做:table[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做: B.next = A ,table[0] = B,如果又进来C,index也等于0,那么 C.next = B ,table[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起

        size++; //容量加1

    }

以上就是HashMap添加元素时的过程解析

那么如何get元素呢？

public V get(Object key) {

 if (key == null) return getForNullKey(); //当前key是否为null 如果为null值返回table[0]这个value

    Entry entry = getEntry(key);

        return null == entry ? null : entry.getValue();

    }

final EntrygetEntry(Object key) {

 if (size == 0) { return null; }  //判断容量是否大于0 

 int hash = (key == null) ? 0 : hash(key); //对当前key 进行hash hash后得到一个值

 for (Entry e = table[indexFor(hash, table.length)]; //获取当前Entry 循环遍历

            e != null;

            e = e.next) {

            Object k;

            if (e.hash == hash &&

                ((k = e.key) == key || (key != null && key.equals(k))))

                return e;

        }

        return null;

    }

扩展问题:

1.当前我们的hashMap中越来越大的之后，"碰撞"就越来越明显，那么如何解决碰撞呢？扩容！

当hashmap中的元素个数超过数组大小capti*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题

HashMap的两种遍历方式

第一种

Map map = newHashMap();

Iterator iter = map.entrySet().iterator();

while(iter.hasNext()) {

Map.Entry entry = (Map.Entry) iter.next();

Object key = entry.getKey();

Object val = entry.getValue();

}

效率高,以后一定要使用此种方式！

第二种

Map map = newHashMap();

Iterator iter = map.keySet().iterator();

while(iter.hasNext()) {

Object key = iter.next();

Object val = map.get(key);

}

效率低,以后尽量少使用！

归纳

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，

也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

㈦ 2021-01-18：java中，HashMap的创建流程是什么

jdk1.7创建流程：
三种构造器。
1.初始容量不能为负数，默认16。
2.初始容量大于最大容量时，初始容量等于最大容量。
3.负载因子必须大于0，默认0.75。
4.根据初始容量算出容量，容量是2的n次幂。
5.设置负载因子loadFactor 。
6.设置容量极限threshold。
7.设置table数组。
8.调用init()空方法。
参数为集合的构造器。
1.调用有两个参数的构造器。
2.inflateTable方法。初始化table数组。
3.putAllForCreate方法。遍历参数，放入当前map。
jdk1.8创建流程：
两种构造器。
1.初始容量不能为负数，默认16。
2.初始容量大于最大容量时，初始容量等于最大容量。
3.负载因子必须大于0，默认0.75。
4.设置负载因子loadFactor 。
5.设置容量极限threshold，调用tableSizeFor方法，大于initialCapacity的最小的二次幂数值 。。
无参构造器。
1.只设置了负载因子，其他什么都没做。
参数为集合的构造器。
1.设置负载因子。
2.putMapEntries方法。遍历参数，放入当前map。
***
[HashMap源码分析（jdk7）](https://www.cnblogs.com/fsmly/p/11278561.html)
[JDK1.8中的HashMap实现](https://www.cnblogs.com/doufuyu/p/10874689.html)
[评论](https://user.qzone.qq.com/3182319461/blog/1610924590)

㈧ java查看hashmap的源码发现并没有向entrySet中装入元素，而去可以如下遍历。

帮助文档上说：返回此映射所包含的映射关系的
collection
视图。在返回的集合中，每个元素都是一个
Map.Entry。
entrySet仅仅是一个视图而已，没有具体的数据，其实还是从HashMap中获取数据的。具体可以看entry和entrySet的源代码就知道数据其实还是来自于table。

㈨ 同步的数据结构，例如concurrenthashmap的源码理解以及内部实现原理，为什么他是同

nized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。ConcurrentHashMap内部使用段(Segment)来表示这些不同的部分，每个段其实就是一个小的hash table，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。
有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组