hashmap的扩容机制

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

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

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

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

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

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

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

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

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

(1)存储键值对，实现快速存取数据；

(2)允许键/值为null，但不允许重复的键；

(3)非同步synchronized(比同步快)，线程不安全；

注：让HashMap同步： Map m = Collections.synchronizeMap(hashMap)

(4)实现Map接口，对键值对进行映射，不保证有序(比如插入的顺序)

注：Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。

(5)HashMap默认的容量大小是16；增加容量时，每次将容量变为“原始容量x2”

(6)HashMap添加元素时，是使用自定义的哈希算法

(1)不存储键值对，仅存储对象；

(2)不允许键/值为null；

(3)线程安全(速度慢)，采用synchronize关键字加锁原理(几乎在每个方法上都加锁)，；

(4)实现了Set接口，不允许集合中有重复的值。注：将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，

比较对象的值是否相等，以确保set中没有储存相等的对象。hashCode()可能相同，用equals()判断对象的相等性。

(5)Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”；

(6)Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。

(1)Java并发包java.util.concurrent中的一个线程安全且高效的HashMap实现

(2)不允许键/值为null；

(3)线程安全：在JDK1.7中采用“分段锁”的方式，1.8中直接采用了CAS（无锁算法）+ synchronized。

Entry：HashMap是一个用于存储Key-Value键值对的集合，每一个键值对叫做Entry，这些Entry分散存储在一个数组当中。

hashMap是在bucket中储存键对象和值对象，作为Map.Entry

bucket：HashMap初始化时，创建一个长度为capacity的Entry数组，这个数组里可以存储元素的位置被称为“桶(bucket)”，

每个bucket都有其指定索引，系统可以根据其索引快速访问该bucket里存储的元素。

loadFactor：负载因子。默认值DEFAULT_LOAD_FACTOR = 0.75f；

capacity：容量，指的是数组的长度

threshold：阈值=capacity*loadFactor。超过阈值则扩容为原来的两倍。

size：HashMap的大小，它是HashMap保存的键值对的数量。

HashMap是基于hashing的原理，底层使用哈希表结构(数组+链表)实现。使用put(key,value)存储对象，使用get(key)获取对象。

理解为，数组中存储的是一个Entry，并且作为链表头结点，头结点之后的每个节点中储存键值对对象Entry。

给put()方法传递键和值时，先对键调用hashCode()方法计算hash从而得到bucket位置，进一步存储，

HashMap会根据当前bucket的占用情况自动调整容量(超过负载因子Load Facotr则resize为原来的2倍)。

扩容扩的是数组的容量，发生碰撞后当链表长度到达8后，链表上升为红黑树，提高速度。

根据键key的hashcode找到bucket位置，然后遍历链表节点，调用equals(用来获取值对象)方法确定键值对，找到要找的值对象。

a.对key的hashCode做hash *** 作(高16bit不变，低16bit和高16bit做了一个异或)

b.计算下标(n-1) &hash，从而获得buckets的位置 //h &(length-1)

数字分析法、平方取中法、分段叠加法、 除留余数法、 伪随机数法。

其他解决hash冲突办法：开放定址法、链地址法、再哈希法。

根据hashcode来划分的数组，如果数组的坐标相同，则进入链表这个数据结构中，jdk1.7及以前为头插法，jdk1.8之后是尾插法，

在jdk1.8之后，当链表长度到达8的时候，jdk1.8上升为红黑树。存的时候按照上面的方式存，取的时候根据equals确定值对象。

1.常见问题：集合类、数据结构、线程安全、解决碰撞方法、hashing概念和方法、equals()和hashCode()的应用、不可变对象的好处

https://blog.csdn.net/weixin_42636552/article/details/82016183

https://blog.csdn.net/u012512634/article/details/72735183

https://blog.csdn.net/zaimeiyeshicengjing/article/details/81589953

https://blog.csdn.net/aura521521/article/details/78462459

原文地址： https://xeblog.cn/articles/26

通过查看 HashMap 的源码可以得知其默认的初始容量为 16 ，默认的加载因子为 0.75 。

一般情况下都是通过这三种构造方法来初始化 HashMap 的。通过默认的无参构造方法初始化后 HashMap 的容量就是默认的16，加载因子也是默认的0.75；通过带参数的构造方法可以初始化一个自定义容量和加载因子的 HashMap 。通常情况下，加载因子使用默认的0.75就好。

HashMap 的容量要求必须是2的N次幂，这样可以提高散列的均匀性，降低 Hash 冲突的风险。但是容量可以通过构造方法传入的，如果我传入一个非2次幂的数进去呢？比如3？传进去也不会干嘛呀，又不报错。。。哈哈哈哈。

是的，不会报错的，那是因为 HashMap 自己将这个数转成了一个最接近它的2次幂的数。这个转换的方法是 tableSizeFor(int cap) 。

这个方法会将传入的数转换成一个2次幂的数，比如传入的是3，则返回的是4；传入12，则返回的是16。

加载因子和 HashMap 的扩容机制有着非常重要的联系，它可以决定在什么时候才进行扩容。 HashMap 是通过一个阀值来确定是否扩容，当容量超过这个阀值的时候就会进行扩容，而加载因子正是参与计算阀值的一个重要属性，阀值的计算公式是 容量 * 加载因子 。如果通过默认构造方法创建 HashMap ，则阀值为 16 * 0.75 = 12 ，就是说当 HashMap 的容量超过12的时候就会进行扩容。

这是 HashMap 的 putVal(...) 方法的一个片段， put(...) 方法其实就是调用的这个方法， size 是当前 HashMap 的元素个数，当元素个数＋1后超过了阀值就会调用 resize() 方法进行扩容。

加载因子在一般情况下都最好不要去更改它，默认的0.75是一个非常科学的值，它是经过大量实践得出来的一个经验值。当加载因子设置的比较小的时候，阀值就会相应的变小，扩容次数就会变多，这就会导致 HashMap 的容量使用不充分，还没添加几个值进去就开始进行了扩容，浪费内存，扩容效率还很低；当加载因子设置的又比较大的时候呢，结果又很相反，阀值变大了，扩容次数少了，容量使用率又提高了，看上去是很不错，实际上还是有问题，因为容量使用的越多， Hash 冲突的概率就会越大。所以，选择一个合适的加载因子是非常重要的。

通过默认构造方法创建一个 HashMap ，并循环添加13个值

当添加第1个值后，容量为16，加载因子为0.75，阀值为12

当添加完第13个值后，执行了扩容 *** 作，容量变为了32，加载因子不变，阀值变为了24

创建一个初始容量为12（非2次幂数）的 HashMap ，并添加1个值

创建一个初始容量为2的 HashMap ，并添加2个值

当添加完第1个值后，容量为2，加载因子为0.75，阀值为1

当添加完第2个值后，执行了扩容 *** 作，容量变为4，加载因子为0.75，阀值为3

创建一个初始容量为2、加载因子为1的 HashMap ，并添加2个值

当添加完第1个值后，容量为2，加载因子为1，阀值为2

当添加完第2个值后，并没有执行扩容 *** 作，容量、加载因子、阀值均没有变化

---