一、什么是哈希表？

1.核心定义

哈希表 = 数组 + 哈希函数 + 冲突解决

哈希表是一种通过哈希函数将「键（Key）」映射到「索引（Index）」，从而实现O (1) 平均时间复杂度查找、插入、删除的数据结构。

2.核心三要素

（1）键（key） ：要存储的数据标识（如数字、字符串、对象）。

（2）哈希函数：把 Key 转换成数组下标的函数（核心！）

（3）哈希表底层：数组（利用数组随机访问特性）

3.核心优势

（1）平均：查找 / 插入 / 删除 = O(1)

（2）最坏：O (n)

（3）对比：数组查找 O (n)，链表查找 O (n)，二叉搜索树查找 O (logn)，哈希表是最快的查找数据结构！

二、哈希函数和哈希冲突

1.哈希函数（Hash Function）

作用：key -> 数组索引

公式：index = hash（key）% 数组长度

2.哈希函数（高频坑点）

（1）不处理负数key->下标越界崩溃

// ❌ 错误哈希函数
int bad_hash1(HashTable* ht, int key) {
    return key % ht->size; // 负数key → 负数下标！
}

错误原因：key = -1 % 10 = -1  →  数组下标不能为负，程序直接崩溃。

正确代码：

// ✅ 正确哈希函数
int good_hash(HashTable* ht, int key) {
    if (key < 0) key = -key; // 必须先转正数
    return key % ht->size;
}

（2）哈希函数分布不均 -> 冲突爆炸

// ❌ 错误哈希函数：所有key都返回同一个下标
int bad_hash2(HashTable* ht, int key) {
    return 0; // 所有元素都存在下标0 → 链表变成长链，O(n)复杂度
}

错误原因：冲突严重，哈希表退化为链表。

正确代码：

// 正确哈希函数：保证分布均匀 + 处理负数
int hash(HashTable* ht, int key) {
    // 1. 处理负数key，避免负数下标越界
    if (key < 0) {
        key = -key;
    }
    // 2. 取余运算：将key映射到[0, size-1]的合法下标
    // 配合质数大小的哈希表，能最大程度保证分布均匀
    return key % ht->size;
}

(3)哈希表大小用偶数 -> 冲突增多

// ❌ 不推荐
HashTable* ht = createHashTable(10); // 偶数，取余分布不均

// ✅ 推荐：质数大小
HashTable* ht = createHashTable(11); // 质数，分布均匀，冲突最少

3.哈希冲突

定义：两个不同的 Key，通过哈希函数算出了同一个索引。无法完全避免，只能解决冲突。

4.哈希冲突的解决办法

（1）链地址法（链表+数组）

数组每个位置存一个链表 / 红黑树

冲突时，把元素追加到链表后面

优点：实现简单，无空间浪费

（2）开放寻址法（纯数组）

冲突时，向后找空位置存放（线性探测 / 二次探测）

优点：无链表，内存连续

缺点：删除麻烦，容易堆积

三、哈希表基本操作总结

1.链表节点

typedef struct Node{
    int key;       //键
    int value;     //值
    struct Node* next;   //用于解决哈希冲突
}Node;

2.哈希表结构

typedef struct HashTable{
    int size;        //数组长度
    Node** table;    //指针数组（存链表头）
}HashTable;

3.哈希函数（核心公式）

正确哈希函数：abs(key) % size

作用：把任意整数 → 合法下标 [0, size-1]

必须处理负数！否则下标越界崩溃

int hash(HashTable* ht, int key) {
    if (key < 0) key = -key; // 负数转正数
    return key % ht->size;   // 取余映射下标
}

4.创建哈希表

HashTable* createHashTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->table = (Node**)malloc(sizeof(Node*) * size);

    // 初始化所有链表为空
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}

5.创建节点

Node* createNode(int key, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

6.插入（冲突处理）

void insert(HashTable* ht, int key, int value) {
    int index = hash(ht, key); // 计算下标
    Node* head = ht->table[index];

    // 遍历：key已存在则覆盖
    Node* cur = head;
    while (cur) {
        if (cur->key == key) {
            cur->value = value;
            return;
        }
        cur = cur->next;
    }

    // 头插法：新节点放链表头部
    Node* newNode = createNode(key, value);
    newNode->next = head;
    ht->table[index] = newNode;
}

7.查找

int search(HashTable* ht, int key) {
    int index = hash(ht, key);
    Node* cur = ht->table[index];

    // 遍历链表查找
    while (cur) {
        if (cur->key == key) return cur->value;
        cur = cur->next;
    }
    return -1; // 未找到
}

8.删除

void deleteKey(HashTable* ht, int key) {
    int index = hash(ht, key);
    Node* prev = NULL;
    Node* cur = ht->table[index];

    // 查找节点
    while (cur && cur->key != key) {
        prev = cur;
        cur = cur->next;
    }
    if (!cur) return; // 不存在直接返回

    // 删除节点
    if (!prev) ht->table[index] = cur->next; // 删头节点
    else prev->next = cur->next;             // 删中间节点
    free(cur);
}

9.销毁（防止内存泄露）

void destroyHashTable(HashTable* ht) {
    for (int i = 0; i < ht->size; i++) {
        Node* cur = ht->table[i];
        while (cur) {
            Node* temp = cur;
            cur = cur->next;
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}

10.一般经常会使用到的方法

int hash[N]={0}     来进行下标映射。

四、哈希表算法分类

哈希表的核心思想只有一个：把 key 转成下标，然后快速存、快速查。

数组哈希：做题比较常用，它把 “链表” 扔掉，直接用一个数组当下标映射，思想还是哈希表：key → 下标 → 存值。

1.两数之和（查找配对）

// 两数之和（数组哈希版，适合数据范围小的场景）
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* res = (int*)malloc(2 * sizeof(int));
    // 数组哈希：key=数值，value=下标（偏移量处理负数）
    int hash[200001];
    memset(hash, -1, sizeof(hash)); // 初始化为-1（表示未访问）

    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        int idx = complement + 100000;
        // 找到配对的数，返回下标
        if (hash[idx] != -1) {
            res[0] = hash[idx];
            res[1] = i;
            return res;
        }
        // 把当前数存入哈希
        int cur_idx = nums[i] + 100000;
        hash[cur_idx] = i;
    }
    return res;
}

一次遍历，哈希表 O (1) 查找，时间 O (n)。

2.频率统计（计数）

// 小写字母统计（26大小）
int hash[26] = {0};
for (int i = 0; i < strlen(s); i++) {
    hash[s[i] - 'a']++; // 字符转下标，计数+1
}

// 全ASCII字符统计（128大小，万能）
int hash[128] = {0};
for (int i = 0; i < strlen(s); i++) {
    hash[(unsigned char)s[i]]++;
}

3.去重

// 数字去重（带偏移量处理负数）
int hash[200001] = {0}; // 覆盖-100000~100000
for (int i = 0; i < numsSize; i++) {
    int idx = nums[i] + 100000; // 负数偏移转正数下标
    if (hash[idx]) return true;  // 已存在→有重复
    hash[idx] = 1;               // 标记已访问
}
return false;

4.键值映射

bool isIsomorphic(char* s, char* t) {
    int map_s[128], map_t[128];
    memset(map_s, -1, sizeof(map_s));
    memset(map_t, -1, sizeof(map_t));
    int len = strlen(s);

    for (int i = 0; i < len; i++) {
        unsigned char c1 = s[i], c2 = t[i];
        // 双向映射不一致，返回false
        if (map_s[c1] != map_t[c2]) return false;
        // 建立双向映射
        map_s[c1] = i;
        map_t[c2] = i;
    }
    return true;
}

5.前缀和+哈希表

int subarraySum(int* nums, int numsSize, int k) {
    // 数组哈希：记录前缀和出现的次数（偏移量处理负数）
    int hash[200001] = {0};
    hash[100000] = 1; // 初始前缀和为0，出现1次
    int preSum = 0, count = 0;

    for (int i = 0; i < numsSize; i++) {
        preSum += nums[i];
        // 查找preSum - k出现的次数
        int target = preSum - k;
        int idx = target + 100000;
        if (idx >= 0 && idx < 200001) {
            count += hash[idx];
        }
        // 更新当前前缀和的次数
        int cur_idx = preSum + 100000;
        hash[cur_idx]++;
    }
    return count;
}

6.滑动窗口+去重

int lengthOfLongestSubstring(char* s) {
    int hash[128]; // 记录字符最后出现的位置
    memset(hash, -1, sizeof(hash));
    int left = 0, maxLen = 0;
    int len = strlen(s);

    for (int right = 0; right < len; right++) {
        unsigned char c = s[right];
        // 字符已在窗口内，移动左指针到重复位置的下一位
        if (hash[c] >= left) {
            left = hash[c] + 1;
        }
        // 更新字符的最新位置
        hash[c] = right;
        maxLen = (right - left + 1) > maxLen ? (right - left + 1) : maxLen;
    }
    return maxLen;
}

五、高频出错点

1.C 语言必须手动 free → 内存泄漏

先 free 链表 → 再 free 数组 → 最后 free 哈希表

2.直接访问数组下标 → 空指针崩溃

ht->table[index]->key：错误

必须用search()函数安全查找：正确

3.插入重复 key 不覆盖 → 数据错误

插入前必须遍历检查，相同 key 覆盖 value

4.认为哈希表永远 O (1) → 认知错误

哈希冲突严重时 = O (n)