哈希表—链地址法

冰冻非一日之寒

哈希冲突是不可避免的，所以我们在设计哈希函数的同时，也要设计解决哈希冲突的办法。

哈希表本质就是一个数组。

通过上一篇知识求出关键字所对应的索引，存储到数组中即可。素数M也是数组的长度

哈希表&数组

通过哈希函数求得的哈希值可能会是一个负数，对哈希值求绝对值即可。有时我们也会见到以下表达式

关键字&索引

哈希值按位与上一个16进制数。

原理：这个16进制数转化为2进制就是一个0，三十一个1。计算机中对整型的表示，第一个数字表示符号位(0代表整数，1代表负数)

将一个整数与之按位与后，第一位肯定是0(代表整数)，后面是整数原来的数字。即最后只是改变了整数的符号位，并将这个整数变成正整数

求绝对值

这样，就得到了一个正整数。

当两个不同的关键字求得的索引相同时，该如何存储呢？

哈希表—链地址法

开辟一个数组，有M个空间，在每一个空间中存储一个链表，这个链表实际上就是一个查找表，可以存储多个数据

哈希表—链地址法

查找表可以使用一个平衡树(红黑树)结构。

TM的底层实现是红黑树

这样，数组中的每一个空间就有一个TreeMap数组(红黑树)了。

在Java8之前，数组中每一个空间对应的就是一个链表

Java8，当哈希冲突达到一定程度后，每一个空间从链表转成红黑树

JAVA

在Java8中，为什么要有这一步的转化操作呢？

因为，当我们的数据规模比较小的时候，也就是哈希冲突比较小，使用链表可以更快的进行增删改查等操作。而使用红黑树的话，还要进行旋转操作，这反而让操作更复杂。

以上就是解决哈希冲突最常用的链地址法