Skip to main content

数据结构：哈希表 (Hash Table)

Aiden L.7/15/24About 1 min数据结构数据结构哈希表键值对

什么是哈希表？

哈希表（或哈希映射）是一种实现关联数组抽象数据类型的数据结构，它可以将“键”映射到“值”。它使用哈希函数将键计算出一个索引（哈希码），并用这个索引来快速访问存储在数组中的值。

核心概念

  1. 哈希函数: 一个能将任意大小的数据映射到固定大小值的函数。一个好的哈希函数应该尽可能地将键均匀分布。
  2. 哈希冲突: 当两个不同的键经过哈希函数计算后得到相同的索引时，就发生了哈希冲突。
  3. 冲突解决方法:
    • 链地址法 (Chaining): 在每个数组索引位置，存储一个链表（或其他数据结构），所有哈希到该索引的键值对都放在这个链表中。
    • 开放地址法 (Open Addressing): 当发生冲突时，在数组中寻找下一个可用的空位来存储该键值对。

C++ STL 中的 std::unordered_map

std::unordered_map 是 C++ 中哈希表的实现。

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> student_scores;

    // 插入
    student_scores["Alice"] = 95;
    student_scores["Bob"] = 88;
    student_scores.insert({"Charlie", 92});

    // 访问
    std::cout << "Alice's score: " << student_scores["Alice"] << std::endl;

    // 查找
    if (student_scores.find("David") == student_scores.end()) {
        std::cout << "David not found." << std::endl;
    }

    // 遍历
    for (const auto& pair : student_scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

复杂度分析

  • 平均时间复杂度 (插入、删除、查找): O(1)。
  • 最坏时间复杂度: O(n)，当所有键都哈希到同一个索引，且使用链地址法时。