哈希桶算法

散列函数

通常大家所说的哈希函数也可以称为散列函数，哈希函数的功能只是将你的目标key通过一种映射方法，也可以说是一种函数运算f，最后得到你目标的
hashValue = f(key)，这里的函数f就称为哈希函数/散列函数。

解决哈希冲突

可以看到哈希函数的选择是一个很关键的步骤。为了引进哈希桶算法，必然要介绍一下哈希冲突，因为哈希桶就是为了解决哈希冲突的。举个例子，有一组序列为[10,11,21,31,38,48,55]，使用的哈希函数为f(key) = key mod 10

image.png

这个时候就产生了冲突了，也就是不同的key通过映射后得到了同样值的hashvalue。

哈希桶算法（链地址）

哈希桶算法其实就是链地址解决冲突的方法

如上面的例子所示，就可以设置桶的个数为10，也就是f(key)集合的个数，而这样的话，hashvalue就可以作为桶的索引，将10,11分别通过f(key)得到0，1则可将这几个key放入桶0， 1的首地址所指的内存中，然后处理值为21的key，得到hashvalue值为1，这个时候需要放入桶1中，但桶1的首地址已经有了元素11，怎么办？那么就可以为每个桶开辟一片内存，内存中存放所有hashvalue相同的key，冲突的key之间用单向链表进行存储，这样就解决了哈希冲突，在查找对应key的时候，只需要通过key索引到对应的桶，然后从桶的首地址对应的节点开始查找，就是链表顺序找到，对比key的值，直到找到对应key的信息，所以，在冲突的时候，特别是冲突率比较高的时候，桶内的链表就会很长，使得查找效率比较低，而在最坏的情况下，所有的key都对应同一个hashvalue，当然这种情况不会出现，这样的哈希函数选取的也没有意义了，假设这种情况出现，那么哈希表就退化成了单链表，其他桶内存浪费，且将查找效率从O(1)直接降到了O(N)，所以上面才说，哈希函数的选择也是很关键的。

链地址缺点

如果相同元素过多，元素在一个桶内部链接过长，反而导致时间复杂度上升。解决思路是桶中元素不再指向链表，而指向一个红黑树。