C++中的数据结构---哈希表的知识点
·
一、哈希表的基本概念
哈希表（Hash Table）是一种通过哈希函数将键映射到存储位置的数据结构，能够实现快速的数据插入、删除和查找操作。其核心思想是利用键值对的映射关系，通过哈希函数计算键的哈希值，进而确定存储位置。
二、哈希函数
哈希函数的设计是哈希表实现的关键，常见的哈希函数包括：
- 直接定址法：Hash(key) = A * key + B，适用于键分布连续的情况。
- 除留余数法：Hash(key) = key % p（p为质数），是最常用的方法之一。
- 平方取中法：对键平方后取中间几位作为哈希值，适用于键分布不均匀的情况。
- 数字分析法：根据键的各位分布特点选择均匀的位组合作为哈希值。
三、哈希冲突及解决方法
哈希冲突是指不同键通过哈希函数计算出相同的存储位置。常见的解决方法包括：
1、开放定址法：冲突时寻找下一个空闲位置存储，包括线性探测、二次探测等。
2、链地址法（哈希桶）：每个存储位置维护一个链表，冲突时将元素添加到链表中。
四、动态哈希与扩容
当哈希表的装填因子（元素数与桶数的比值）超过阈值（如0.7）时，需要进行扩容操作。扩容通常涉及重新分配更大的桶数组，并重新哈希所有元素。
五、C++中的实现
在C++中，unordered_map和unordered_set是基于哈希表实现的容器，使用哈希桶解决冲突。自定义类型作为键时，需要提供哈希函数和相等比较函数。
六、性能分析
理想情况下，哈希表的插入、删除和查找操作的时间复杂度为O(1)，但在最坏情况下（如所有键冲突）可能退化为O(n)。因此，哈希函数的设计和冲突处理策略对性能至关重要。
参考资料：
https://blog.csdn.net/weixin_45031801/article/details/141572449
https://blog.csdn.net/strive_mianyang/article/details/146720264
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
3
0- 0
已为社区贡献1条内容
所有评论(0)