Hash 算法
【摘要】 🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
Hash:
hash算法解决冲突的方法常用的有开放定址法、再哈希法、链地址法、 建立公共溢出区。
哈希表：
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
1.开放定址法
开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
公式：Hi = (H(key) + di) MOD m （i=1,2,…,k(k<=m-1)）
m为哈希表的长度，di是产生冲突时候的增量序列。
线性探测再散列：di 的取值为1,2,3……m-1；
二次探测再散列：1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k <= m/2)；
伪随机探测再散列：di 是一组为随机数；
2. 再哈希法
再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3. 链地址法（拉链法）
基本思想：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，如下图所示：
4. 建立公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）