C++ Hash表与哈希表数据分布

在C++中，哈希表（Hash Table）是一种使用哈希函数将键（Key）映射到值（Value）的数据结构

1. 哈希函数：哈希函数是将输入的键转换为数组索引的关键部分。一个好的哈希函数应该能够将输入均匀地分布在整个数组中，以减少冲突的可能性。C++标准库中的std::hash模板类可以用于生成哈希值。

2. 冲突解决策略：当两个不同的键具有相同的哈希值时，会发生冲突。C++中的哈希表通常使用以下两种策略之一来解决冲突：

   • 链地址法（Separate Chaining）：在这种方法中，哈希表的每个索引都包含一个链表。当发生冲突时，新的键值对将被添加到该索引的链表中。C++中的std::list或std::vector可以作为链表实现。
   • 开放寻址法（Open Addressing）：在这种方法中，当发生冲突时，会尝试在数组中找到另一个空闲的位置来存储键值对。开放寻址法有多种实现方式，如线性探测、二次探测和双散列等。

3. 负载因子：负载因子是哈希表中已存储元素数量与数组大小之比。负载因子越高，冲突的可能性越大。通常，当负载因子超过某个阈值（例如0.7或0.8）时，哈希表会进行扩容以提高性能。

4. 动态调整：为了保持哈希表的性能，可以根据负载因子动态调整数组的大小。当负载因子过高时，可以增加数组的大小并重新哈希所有元素；当负载因子过低时，可以减小数组的大小以节省空间。

总之，C++中的哈希表通过使用哈希函数、冲突解决策略、负载因子和动态调整等方法来实现高效的数据分布和快速查找。