admin管理员组

文章数量:1437235

【数据结构与算法】哈希表实现：闭散列 && 开散列

Ⅰ. 哈希结构

一、哈希的概念

​ 顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在 查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为 O(N)，平衡树中为树的高度，即 O(

l o g 2 n log_2 n

)，搜索的效率取决于搜索过程中元素的比较次数。

​ 理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素**。

当向该结构中：

  • 插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
  • 搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

​ 该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表（或者称散列表）

​ 例如：数据集合 {1，7，6，4，5，9}

​ 哈希函数设置为：hash(key) = key % capacity （capacity 为存储元素底层空间总的大小）

​ 用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快 问题：按照上述哈希方式，向集合中插入元素44，会出现什么问题？答案是发生哈希冲突（或哈希碰撞）！

二、哈希冲突

​ 不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为 哈希冲突 或 哈希碰撞。把具有不同关键码而具有相同哈希地址的数据元素称为 “ 同义词 ”。

❓ 发生哈希冲突该如何处理呢？哈希冲突可以被解决吗？

本文标签： 数据结构与算法哈希表实现闭散列 ampamp 开散列

版权声明：本文标题：【数据结构与算法】哈希表实现：闭散列 && 开散列 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1747431498a2696604.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。