开放定址法感觉不太好用，刷题也不常见，所以我就没学...就看一下拉链法好了 哈希表：拉链法笔记 1. 前提条件 哈希表本质： key ↓ hash函数 ↓ 数组下标 例如：hash(key) = key % 10 插入：21 得到：21 % 10 = 1 所以放到：table[1] 2. 核心概念 如果没有冲突： table[1] = 21 如果冲突： 21 % 10 = 1 31 % 10 = 1 41 % 10 = 1 都落到下标 1。 拉链法不是往后找空位，而是： table[1] -> 21 -> 31 -> 41 也就是：数组 + 链表 3. 结构理解 数组每个位置叫一个桶： table[0] table[1] table[2] ... 每个桶里放一条链表。 例如： 下标: 0 1 2 3 NULL 21->31->41 NULL 13->23 所以查找 31： 31 % 10 = 1 先找到：table[1] 然后在这条链表里找：21 -> 31 4. 结构体模板 这里我们存两样东西： key：数组值 value：数组下标 因为两数之和要返回原下标。 #include #include #define HASH_SIZE 10007 struct HashNode { int key; int value; struct HashNode* next; }; struct HashTable { struct HashNode* table[HASH_SIZE]; }; 5. 哈希函数 C 里面 % 遇到负数可能得到负结果，所以要处理一下。 int hash(int key) { int h = key % HASH_SIZE; if(h < 0) { h += HASH_SIZE; } return h; } 例如： key = -3 先： -3 % 10007 = -3 修正： -3 + 10007 变成合法下标。 6. 初始化哈希表 void initHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { h->table[i] = NULL; } } 意思： 每个桶一开始都是空链表 7. 查找 struct HashNode* find(struct HashTable* h, int key) { int index = hash(key); struct HashNode* cur = h->table[index]; while(cur != NULL) { if(cur->key == key) { return cur; } cur = cur->next; } return NULL; } 理解： 1. 先算桶下标 2. 找到 table[index] 3. 在链表里顺着 next 找 8. 插入 这里用头插法。 void insert(struct HashTable* h, int key, int value) { int index = hash(key); struct HashNode* node = malloc(sizeof(struct HashNode)); node->key = key; node->value = value; node->next = h->table[index]; h->table[index] = node; } 例如桶里原来： table[1] -> 21 -> 31 插入 41： node->next = table[1] table[1] = node 结果： table[1] -> 41 -> 21 -> 31 这就是链表头插法。 9. 释放哈希表 C 里 malloc 了节点，就要 free。 void freeHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { struct HashNode* cur = h->table[i]; while(cur != NULL) { struct HashNode* next = cur->next; free(cur); cur = next; } h->table[i] = NULL; } } 10. 拉链法完整模板 #include #include #define HASH_SIZE 10007 struct HashNode { int key; int value; struct HashNode* next; }; struct HashTable { struct HashNode* table[HASH_SIZE]; }; int hash(int key) { int h = key % HASH_SIZE; if(h < 0) { h += HASH_SIZE; } return h; } void initHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { h->table[i] = NULL; } } struct HashNode* find(struct HashTable* h, int key) { int index = hash(key); struct HashNode* cur = h->table[index]; while(cur != NULL) { if(cur->key == key) { return cur; } cur = cur->next; } return NULL; } void insert(struct HashTable* h, int key, int value) { int index = hash(key); struct HashNode* node = malloc(sizeof(struct HashNode)); node->key = key; node->value = value; node->next = h->table[index]; h->table[index] = node; } void freeHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { struct HashNode* cur = h->table[i]; while(cur != NULL) { struct HashNode* next = cur->next; free(cur); cur = next; } h->table[i] = NULL; } } 11. LeetCode 1 两数之和：哈希实现 核心思想 遍历每个数 nums[i]。 当前数是：x = nums[i] 想要另一个数：need = target - x 先去哈希表查：need 是否出现过 如果出现过，直接返回： need 的下标 当前 i 如果没出现过，就把当前数存进去： key = nums[i] value = i 12. 为什么先查再插？ 例如： nums = [3,3] target = 6 i = 0： x = 3 need = 3 表里没有 3。 插入： 3 -> 0 i = 1： x = 3 need = 3 查到之前的： 3 -> 0 返回： [0,1] 如果先插再查，可能会把自己和自己配对。 所以： 先查 need 再插 x 13. 两数之和 C 代码 #include #include #define HASH_SIZE 10007 struct HashNode { int key; int value; struct HashNode* next; }; struct HashTable { struct HashNode* table[HASH_SIZE]; }; int hash(int key) { int h = key % HASH_SIZE; if(h < 0) { h += HASH_SIZE; } return h; } void initHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { h->table[i] = NULL; } } struct HashNode* find(struct HashTable* h, int key) { int index = hash(key); struct HashNode* cur = h->table[index]; while(cur != NULL) { if(cur->key == key) { return cur; } cur = cur->next; } return NULL; } void insert(struct HashTable* h, int key, int value) { int index = hash(key); struct HashNode* node = malloc(sizeof(struct HashNode)); node->key = key; node->value = value; node->next = h->table[index]; h->table[index] = node; } void freeHashTable(struct HashTable* h) { for(int i = 0; i < HASH_SIZE; i++) { struct HashNode* cur = h->table[i]; while(cur != NULL) { struct HashNode* next = cur->next; free(cur); cur = next; } } } int* twoSum(int* nums, int numsSize, int target, int* returnSize) { struct HashTable h; initHashTable(&h); int* ans = malloc(2 * sizeof(int)); *returnSize = 2; for(int i = 0; i < numsSize; i++) { int x = nums[i]; int need = target - x; struct HashNode* found = find(&h, need); if(found != NULL) { ans[0] = found->value; ans[1] = i; freeHashTable(&h); return ans; } insert(&h, x, i); } *returnSize = 0; free(ans); freeHashTable(&h); return NULL; } 14. 例子流程 nums = [2,7,11,15] target = 9 i = 0： x = 2 need = 7 查 7： 没找到 插入： 2 -> 0 i = 1： x = 7 need = 2 查 2： 找到了，下标 0 返回： [0,1] 15. 易错点 1. key 和 value 不一样 在两数之和里： key = nums[i] value = i 不能只存值，因为答案要返回下标。 2. 负数 hash 要处理 int h = key % HASH_SIZE; if(h < 0) { h += HASH_SIZE; } 3. 先查再插 避免同一个元素用两次。 4. 冲突用链表解决 同一个桶里可能有多个节点： table[index] -> node1 -> node2 -> node3 查找时要遍历这条链。 笔记版总结 拉链法哈希表 -------------------------------- 结构： 数组 + 链表 数组每个位置叫桶 bucket 每个桶里是一条链表 -------------------------------- 哈希函数： index = key % HASH_SIZE -------------------------------- 冲突： 多个 key 得到同一个 index -------------------------------- 解决： 把它们挂到同一个桶的链表里 -------------------------------- 插入： 1. 计算 index 2. 创建新节点 3. 头插到 table[index] -------------------------------- 查找： 1. 计算 index 2. 遍历 table[index] 链表 3. 找到 key 返回节点 4. 找不到返回 NULL -------------------------------- 两数之和： 遍历 nums[i] x = nums[i] need = target - x 先查 need 是否出现过 如果出现过： 返回 need 的下标和 i 否则： 插入 x 和 i -------------------------------- key = 数值 value = 下标 一句话： 拉链法就是：数组快速定位桶，链表解决同桶冲突；两数之和就是边查 need，边存当前数。 看一下py的字典实现，因为内置了字典，而c需要手写底层hash def twoSum(nums, target): mp = {} for i, x in enumerate(nums): need = target - x if need in mp: return [mp[need], i] mp[x] = i