数据结构之Hash表！

Hash表叫做散列表，就是把任意长度的输入，通过散列算法，变成固定长度输出，该输出结果是散列值。

这种转换是一种压缩映射，散列表的空间通常小于输入的空间，不同的输入可能会散列成相同的输出。

  • 所以不能从散列表来唯一的确定输入值，这就出现了Hash冲突。

Hash冲突：

根据Key（键）即经过一个函数F(key)得到的结果的作为地址去存放当前的Key，Value键值对。

但是却发现算出来的地址上已经被占用了，这就是所谓的Hash冲突。

解决Hash冲突：

再Hash法：

再散列法，当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1。

如果p1仍然冲突，再以p1为基础，产生另一个哈希地址p2，直到找出一个不冲突的哈希地址pi。

链地址法：

将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。

  • 因而查找、插入和删除主要在同义词链中进行。

链地址法适用于经常进行插入和删除的情况。

建立公共溢出区：

将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。