|
哈希冲撞
其实哈希表这个数据结构就像一个函数一样，传入一个key，返回一个结果经过哈希函数计算的一个值，那么我们的要求就是当我们输入2个相同key的时候，返回的值应该是相同的，当我们输入的key是不同的时候，返回的一个值应该是相同的，这个时候，我们设计的哈希表才算是成功了。
但是实践的时候我们会发现，很多时候，我们会发现输入2个不同的key，会返回2个相同的值，这个时候就出现了哈希冲撞。
我们解决的方法有2种
-
开放寻址法： 只要出现哈希冲撞，就通过重新探测新的位置的方法来解决冲突。
当我们向哈希表插入数据的时候，一个数据经过哈希函数的计算之后，对应的位置已经有了数，那么它会直接从这个位置开始，在数组中依次查找空的位置，直到找到新的位置为止。
当我们向哈希表中查找一个值的时候，我们先经过哈希函数计算出对应的值，然后和数组中对应的位置去比较，如果相同，就说明这就是我们要查找的元素，否则，我们就从这个位置之后的地方顺序查找，直到找到对应的数据，如果没有，就说明这个值不存在。
当我们在哈希表中删除一个值的时候，不能直接取把这个地方的值变为0，而是要把这个地方标记为deleted，这是为了查找的准确，当我们查找到这个位置为deletde的时候，我们会继续往下遍历，不会停下。
2.链表法：
其实最底层就是一个桶中放一个链表，这个桶其实也可以说成是数组，也就是当我们经过哈希函数算出值之后，如果出现重复，那么我们就将重复的数放到链表中，然后插入，删除，查找就是先找到这个桶，然后再到这里面的链表中去寻找。
|