HashMap

$HashMap$ 由数组和链表组成, 基于 $hash$ 算法实现的，通过键 $key$ 经过扰动函数扰动后得到 $hash$ 值, 然后再通过 $hash & (length - 1)$ 代替取模的方式进行元素定位，存储元素，在查找元素时可以通过 $key$ 直接能够定位到对应的元素，如果在没有 $hash$ 冲突的时候，时间复杂度基本就是 O(1),当发生 hash 冲突的时候，采用链地址法，将冲突的元素以链表的形式进行存储,在 $JDK1.8$ 中，当链表长度超过一定阈值时，直接进行数据结构转换，将链表转化成红黑树，红黑树是一种平衡二叉树，时间复杂度是 $O(log \ n)$

1. $HashMap$

1.1. 扰动函数

1.1.1. $h$ ^ $(h >>> 16)$

$hash$ 并不是用原有对象的 $hashcode$ 最为最终的 $hash$ 值，而是做了一定位运行

static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

$(n-1)$ 的值太小的话，$(n - 1) & hash$ 的值就完全依靠 $hash$ 的低位值，比如 $n-1$ 为 $0000\ 1111$，那么最终的值就完全依赖于 $hash$ 值的低 $4$ 位了，这样的话 $hash$ 的高位就玩完全失去了作用

$h$ ^ $(h$ >>> $16)$，通过这种方式，让高位数据与低位数据进行异或，也是变相的加大了 $hash$ 的随机性

1.1.2. $(n - 1) & hash$

通过 $(n - 1) & hash$ 即可算出在数组中的位置

• $HashMap$ 中桶数组的大小 $length$ 总是 2 的幂，此时，$(n - 1) & hash$ 等价于对 $length$ 取余。但取余的计算效率没有位运算高，所以 $(n - 1) & hash$ 也是一个小的优化

• 如果 $Length$ 为 $2$ 的次幂 则 length-1 转化为二进制必定是 $11111……$ 的形式，在于 h 的二进制与操作效率会非常的快，而且空间不浪费；如果 length 不是 2 的次幂，比如 length 为 15，则 length - 1 为 14，对应的二进制为 1110，在于 h 与操作，最后一位都为 0 ，而 0001，0011，0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！这样就会造成空间的浪费。

1.2. 如何处理哈希冲突？

1. 开放定址法

开放定址法是指当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。

线行探查法(Linear Probing)是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判新下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止

平方探测法(Quadratie Probing) 即是发生冲突时，用发生冲突的单无H(ev，加上1？、 2’等，即H(key) +13，H(key)十23，H(key) +32..直到找到
空闲单元。f()也可以构造为：士i^21=1,2,3.,k。

2. 再哈希法

再哈希法即选取若干个不同的哈希函数，在产生哈希冲突的时候计算另一个哈希函数，直到不再发生冲突为止。虽然不易发生聚集，但是增加了计算时间。

3. 建立公共溢出区

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

4. 链地址法

链地址法是指在碰到哈希冲突的时候，将冲突的元素以链表的形式进行存储。也就是凡是哈希地址为i的元素都插入到同一个链表中，元素插入的位置可以是表头（头插法），也可以是表尾（尾插法）

1.3. $HashMap$ 的扩容机制

Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否发生了hash冲突。

1.3.1. $JDK7$ 的扩容机制

JDK7 的扩容机制相对简单:

• 第一次 $Put$ 时会初始化数组，其容量变为 不小于指定容量的 2 的幂数。然后根据负载因子确定阈值。
• 如果不是第一次扩容，则 ，

在准备好新的数组后，$Map$ 会遍历数组的每个桶，然后遍历桶中的每个 $Entity$，重新计算其 $hash$ 值，找到新数组中的对应位置，以头插法插入新的链表

• 因为是头插法，因此新旧链表的元素位置会发生转置现象。
• 元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转）

1.3.2. $JDK8$ 的扩容机制

$JDK8$ 则因为巧妙的设计，性能有了大大的提升:

• 空参数的构造函数: 第一次调用 put 方法时，则会开始第一次初始化扩容，长度为16。
• 有参构造函数: 用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值(threshold)。第一次调用put方法时，会将阈值赋值给容量，然后让
• 如果不是第一次扩容，则容量变为原来的 2 倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

由于数组的容量是以 2 的幂次方扩容的，


表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过 $hash$ 转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为 $10000+原坐标$，即“原长度+原坐标”

那么一个 $Entity$ 在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置

当 e.hash & oldCap = 0，则节点在新数组中的索引值与旧索引值相同。
当 e.hash & oldCap = 1，则节点在新数组中的索引值为旧索引值+旧数组容量。

1.4. $Put&Get$ 操作

1.4.1. $JDK1.7$

$Put$

• 判断当前数组是否为空，如果当前数组为空，会调用相应 resize() 方法， 初始化数组与临界值
• 如果 key 为空，则 put 一个空值进去。
• 根据当前 key 值计算出 hash 值。获取对应数组中的下标，如果当前数组单元没有放入数据，则添加数据到相应的数组单元中
• 如果桶是一个链表则需要遍历判断里面的 key 是否和传入 key 相等，如果相等则进行覆盖，并返回原来的值。

$Get$

• 首先也是根据 key 计算出 hashcode，然后定位到具体的桶中。
• 判断该位置是否为链表。
• 不是链表就根据 key、key 的 hashcode 是否相等来返回值。
• 为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
• 啥都没取到就直接返回 null

1.4.2. $JDK1.8$

$Put$

• 判断当前数组是否为空，如果当前数组为空，初始化数组与临界值
• 将元素 $key$ 经过扰动函数扰动后得到 hash 值, 然后再通过 $hash & (length - 1)$ 代替取模的方式计算插入元素的数组索引
• 插入时，需判断是否存在Hash冲突, 如果当前数组单元没有数据，则直接在该数组位置新建节点，插入完毕, 否则，代表存在Hash冲突，即当前存储位置已存在节点，则通过 equals() 判断 table[i]的元素的 key 是否与需插入的 key 一样，若相同则 直接用新 value 覆盖 旧 value
• 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
• 如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面。
• 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
• 最后判断是否需要进行扩容。

$Get$

• 首先将 key hash 之后取得所定位的桶。
• 如果桶为空则直接返回 null 。
• 否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。
• 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
• 红黑树就按照树的查找方式返回值。
• 不然就按照链表的方式遍历匹配返回值。

2. $ConcurrentHashMap$

在多线程环境下，使用 $HashMap$ 是不安全的，针对 $HashMap$ 在多线程环境下不安全这个问题，$HashMap$ 的作者认为这并不是 $bug$，而是应该使用线程安全的 $HashMap$。目前有如下一些方式可以获得线程安全的 $HashMap$

• $Collections.synchronizedMap$
• $HashTable$
• $ConcurrentHashMap$

前两种方式由于全局锁的问题，存在很严重的性能问题。所以，著名的并发编程大师 $Doug\ Lea$ 在 $JDK1.5$ 的$java.util.concurrent$ 包下面添加了一大堆并发工具。其中就包含 $ConcurrentHashMap$ 这个线程安全的 $HashMap$。

ConcurrentHashMap 是 HashMap 的线程安全版本，其内部和 HashMap 一样，也是采用了数组+链表+红黑树的方式来实现。

针对 HashTable 会锁整个 hash 表的问题，ConcurrentHashMap 提出了分段锁的解决方案, 分段锁的思想就是：锁的时候不锁整个hash表，而是只锁一部分, ConcurrentHashMap 中维护着一个 Segment 数组，Segment 本身继承了 ReentrantLock，本身就是一个锁, 在 Segment 中维护着一个 HashEntry 数组，每个 HashEntry 就代表 map 中的一个 K-V, 当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁， ConcurrentHashMap 并发程度是有segment数组来决定的，并发度一旦初始化无法扩容。

为了进一步优化性能，在 jdk1.8 版本中，对 ConcurrentHashMap 做了优化，取消了分段锁的设计，取而代之的是通过 cas 操作和 synchronized 关键字来实现优化，而扩容的时候也利用了一种分而治之的思想来提升扩容效率，在 JDK1.8 中 ConcurrentHashMap 的存储结构和 HashMap 基本一致，如下图所示：

。

$HashMap$ 是非线程安全的，在多线程的操作下会存在异常情况，可以使用 $HashTable$ 或者 $ConcurrentHashMap$ 进行代替

5.1. $HashMap$ 为啥线程不安全？

HashMap 不是一个线程安全的容器

• 不安全性体现在多线程并发对 HashMap 进行 put 操作上。如果有两个线程 A 和 B ，首先 A 希望插入一个键值对到 HashMap 中，在决定好桶的位置进行 put 时，此时 A 的时间片正好用完了，轮到 B 运行，B 运行后执行和 A 一样的操作，只不过 B 成功把键值对插入进去了。如果 A 和 B 插入的位置（桶）是一样的，那么线程 A 继续执行后就会覆盖 B 的记录，造成了数据不一致问题。

• $HashMap$ 在扩容时，因 $resize$ 方法会形成环，造成死循环，导致 $CPU$ 飙高。

  JDK1.7—>-两个线程同时并发的对原数组扩容。由于链表都使用头插法，两个线程在用指针指向后，会形成循环链表。 然后再新数据进入的时候,会先从链表上找是否存在对应的key。然后在循环链表中一直死循环，无法插入。

5.2. $Put&Get$

5.2.1. $Base1.7$

5.2.2. $Base1.8$

1. $putVal()$

   • 在 $ConcurrentHashMap$ 中不允许 key, val 字段为空，所以第一步先校验 key, value 值，key、val 两个字段都不能是 null 才继续往下走，否则直接返回一个 $NullPointerException$ 错误

     这点跟 HashMap 有区别，HashMap 是可以允许为空的

   • 判断容器是否初始化，如果容器没有初始化，则调用 initTable 方法初始化，initTable 方法如下

     Table 本质上就是一个 Node 数组，其初始化过程也就是对 Node 数组的初始化过程，方法中使用了 CAS 策略执行初始化操作。初始化流程为

     • 判断 sizeCtl 值是否小于 0，如果小于 0 则表示 $ConcurrentHashMap$ 正在执行初始化操作，所以需要先等待一会, 如果其它线程初始化失败还可以顶替上去
     • 如果 sizeCtl 值大于等于 0，则基于 $CAS$ 策略抢占标记 $sizeCtl$ 为 -1，表示 ConcurrentHashMap 正在执行初始化，然后构造 table，并更新 $sizeCtl$ 的值

   • 根据 hash 值找到数组对应的下标位置，如果该位置未存放节点，也就是说不存在 hash 冲突，则使用 CAS 无锁的方式将数据添加到容器中，并且结束循环

   • 如果并未满足第三步，则会判断容器是否正在被其他线程进行扩容操作，如果正在被其他线程扩容，则放弃添加操作，保证了容器在扩容时并不会有其他线程进行数据添加操作，这也保证了容器的安全性。

   • 如果 hash 冲突，则进行链表操作或者红黑树操作（如果链表树超过8，则修改链表为红黑树），在进行链表或者红黑树操作时，会使用 synchronized 锁把头节点被锁住了，保证了同时只有一个线程修改链表，防止出现链表成环。

   • 进行 addCount(1L, binCount) 操作，该操作会更新 size 大小，判断是否需要扩容

     addCount 方法做了两个工作： 1、对 map 的 size 加一 2、检查是否需要扩容，或者是否正在扩容。如果需要扩容，就调用扩容方法，如果正在扩容，就帮助其扩容。

5.3. $ConcurrentHashMap$ 如何保证线程的安全性$?$

在 $ConcurrentHashMap$ 中，采用了大量的分而治之的思想来降低锁的粒度，提升并发性能。其大量使用了 $cas$ 操作来保证安全性

5.3.1. 如何用 $CAS$ 保证数组初始化的安全

$ConcurrentHashMap$ 变量 sizeCtl，这个变量对理解整个 $ConcurrentHashMap$ 的原理非常重要。

sizeCtl 有四个含义：

• sizeCtl<-1 表示有 N-1 个线程正在执行扩容操作，如 -2 就表示有 2-1 个线程正在扩容。
• sizeCtl=-1 占位符，表示当前线程正在初始化数组。
• sizeCtl=0 默认状态，表示数组还没有被初始化。
• sizeCtl>0 记录下一次需要扩容的大小。

$ConcurrentHashMap$ 采用了 $CAS$ 操作，因为 sizeCtl 默认为 0，如果可以替换成功，则当前线程可以执行初始化操作，CAS 失败，说明其他线程抢先一步把 sizeCtl 改为了 -1。扩容成功之后会把下一次扩容的阈值赋值给 sizeCtl

5.3.2. $Put$ 操作如何保证数组元素的可见性

如果发现当前节点元素为空，也是通过 $CAS$ 操作来存储当前元素。

如果当前节点元素不为空，则会使用 $synchronized$ 关键字锁住当前节点，并进行对应的设值操作, 每次只锁住一个下标，锁的粒度更细了。所以最多可以支持的并发数比 $1.7$ 版本的分段设计更多了

5.3.4. $ConcurrentHashMap$ 的扩容

$ConcurrentHashMap$ 中采用的是分段扩容法，支持多线程同时进行, 即每个线程负责一段，默认最小是 $16$ ，也就是说如果 $ConcurrentHashMap$ 中只有 $16$ 个槽位，那么就只会有一个线程参与扩容。如果大于 $16$ 则根据当前 $CPU$ 数来进行分配，最大参与扩容线程数不会超过 $CPU$ 数。

扩容空间和 $HashMap$ 一样，每次扩容都是将原空间大小扩大为之前的两倍，接下来就是要准备确认边界。

• 每个线程会先领取自己的任务区间 $[bound,i]$，然后开始 –i 来遍历自己的任务区间，对每个桶进行处理。如果遇到桶的头结点是空的，那么使用 $ForwardingNode$ 标识旧 $table$ 中该桶已经被处理完成了。如果遇到已经处理完成的桶，直接跳过进行下一个桶的处理。如果是正常的桶，对桶首节点加锁，正常的迁移即可，迁移结束后依然会将原表的该位置标识位已经处理。
• 在数据转移的过程中会加 synchronized 锁，锁住头节点，防止向链表插入数据
• 进行数据迁移，如果这个桶上的节点是链表或者红黑树，则会将节点数据分为低位和高位，计算的规则是通过该节点的 hash 值跟为扩容之前的 table 容器长度进行位运算（&），如果结果为 0 ，则将数据放在新表的低位（当前 table 中为 第 i 个位置，在新表中还是第 i 个位置），结果不为 0 ，则放在新表的高位（当前 table 中为第 i 个位置，在新表中的位置为 i + 当前 table 容器的长度）
• 如果桶挂载的是红黑树，不仅需要分离出低位节点和高位节点，还需要判断低位和高位节点在新表以链表还是红黑树的形式存放。

$HashMap$ 的线程安全问题大部分出在扩容 $(rehash)$ 的过程中。$ConcurrentHashMap$ 的扩容只针对每个 $segment$ 中的$HashEntry$ 数组进行扩容。

5.4. $ConcurrentHashMap$ 的 $get$ 方法是否要加锁$?$

ConcurrentHashMap的get方法就是从Hash表中读取数据，并不会与扩容不冲突，因此该方法也不需要同步锁，这样可提高ConcurrentHashMap 的并发性能。

5.5. 总结

1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率$O(logn)$，甚至取消了 $ReentrantLock$ 改为了 $synchronized$

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，

• 相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。
• 数据结构：取消了 $Segment$ 分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。
• 保证线程安全机制：$JDK1.7$ 采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
• 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。
• 链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
• 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

3. LinkedHashMap

HashMap 是一个无序的 Map，因为每次根据 key 的 hashcode 映射到 Entry 数组上，所以遍历出来的顺序并不是写入的顺序。$LinkedHashMap$ 是 HashMap 的子类,在原有 HashMap 数据结构的基础上,它还维护着一个双向链表链接所有 entry,这个链表定义了迭代顺序

LinkedHashMap 的排序方式有两种

• 根据写入顺序排序。

• 根据访问顺序排序。

  其中根据访问顺序排序时，每次 $get$ 都会将访问的值移动到链表末尾，这样重复操作就能的到一个按照访问顺序排序的链表。

LinkedHashMap相对于HashMap的源码比，是很简单的。因为大树底下好乘凉。它继承了HashMap，仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与HashMap相比最大的不同。

在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。

• accessOrder ,默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。为true时，可以在这基础之上构建一个LruCache.
• LinkedHashMap并没有重写任何put方法。但是其重写了构建新节点的newNode()方法.在每次构建新节点时，将新节点链接在内部双向链表的尾部
• accessOrder=true的模式下,在afterNodeAccess()函数中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。值得注意的是，afterNodeAccess()函数中，会修改modCount,因此当你正在accessOrder=true的模式下,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
• nextNode() 就是迭代器里的next()方法 。
  该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
  而双链表节点的顺序在LinkedHashMap的增、删、改、查时都会更新。以满足按照插入顺序输出，还是访问顺序输出。
• 它与HashMap比，还有一个小小的优化，重写了containsValue()方法，直接遍历内部链表去比对value值是否相等。

6.1. 总结

$LinkedHashMap$ 其实就是对 $HashMap$ 进行了拓展，使用了双向链表来保证了顺序性, 因为是继承与 HashMap 的，所以一些 HashMap 存在的问题 $LinkedHashMap$ 也会存在，比如不支持并发等。$LinkedHashMap$ 的 $putXXX$ 和 $getXXX$ 都直接继承于 $HashMap$，并没有重载，其 $Put$/$Get$ 的逻辑也就和 HashMap 一样

7. $ConcurrentSkipListMap$

ConcurrentSkipListMap 是基于 TreeMap 的设计原理实现的，略有不同的是前者基于跳表实现，后者基于红黑树实现，ConcurrentSkipListMap 的特点是存取平均时间复杂度是 O（log（n）），适用于大数据量存取的场景，最常见的是基于跳跃表实现的数据量比较大的缓存。

8. $TreeMap$

$TreeMap$ 是一个通过红黑树实现有序的 $key-value$ 集合， 映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put、remove方法，它的时间复杂度是log（n）

8.2. 红黑树

红黑树是每个节点都带有颜色属性的二叉搜索树，颜色或红色或黑色。除了符合二叉搜索的基本特性外，它还附加如下性质:
①.节点是红色或黑色
②.根节点是黑色
③.每个叶节点(NIL节点，空节点)是黑色的
④.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
⑤.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

当我们对红黑树进行插入和删除等操作时，可能会破坏红黑树的性质。为了保证红黑树始终是一颗红黑树，其通过旋转、变色进行调整.而旋转又分成两种形式:

8.1. 排序规则

TreeMap 默认排序规则:按照 key 的字典顺序来排序(升序) 当然,也可以自定义排序规则：实现Comparable接口或者在创建构造器的时候给一个Comparator实例。我们每一种情况都分析一下。

8.1.1. 采用默认排序

默认的排序规则是根据 $key$ 值的首字符去进行比较判断的，并按照从小到大升序排序。

与 HashMap 相比，TreeMap 是一个能比较元素大小的 Map 集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序；

注意：使用 $TreeMap$ 所有的key都必须直接或间接的实现Comparable接口，否则会报cannot be cast to java.lang.Comparable。当然，直接采用TreeMap(Comparator<? super K> comparator)构造器也是可以的。

8.1.2. 采用Comparable接口排序

将key实现Comparable接口，重写其中的compareTo方法，定义排序的规则

class Student implements Comparable<Student>{
    String name;
    int age;
    @Override
    public int compareTo(Student o) {
        if(this.age<o.age){
            return -1;
        }else if(this.age>o.age){
            return 1;
        }
        return 0;
    }
}

当前元素小于比较元素，则返回-1，大于则返回1，否则返回0。按照TreeMap的put方法逻辑，小于0的则排在左侧，大于的排在右侧，等于的就覆盖，也就实现了升序排序，所以说，当我们想要降序排的时候，只需把自定义中的返回-1和1的替换即可

8.1.3. Comparator

public static void main(String[] args) {
    TreeMap<Object, Object> map = new TreeMap<>(new Comparator<Object>() {
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof String && o2 instanceof String) {
                return ((String) o1).compareTo((String) o2);
            } else if(o1 instanceof Long && o2 instanceof Long) {
                return ((Long) o1).compareTo((Long) o2);
            }
            return 0;
        }

    });
}

Comparable和Comparator接口是干什么的？列出它们的区别。

Java提供了只包含一个 compareTo() 方法的Comparable接口。这个方法可以个给两个对象排序。具体来说，它返回负数，0，正数来表明已经存在的对象小于，等于，大于输入对象。

Java提供了包含 compare() 和equals() 两个方法的Comparator接口。compare()方法用来给两个输入参数排序，返回负数，0，正数表明第一个参数是小于，等于，大于第二个参数。equals()方法需要一个对象作为参数，它用来决定输入参数是否和comparator相等。只有当输入参数也是一个comparator并且输入参数和当前comparator的排序结果是相同的时候，这个方法才返回true。

总结

HashMap 在 JDK1.7 和1.8有什么区别

JDK1.7 用的是头插法，而 JDK1.8 及之后使用的都是尾插法，因为 JDK1.7 是用单链表进行的纵向延伸，当采用头插法时会容易出现逆序且环形链表死循环问题。但是在 JDK1.8 之后是因为加入了红黑树使用尾插法，能够避免出现逆序且链表死循环的问题。

扩容后数据存储位置的计算方式也不一样：

1. 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行&（这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在，因为如果只有2的n次幂的情况时最后一位二进制数才一定是1，这样能最大程度减少hash碰撞）（hash值 & length-1）。

2. 而在JDK1.8的时候直接用了JDK1.7的时候计算的规律，也就是扩容前的原始位置+扩容的大小值=JDK1.8的计算方式，而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。

   在计算 hash 值的时候，JDK1.7 用了 9 次扰动处理=4 次位运算+5 次异或，而 JDK1.8 只用了2次扰动处理=1次位运算+1次异或。

3. JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）

$HashSet$

HashSet 底层基于 HashMap 实现，只能插入唯一元素，支持插入 null，不保证插入顺序。add、remove、contains、size等方法的时间复杂度都是O(1)。非线程安全，多线程使用请使用线程安全的 Collections.synchronizedSet。迭代支持快速失败，迭代过程中如果出现结构性修改会报 ConcurrentModificationException 异常。

Map是二元结构而Set是一元结构，这里使用PRESENT作为value的默认填充值，解决差异问题。

$TreeSet$

基于TreeMap实现，非线程安全，元素有序，不允许插入null值。一般在需要对非重复元素进行排序时使用TreeSet。

13485386542