大白话解释哈希碰撞是什么以及如何解决

大白话解释哈希碰撞是什么以及如何解决

引用

CSDN

1.

https://blog.csdn.net/weixin_44129618/article/details/122499313

哈希表（Hash Table）是计算机科学中一种非常重要的数据结构，广泛应用于各种场景中的数据存储和检索。本文将用通俗易懂的语言，为您解释哈希表的基本原理、什么是哈希碰撞，以及如何解决哈希碰撞问题。

一、哈希表如何存数据

哈希表的本质其实就是数组，哈希表中通常存放的是键值对Entry。

这里的id是个key，哈希表就是根据key值来通过哈希函数计算得到一个值，这个值就是下标值，用来确定这个Entry要存放在哈希表中哪个位置。

二、哈希碰撞

哈希碰撞指的是，两个不同的值（比如张三、李四的id）经过哈希计算后，得到的哈希值相同，后来的李四要放到原来的张三的位置，但是数组的位置已经被张三占了，导致冲突。

三、解决方法

3.1 开放寻址法

开放寻址法指的是，当前数组位置1被占用了，就放到下一个位置2上去，如果2也被占用了，就继续往下找，直到找到空位置。

3.2 拉链法

将所有关键字为同义词的记录存储在同一线性链表中。

拉链法采用的是链表的方式，这个时候位置4就不单单存放的是Entry了，此时的Entry还要额外保存一个next指针，指向数组外的另一个位置，将李四安排在这里，张三那个Entry中的next指针就指向李四的这个位置，也就是保存的这个位置的内存地址。

如果还有冲突，就把又冲突的那个Entry放到一个新位置上，然后李四的Entry指向它，这样就形成一个链表。