哈希表(散列表Hash table，也叫哈希表 )

bucket（或称为"桶"）通常指的是哈希表中的一个位置，它可以存储一个或多个键值对。

哈希表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中的bucket来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

详细可见此篇文章:
https://zhuanlan.zhihu.com/p/346539485

链表:

在理想的情况下，哈希函数将每个键均匀地散列到哈希表的各个位置。但在实际中，我们可能会遇到两个不同的键计算出相同的哈希值，这就是所谓的“哈希冲突”。HashMap通过使用链表来解决这个问题。

当哈希冲突发生时，HashMap会在冲突的bucket位置增加一个链表，新的元素会被添加到链表的末尾。每个链表中的元素都包含了相同哈希值的键值对。所以在查找元素时，如果遇到哈希冲突，HashMap需要进行一次线性查找。

哈希冲突（Hash Collision）是指在使用哈希表存储数据时，两个或多个不同的键（Key）被哈希函数映射到同一个位置的情况。这种情况会导致数据的存储和查找变得复杂，因此需要采取一些措施来解决哈希冲突。如何解决哈希冲突?详细见此博客http://t.csdnimg.cn/kt4B6

红黑树:

从Java 8开始，如果链表的长度超过一定的阈值（默认为8），那么链表会被转换为红黑树。红黑树是一种自平衡的二叉查找树，通过保持树的平衡，可以提高查找效率。

树化的规则:当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化

退化的规则:

情况 1 ：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表

情况 2 ： remove 树节点时，若 root 、 root.left 、 root.right 、 root.left.left 有一个为 null ，也会退化为链表

(3)hashMap扩容

何时扩容?

JDK8扩容分两种情况，一种是元素个数超过阈值需要扩容 ,(threshold)阈值为数组长度乘以负载因子(loadFactor)，loadFactor默认是0.75f
一种是当链表上的元素大于8，数组个数还没到达64，无法转化为红黑树，也会进行扩容。

HashMap的扩容公式：Capacity * loadFactor = HashMap

其中initailCapacity是初始容量：默认值为16（懒加载机制，只有当第一次put的时候才创建）

初始容量和负载因子也可以自己设定的

HashMap 的 table 的容量如何确定？loadFactor 是什么？该容量如何变化？这种变化会带来什么问题？

// HashMap 的 table 的容量如何确定？

table 数组大小是由 capacity 这个参数确定的，默认是 16 ，也可以构造时传入，最大限制是 1 << 30 ；

// loadFactor 是什么？

loadFactor 是装载因子，主要目的是用来确认 table 数组是否需要动态扩展，默认值是 0 . 75 ，比如

table 数组大小为 16 ，装载因子为 0.75 时， threshold 就是 12 ，当 table 的实际大小超过 12

时， table 就需要动态扩容；

// 该容量如何变化？

扩容时，调用 resize () 方法，将 table 长度变为原来的两倍（注意是 table 长度，而不是

threshold ）

// 这种变化会带来什么问题？

如果数据很大的情况下，扩展时将会带来性能的损失，在性能要求很高的地方，这种损失很可能很致命。

扩容原理:

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

扩容使用的是位运算，因为用乘法会影响CPU的性能，计算机不支持乘法运算，最终都会转化为加法运算。

容量扩展的特性:

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

hashMap的扩容为什么总是2的次幂?

容量为2的幂数则可以使元素均匀的散布hashmap中，减少hash碰撞。
hashMap确定元素位置: (n-1)&hash
向集合中添加元素时，会使用(n - 1) & hash的计算方法来得出该元素在集合中的位置。只有当对应位置的数据都为1时，运算结果也为1，当HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞

(4)JDK1.8 中 HashMap 的 put()，get() 方法具体的一个执行流程

// put() 方法：

1. 计算 Key 的 hash 值，结合数组长度，计算得桶下标；

(( key . hashCode () ^ ( key . hashCode () >>> 16 )) & ( table . length - 1 ))

2. 如果 Key 的 hash 值未发生碰撞，直接放入桶中；

3. 如果发生碰撞，并且 Key 值相同，则替换 Value ；

4. 如果发生碰撞，并且 Key 值不相同，则插入链表的尾部（尾插法）或者红黑树中（树的添加方式）；

5. 如果碰撞导致链表长度大于 TREEIFY_THRESHOLD = 8 并且数组总容量大于 64 时，就把链表转换成红

黑树；

6. 当桶中的元素个数大于 capacity * loadfactor 时，容器会进行扩容 resize 为 2 n ，并重新计算每

个节点的 hash 值。

// get() 方法：

1. 计算 Key 的 hash 值，从而获取该键值所在链表的数组下标；

2. 顺序遍历链表， equals () 方法查找相同 Node 链表中 K 值对应的 V 值。

(5)线程安全问题

jdk1.7和jdk1.8中HashMap都是线程不安全的.

HashMap 并不是线程安全的，因为在多线程环境下，多个线程同时对同一个HashMap进行操作可能会导致数据不一致

需要注意的是，虽然 HashMap 并不是线程安全的，但是在单线程环境下使用是安全的。如果不需要在多线程

环境下对 HashMap 进行修改，可以将其声明为 final，从而避免意外的修改。

为什么是不安全的,详细请见此篇文章:http://t.csdnimg.cn/NFdFn

'解决线程安全的方式:'

比如使用HashTable
使用Collection.synchronizedMap
使用ConcurrentHashMap

在使用HashTable或者Collection.synchronizedMap中，这两者有着共同的问题：那就是性能问题。

无论读操作还是写操作，它们都会给整个集合进行加锁，导致同一时间内其他的操作进入阻塞状态。

那么在并发环境下，能够兼顾线程安全和运行效率的情况下就要使用concurrentHashMap

ConcurrentHashMap与HashMap的区别:

ConcurrentHashMap是线程安全的数组，它采用分段锁保证安全性。容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这样便可以有效地提高并发效率。
而HashMap不是线程安全，没有锁机制，在多线程环境下会导致数据覆盖之类的问题，所以在多线程中使用HashMap是会抛出异常的。
ConcurrentHashMap对整个桶数组进行了分段；而HashMap则没有对整个桶数组进行分段。

(6)HashMap的相关面试题:

什么对象可以作为HashMap的key值？

从HashMap的语法上来讲，一切对象都可以作为Key值。如：Integer、Long、String、Object等。但是在实际工作中，最常用的使用String作为Key值。

String作为不可变对象，一旦创建就不可修改。这为HashMap的使用带来了一定的安全性。由于Key的不可变性，我们无法在HashMap中修改已存在的Key的值，这避免了在使用可变对象作为Key时可能引发的问题。

同时，String类已经实现了equals()和hashCode()方法，确保了Key的比较和哈希计算的正确性。

使用Object作为Key值的时候,自定义类中的属性改变时，导致hashCode的值也发生变化，变化后，map.get(key)因为hashCode值的变化，而无法找到之前保存的value值，同样，删除也取不到值。解决方案是重写HashCode方法

2.LinkedHashMap/TreeMap/HashTable

(1)LinkedHashMap基本概念

LinkedHashMap继承于HashMap，他继承了HashMap的方法和特性，比如内部的默认初始容量、默认负载因子、扩容机制等。但是LinkedHashMap在此基础上又进行了扩展，主要提供了元素的访问顺序上的加强。

LinkedHashMap的特性：

允许key为null,value为null;
key不可以重复，value可以重复；
内部是以数组+双向链表实现的，JDK8以后加入了红黑树；
内部键值对的存储是有序的（需要注意初始化的时候accessOrder属性的设置）；
初始容量为16，负载因子为0.75，也就是当容量达到容量*负载因子的时候会扩容，一次扩容增加一倍；
内部的键值对要重写key对象重写hashCode()、equals()；

(2)TreeMap基本概念

TreeMap是一个双列集合，是Map的子类。底层由红黑树结构构成

map根据其键的自然顺序排序，或者根据map创建时提供的Comparator排序
不是线程安全的
key 不可以存入null
底层是基于红黑树实现的

TreeMap的数据结构:详细见此篇文章http://t.csdnimg.cn/3CI1m

(3)HashTable基本概念

Hashtable ，一个元老级的类，键值不能为空，与 HashMap 不同的是，方法都加

了 synchronized 同步锁，是线程安全的，但是效率上，没有 HashMap 快！同时， HashMap 是

HashTable 的轻量级实现，他们都完成了 Map 接口，区别在于 HashMap 允许 K 和 V 为空，而

HashTable 不允许 K 和 V 为空，由于非线程安全，效率上可能高于 Hashtable 。

参考资料

HashMap的底层数据结构 - Native8418的文章 - 知乎
https://zhuanlan.zhihu.com/p/636054806

hashMap扩容原理http://t.csdnimg.cn/FNTFm

http://t.csdnimg.cn/FNTFm

HashMap扩容机制 - 简书
HashMap线程安全https://blog.csdn.net/qq_44544908/article/details/129018615

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/441441

集合基础知识总结(双列集合)

一、Map

二、实现类

1.HashMap

(1)基本概念:

(2)HashMap的底层数据结构:

1.7和1.8有哪些区别?

底层实现:

链表: