C++ hashtable

1. 基本概念

哈希表是一种数据结构，它提供了快速的插入、查找和删除操作，其核心思想是通过一个哈希函数（Hash Function）将数据的关键键（Key）映射为一个固定长度的哈希值（Hash Value），然后利用这个哈希值来确定数据在表中的存储位置，也就是索引（Index）。

2. 哈希函数

• 作用：
  哈希函数负责把各种各样的输入键（通常键的数据类型多样，比如整数、字符串等）转化为一个相对固定范围的整数（哈希值）。理想的哈希函数应该具有以下特性：
  • 确定性：对于相同的输入键，每次计算得到的哈希值都应该相同，保证数据能准确存储和查找。
  • 均匀分布性：尽可能使不同的输入键均匀地映射到哈希表的各个存储位置上，避免出现大量数据集中映射到少数几个位置（即哈希冲突）的情况。
  • 高效性：能够快速地计算出哈希值，减少计算时间成本。
• 示例：
  • 对于整数键，简单的取模运算可以作为一种哈希函数，比如 hash(key) = key % table_size，这里 table_size 是哈希表的大小（即存储位置的总数）。
  • 对于字符串键，一种常见的做法是将字符串中每个字符的ASCII码值进行加权求和后再取模，例如：

int hash(const std::string& key)
 {
    int hash_value = 0;
    for (size_t i = 0; i < key.length(); ++i) {
        hash_value += (int)key[i] * (i + 1);
    }
    return hash_value % table_size;
}

3. 哈希冲突及解决方法

以下是几种常见的解决哈希冲突的方法：

开放定址法

• 基本原理：
  当通过哈希函数计算得到的存储位置已经被占用（即发生哈希冲突）时，按照某种探测规则在哈希表中寻找下一个空闲的存储位置来存放冲突的数据。

• 具体方式：

  • 线性探测：
    • 探测规则：在发生冲突后，依次从冲突位置往后顺序查找空闲的存储位置，也就是以固定的步长（通常为1）逐个探测后续的位置。例如，假设哈希表的大小为10，哈希函数计算出某个键对应的哈希值为3，但位置3已被占用，那么就依次检查位置4、5、6……直到找到空闲位置存放该键值对。
    • 优点：实现简单，易于理解和编码实现，不需要额外的数据结构来辅助解决冲突。
    • 缺点：容易出现数据堆积现象，也就是连续的多个键值对可能因为冲突而聚集在一起，形成较长的“聚集链”，这会导致后续的查找、插入操作效率降低，特别是在哈希表比较满的时候更为明显。例如，若很多键值对经过哈希函数计算后初始哈希值都集中在某个范围，后续采用线性探测时就容易在这一范围附近堆积大量数据。
  • 二次探测：
    • 探测规则：在发生冲突后，按照与冲突位置的距离呈二次函数关系的顺序去寻找空闲位置。通常先探测与冲突位置间隔为 (1^2)、(22)、(3^2) 等的位置，即若初始哈希值为 (h)，第一次探测位置为 (h + 1^2)，第二次探测位置为 (h + 2^2)，以此类推（也可以采用类似 (h - 1^2)、(h - 2^2) 等向前探测的方式）。例如，哈希值为5的位置冲突了，先探测 (5 + 1^2 = 6) 位置，若不行再探测 (5 + 2^2 = 9) 位置等。
    • 优点：相对线性探测而言，在一定程度上能够避免数据过度堆积的问题，使得数据在哈希表中的分布更均匀一些，从而提高查找和插入操作的效率。
    • 缺点：不能完全消除数据堆积的情况，而且计算探测位置的过程相对复杂一点，需要进行更多的计算，增加了一定的时间成本；另外，在哈希表快满时，二次探测的效果也会大打折扣，甚至可能出现无法找到空闲位置的情况（尽管这种情况相对少见）。
  • 双重哈希：
    • 探测规则：使用两个不同的哈希函数 (h_1(key)) 和 (h_2(key))，当发生冲突时，通过公式 (h(key) = (h_1(key) + i \times h_2(key)) % table_size)（其中 (i) 为探测次数，从 (0) 开始递增，(table_size) 为哈希表的大小）来确定后续的探测位置。例如，第一个哈希函数计算出初始哈希值为 (3)，第二个哈希函数计算出值为 (2)，当冲突发生时，第一次探测位置是 ((3 + 0 \times 2) % table_size)，第二次探测位置是 ((3 + 1 \times 2) % table_size) 等。
    • 优点：通过两个哈希函数的配合，能更有效地避免数据堆积，使数据在哈希表中的分布更加均匀，在合适的参数选择下，可以获得较好的查找和插入性能。
    • 缺点：需要设计和维护两个哈希函数，增加了代码实现的复杂性和计算开销；并且要合理选择两个哈希函数，否则可能达不到预期的效果，甚至可能出现循环探测找不到空闲位置的问题（不过通过合适的设计可以尽量避免这种情况）。

链地址法

• 基本原理：
  把哈希值相同的数据（键值对）用链表连接起来，形成一个个“桶”。当有新的数据产生哈希冲突时，就将其添加到对应哈希值所在的链表末尾。每个链表可以看作是一个存储具有相同哈希值的键值对的集合。

• 优点：

  • 实现相对简单，易于理解和编码实现，只需要在哈希表的基础上额外维护链表结构即可。
  • 处理冲突的效率较高，对于插入操作，只要找到对应的链表头，然后在链表末尾添加新节点即可；查找操作也是先定位到对应的链表，再在链表中顺序查找目标数据，平均查找时间复杂度取决于链表的长度，在链表长度较短时，性能较好。
  • 不会像开放定址法那样出现数据堆积影响整个哈希表性能的问题，因为每个链表相对独立，即使某个哈希值对应的链表较长，对其他哈希值对应的链表以及整个哈希表的其他操作影响不大。

• 缺点：
  需要额外的内存空间来存储链表节点，如果哈希表中存在大量的哈希冲突，导致某些链表很长，那么除了存储键值对本身的数据内存外，还会消耗较多的链表节点内存，可能在一定程度上影响内存的利用效率；另外，在链表较长时，查找操作的时间复杂度会有所增加，不过可以通过一些优化手段（如将链表转换为更高效的数据结构，像红黑树等，当链表长度超过一定阈值时进行转换）来缓解这个问题。

再哈希法

• 基本原理：
  当发生哈希冲突时，换用另一个哈希函数重新计算哈希值，期望通过新的哈希函数能够得到一个空闲的存储位置。如果新的哈希值仍然冲突，就继续更换哈希函数再次计算，直到找到空闲位置或者达到设定的最大尝试次数等限制条件为止。

• 优点：
  可以根据不同的冲突情况灵活选择不同的哈希函数来优化数据的存储位置，有可能找到更合适的、分布更均匀的存储方式，减少冲突带来的影响。

• 缺点：
  需要准备多个不同的哈希函数，增加了代码的复杂性和维护成本；而且频繁更换哈希函数会带来较高的计算开销，尤其是如果尝试多次都无法有效解决冲突时，会严重影响哈希表操作的整体效率；此外，很难保证换用的哈希函数一定能找到空闲位置，可能陷入不断尝试却始终无法妥善解决冲突的困境。

建立公共溢出区

• 基本原理：
  在哈希表之外，额外开辟一块连续的存储区域作为公共溢出区。当发生哈希冲突时，将冲突的数据统一存放到这个公共溢出区中，可以通过记录指针或者索引等方式来关联原哈希表中的位置和公共溢出区中的存储位置，便于后续查找等操作。

• 优点：
  能够保证哈希表本身的结构相对简单，不会因为解决冲突而使哈希表内部的存储结构变得复杂，便于对哈希表的其他操作（如遍历等）进行管理；而且对于公共溢出区，可以采用更灵活的存储和管理方式，比如根据数据量动态调整其大小等。

• 缺点：
  增加了额外的存储区域，需要更多的内存空间来支持；查找操作相对复杂一些，需要先在哈希表中查找，如果没找到再去公共溢出区查找，增加了一次额外的查找步骤，可能会影响查找的效率，尤其是在公共溢出区数据量较大时更为明显。

不同的哈希冲突解决方法各有优缺点，在实际应用中需要根据具体的使用场景、数据特点以及性能要求等因素综合考虑来选择合适的方法。

4. 哈希表的操作实现

• 插入操作：
  • 首先，通过哈希函数计算要插入数据的键对应的哈希值，确定其在哈希表中的大致存储位置。
  • 如果该位置没有数据（不存在哈希冲突），则直接将数据存储在该位置；如果发生哈希冲突，根据所采用的冲突解决方法（如开放定址法进行探测找空闲位置，或者链地址法添加到对应链表末尾等）来妥善放置数据。
• 查找操作：
  • 同样先利用哈希函数算出要查找数据的键对应的哈希值，定位到对应的存储位置或“桶”。
  • 如果是采用开放定址法解决冲突，按照相应的探测规则查找目标数据；如果是链地址法，就在对应的链表中逐个查找，直到找到目标数据或者遍历完链表确定未找到。
• 删除操作：
  • 先通过哈希函数找到目标数据所在位置，再依据冲突解决方式来进行删除。对于开放定址法，要谨慎处理删除后的空闲位置标记等问题，避免影响后续查找等操作的正确性；对于链地址法，直接从链表中删除相应节点即可。

5. 内存管理及优化

• 在内存中，哈希表的存储结构根据实现方式有所不同。采用开放定址法时，通常就是一个连续的数组结构来存放数据；采用链地址法时，除了有用于存储数据大致位置的数组（存放指向链表头的指针等），还需要为各个链表分配额外的内存空间用于存储节点。
• 为了优化哈希表的性能，可以根据实际应用场景合理选择哈希函数、冲突解决方法以及哈希表的大小等参数。例如，根据预估的数据量来调整哈希表大小，避免过于频繁的哈希冲突；定期对哈希表进行重构（比如重新计算哈希值、调整存储位置等）来优化数据分布，提高整体效率。

总之，哈希表通过巧妙地运用哈希函数和解决哈希冲突的机制，实现了高效的数据存储、查找和删除操作，在众多领域如数据库、编译器、缓存系统等都有着广泛的应用。

哈希表的时间复杂度在不同操作以及不同情况下有所差异，以下是对其插入、查找和删除操作时间复杂度的详细分析：

时间复杂度

理想情况（无哈希冲突或冲突极少）

• 插入操作：
  在理想状态下，通过哈希函数能将每个键均匀且唯一地映射到哈希表的不同位置，插入操作只需要计算键对应的哈希值，然后将数据存放到对应的位置即可，这个过程通常可以在常数时间 (O(1)) 内完成。例如，有一个足够大且设计良好的哈希表，插入少量不同的键值对时，几乎不会产生哈希冲突，每次插入都能迅速定位到空闲位置进行存储。
• 查找操作：
  同样，当不存在哈希冲突时，查找一个键对应的键值对，只需根据键计算出哈希值，然后直接访问该哈希值对应的位置就能确定是否找到目标，时间复杂度也是 (O(1))。就好比在一个完美的哈希表中找某个元素，一次定位就能知晓结果。
• 删除操作：
  类似于插入和查找操作，若没有哈希冲突，通过哈希值定位到要删除的数据所在位置后，直接进行删除处理，时间复杂度同样为 (O(1))。

一般情况（考虑哈希冲突及解决方法）

• 开放定址法：
  • 插入操作：
    平均情况下，插入操作的时间复杂度接近 (O(1))，不过在最坏情况下，如果哈希表接近满或者哈希函数设计不佳导致大量冲突，插入操作可能需要多次探测空闲位置，时间复杂度会退化为 (O(n))，其中 (n) 是哈希表的大小。例如，采用线性探测且不断有数据集中在少数几个哈希值对应的位置附近，插入新数据时可能要线性遍历很长一段已占用的位置去寻找空闲处。
  • 查找操作：
    平均情况下，查找操作的时间复杂度大约是 (O(1))，但在最坏情况下，比如数据聚集严重，查找一个键可能需要遍历哈希表中的大部分位置，时间复杂度会达到 (O(n))。
  • 删除操作：
    平均时间复杂度接近 (O(1))，然而在最坏情况下，由于要谨慎处理删除后留下的空闲位置（避免影响后续查找等操作的正确性，可能需要对后续数据进行重新整理等操作），时间复杂度也可能退化为 (O(n))。
• 链地址法：
  • 插入操作：
    插入操作首先要通过哈希函数定位到对应的链表，这个过程通常是 (O(1))，然后在链表末尾添加节点，平均时间复杂度取决于链表的平均长度，设链表平均长度为 (k)，则插入操作的平均时间复杂度为 (O(1 + k))，在链表较短时，可近似看作 (O(1))。例如，一个哈希表采用链地址法，大部分链表长度较短，插入新键值对时找到对应链表后很快就能添加进去。
  • 查找操作：
    先通过哈希函数定位到链表是 (O(1))，然后在链表中查找目标键值对，平均时间复杂度同样取决于链表平均长度 (k)，为 (O(1 + k))，若 (k) 较小，可认为接近 (O(1))，但在链表很长时，时间复杂度会升高，最坏情况下如果链表长度达到 (n)（哈希表大小），时间复杂度就是 (O(n))。
  • 删除操作：
    先定位到链表是 (O(1))，然后在链表中删除相应节点，平均时间复杂度取决于链表平均长度 (k)，为 (O(1 + k))，类似查找操作，在不同链表长度情况下表现不同。

综合来看

哈希表在设计良好（哈希函数合理、冲突解决方法得当、哈希表大小合适等）的情况下，插入、查找和删除操作的平均时间复杂度都能接近 (O(1))，这使得它在很多需要快速查找、插入和删除数据的场景中有着广泛的应用。不过在极端或不良的条件下（比如哈希函数选择不当、数据量远超哈希表承载能力等），时间复杂度可能会恶化，所以在实际应用中要综合考虑各方面因素来优化哈希表的性能。