C++中Hash表与哈希表扩展

在C++中，哈希表（Hash Table）是一种数据结构，它提供了快速的插入、删除和查找操作

1. 动态扩容：当哈希表的负载因子（即已存储元素数量与表大小的比值）超过某个阈值时，可以通过重新分配更大的内存空间并将所有元素复制到新的内存空间来扩展哈希表。这样可以保持较低的负载因子，从而确保操作的高效性。在C++中，可以使用std::unordered_map和std::unordered_set，它们会在需要时自动扩展哈希表。

2. 开放寻址法：当发生哈希冲突（两个不同的元素具有相同的哈希值）时，开放寻址法会尝试在哈希表中寻找另一个可用的空槽位。常见的开放寻址策略有线性探测、二次探测和双重散列。C++的std::unordered_map和std::unordered_set使用的是开放寻址法来解决哈希冲突。

3. 链地址法：链地址法是另一种解决哈希冲突的方法。在这种方法中，哈希表的每个槽位都包含一个链表或其他动态数据结构，用于存储具有相同哈希值的元素。当发生冲突时，新元素将被添加到链表的末尾。C++的std::unordered_map和std::unordered_set实际上是基于链地址法实现的，但它们使用开放寻址法来解决哈希冲突。

4. 自定义哈希函数：为了提高哈希表的性能，可以根据具体应用场景自定义哈希函数。一个好的哈希函数应该能够将输入数据均匀地分布在整个哈希表中，以减少冲突的可能性。在C++中，可以为std::unordered_map和std::unordered_set提供自定义的哈希函数和相等比较函数。

5. 哈希表与红黑树结合：在某些情况下，可以将哈希表与红黑树结合使用。当哈希表的负载因子超过某个阈值时，可以将具有相同哈希值的所有元素存储在一个红黑树中。这样可以确保在查找、插入和删除操作中保持对数时间复杂度。C++的std::unordered_map和std::unordered_set在负载因子超过一定阈值时会自动将链表转换为红黑树。