拉链法

开放定址法感觉不太好用，刷题也不常见，所以我就没学...就看一下拉链法好了
哈希表：拉链法笔记

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 <stdlib.h>
#include <stdbool.h>

#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 找
4. 插入

这里用头插法。

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 <stdlib.h>
    #include <stdbool.h>

#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 <stdlib.h>
#include <stdbool.h>

#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