很多时候我们在编程中都能听到 Hash 这个词，那么什么是 Hash 表呢？

一、什么是 Hash 表

Hash 表又叫散列表，是先将原数据按照 Hash 函数运算之后得到 HashCode，再按 HashCode 进行排序后组成的表。 因此散列表可以实现类似数组一样的数据结构，通过下标直接访问数据。

二、Hash 函数如何设计呢?

Hash 函数的设计主要尊从以下几个原则

• 运算占用资源小
• 生成的 Hash Code 要尽可能的均匀分布

如果 Hash 函数太过于复杂，计算 Hash Code 就会消耗掉更多的计算资源。这会是 Hash 表的性能下降。 Hash Code 分布不均可能导致某个 Hash Code 对应多条数据，而其他 Hash Code 却为空的情况。我们将它称为 Hash 表数据冲突 。 这时 Hash 表的利用率就非常低了。

三、Hash 表数据冲突如何解决

Hash 表的长度是固定且有限的，在实际应用中不同数据也可能得到相同的 Hash 值。这个时候我们就需要通过其他方式来解决 Hash 表的数据冲突。

1.开放寻址法

开发寻址的核心就是"换"，当某个 HashCode 中已经有值的时候，相同 Hash Code 的下一条数据就会被放到最近的一个空位置中。 使用这种方式会让数据冲突的可能性越来越大。

2.链表法

链表法就是使用指针，让对应多个数据的 HashCode 指向一条链表。 进行操作时，我们先找到对应的 HashCode ，再到对应的链表上查找对应的值。 这时 Hash 表的查询操作的时间复杂度为 O(n)。 因此，当 Hash 表中的链表长度过长时，我们可以同过两种思路来降低时间复杂度。

一种思路我们可以对链表进行排序，在查找数据时就可以使用二分查找。 另一种思路就是用红黑树来替换掉链表。

在 JDK1.8 以后的 Java 中，HashMap 就使用了这种方式来解决 HashCode 冲突。 当链表长度大于 8 时(8 只是默认值，可以修改)，链表就会转换为红黑树。 当红黑树结点个数小于 8 时，又会将红黑树转换为链表。 以此提升效率。

链表法虽然会多占用指针的空间，但在大部分场景下，指针占用的空间和数据空间相比显得微不足道。因此链表法是最常见的解决 HashCode 冲突的方法。

四、Hash 表扩容问题

装载因子 = 填入表中的元素个数 / Hash 表的长度

装载因子越大，就表示数据冲突的可能性越大。 因此，当装载因子达到某个阈值的时候，就需要对其进行扩容操作。 在进行扩容时，重新计算 HashCode 会消耗大量的资源，因此线上环境建议使用动态扩容策略 建立一个新的 Hash 表用于存放新数据，每当插入一条新数据就将一条旧的数据从旧表迁移到新表中。

五、并发版 HashMap——ConcurrentHashMap

HashMap 并非是线程安全的，在并发更新的情况下 HashMap 可能会出现死循环或者更新丢失的问题。因此 JDK 还为我们提供了一个线程安全的 HashMap——ConcurrentHashMap。

那么 ConcurrentHashMap 是如何解决并发的问题呢？

1. 分段锁

将一个 Hash 表分为多个段，每一段有一个独立的锁。
在进行操作时，多个段之间可以并行的进行读写操作。

public ConcurrentHashMap(int initialCapacity,float loadFactor,int concurrencyLevel)

默认情况下，段是 16 个。我们可以指定 concurrencyLevel 指定预估的并行线程数

2. 读不需要锁

只有写操作需要获取锁，读不需要。（CAS）
在 JDK 1.8 中，ConcurrentHashMap 也做了优化，在 Hash 冲突比较严重时，会将链表转换成平衡二叉排序树。(HashMap 是将单链表转换成红黑树)