hash表
哈希冲突
在哈希表中，我们可以利用哈希函数快速访问到数组中的目标数据。如果发生哈希冲突，就使用链表进行存储，这样一来，不管数据量为多少，我们都能够灵活应对。
如果数组的空间太小，使用哈希表的时候就容易发生冲突，线性查找的使用频率也会更高；反过来，如果数组的空间太大，就会出现很多空箱子，造成内存的浪费。因此，给数组设定合适的空间非常重要。
在存储数据的过程中，如果发生冲突，可以利用链表在已有数据的后面插入新数据来解决冲突，这种方法被称为链表法，也被称为链地址法。
其中在 Java 集合类的 HashMap 中解决冲突的方法就是采用的链表法，建议阅读 HashMap 源码。
除了链地址法以外，还有几种解决冲突的方法。其中，应用较为广泛的是开放地址法，或称为开放寻址法。这种方法是指当冲突发生时，立刻计算出一个候补地址（数组上的位置）并将数据存进去。如果仍然有冲突，便继续计算下一个候补地址，直到有空地址为止，可以通过多次使用哈希函数或线性探测法等方法计算候补地址。
在 Java 中，ThreadLocal 所使用的就是开放地址法。
哈希函数设计的好坏决定了哈希冲突的概率，也就决定哈希表的性能。
总结
这篇文章主要讲了一些比较基础的哈希表知识，包括哈希表的由来、哈希冲突的解决方法。
哈希表也叫散列表，来源于数组]它借助哈希函数对数组这种数据结构进行扩展，利用的是数组支持按照下标随机访问元素的特性，是存储 Key-Value 映射的集合。
哈希表两个核心问题是哈希函数设计和哈希冲突解决。对于某一个 Key，哈希表可以在接近 O(1) 的时间内进行读写操作。哈希表通过哈希函数实现 Key 和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。哈希函数设计的好坏决定了哈希冲突的概率，也就决定哈希表的性能。
有兴趣的可以在 JDK 中阅读 HashMap 的源码，在 JDK 8 和之前的版本的实现还有许多不多，比如在 JDK 8 中，引入红黑树，当链表长度太长（默认超过 8）时，链表就转换为红黑树，就可以利用红黑树快速增删改查的特点，提高 HashMap 的性能。
微信打赏