C语言HashTable基本理解

哈希表概念

1. 哈希表的基本概念

​ 哈希表（Hash Table），也称为散列表，是一种根据键（Key）直接访问存储位置的数据结构。它通过哈希函数（Hash Function）将键映射到一个固定大小数组的索引上，这个数组被称为哈希表，存储在该索引位置的数据被称为值（Value）。

2. 哈希表的核心组件

2.1 哈希函数

​ 哈希函数是哈希表的核心，它的作用是将键转换为哈希表中的一个索引。一个好的哈希函数应该满足以下几个条件：

• 确定性：对于相同的键，哈希函数必须始终返回相同的索引。
• 均匀性：哈希函数应该尽可能均匀地将键分布到哈希表的各个位置，以减少冲突的发生。
• 高效性：哈希函数的计算应该尽可能快，以保证哈希表的操作效率。

​ 常见的哈希函数有取模法，例如 index = key % table_size，其中 key 是键，table_size 是哈希表的大小。

2.2 冲突处理（哈希碰撞）

​ 如图所示：当目标数组经过Hash Function将Key转化为Hash Table的Index时，有可能发生重复利用一个Index的情况，若不采取操作，可能会覆盖原来存储的数据，我最常用的是采用链表的方法，即在Hash Table每个Index所指的地方维护一个链表，将具有相同Index的数据存放到链表中。

​ 由于哈希函数的映射是多对一的，不同的键可能会映射到相同的索引，这种情况称为冲突。常见的冲突处理方法有以下两种：

• 开放地址法：当发生冲突时，通过某种探测方法（如线性探测、二次探测等）寻找下一个空闲的位置来存储数据。
• 链地址法：在哈希表的每个位置上维护一个链表（或其他数据结构），当发生冲突时，将具有相同哈希值的数据存储在该位置的链表中。

3.哈希表的三种结构

哈希结构（Hash Structures）是计算机科学中非常重要的数据结构，主要用于高效地存储和查找数据。以下是三种最常见的哈希结构及其详细介绍和示例。

（1）数组作为哈希表

特点：

• 适用于键的范围已知且较小的情况
• 直接使用数组索引作为键
• 访问时间复杂度：O(1)

适用场景：

• 字符统计（如小写字母统计）
• 固定范围的数字统计

示例：

    const count: number[] = new Array(26).fill(0);

（2）Set（集合）

特点：

• 存储唯一值
• 快速判断元素是否存在
• 添加、删除、查找时间复杂度：O(1)

适用场景：

• 去重
• 快速查找元素是否存在

示例：

    const numSet = new Set<number>();

在 TypeScript 中，const numSet = new Set<number>(); 创建了一个强类型的集合（Set），它只能存储 数值类型（number） 的元素。下面详细解释其功能、用法和注意事项：

1. Set 基础概念

Set 是 ES6 引入的一种数据结构，类似于数组，但具有以下特点：

• 元素唯一：不允许重复值。
• 无序性：元素没有固定顺序。
• 高效查找：基于哈希表实现，插入、删除、查找的时间复杂度接近 O (1)。

（3）Map（字典）

特点：

• 存储键值对
• 键可以是任意类型（对象引用需注意）
• 添加、删除、查找时间复杂度：O(1)

适用场景：

• 需要保存键值映射关系
• 统计频率
• 缓存

示例：

    const numMap = new Map<number, number>();

在 TypeScript 中，const numMap = new Map<number, number>(); 创建了一个强类型的映射（Map），它只能存储 键和值均为数值类型（number） 的键值对。下面详细解释其功能、用法和注意事项：

1. Map 基础概念

Map 是 ES6 引入的一种数据结构，类似于对象（Object），但具有以下特点：

• 键的类型灵活：键可以是任意类型（对象、函数、基本类型等），而对象的键只能是字符串或 Symbol。
• 有序性：按插入顺序存储键值对，遍历时顺序与插入顺序一致。
• 高效查找：基于哈希表实现，插入、删除、查找的时间复杂度接近 O (1)。

三种哈希结构对比

结构	特点	适用场景	时间复杂度
数组	键为数字索引，内存连续	有限范围的键，如字母统计	O(1)
Set	存储唯一值	去重，存在性检查	O(1)
Map	存储键值对，键可以是任意类型	需要键值映射关系的场景	O(1)

4. C 语言实现哈希表（使用链地址法）

4.1 代码示例

// 定义哈希表节点结构
typedef struct HashNode {int key;int value;struct HashNode* next;
} HashNode;// 定义哈希表结构
typedef struct HashTable {int size;HashNode** table;
} HashTable;

1. 哈希表节点（HashNode）
   • 包含三个字段：key（键）、value（值）和next（指向下一个节点的指针）。
   • 通过链表结构处理哈希冲突（不同的键映射到相同索引时）。
2. 哈希表（HashTable）
   • 包含两个字段：size（哈希表大小）和table（指向指针数组的指针）。
   • table数组的每个元素是一个链表头指针。

// 初始化哈希表
HashTable* createHashTable(int size) {HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));hashTable->size = size;hashTable->table = (HashNode**)malloc(size * sizeof(HashNode*));for (int i = 0; i < size; i++) {hashTable->table[i] = NULL;}return hashTable;
}// 创建新的哈希表节点
HashNode* createHashNode(int key, int value) {HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));newNode->key = key;newNode->value = value;newNode->next = NULL;return newNode;
}

1. 分配哈希表结构内存
   • 使用 malloc 动态分配 HashTable 结构体的内存空间。
2. 设置哈希表大小
   • 将传入的 size 参数赋值给哈希表的 size 字段，决定哈希表的桶bucket数量。
3. 分配哈希表数组内存
   • 分配一个指针数组，每个元素是一个指向 HashNode 的指针（即链表头指针）。
4. 初始化所有桶为空

// 哈希函数
int hashFunction(int key, int size) {return key % size;
}// 插入节点到哈希表
void insert(HashTable* hashTable, int key, int value) {int index = hashFunction(key, hashTable->size);HashNode* newNode = createHashNode(key, value);if (hashTable->table[index] == NULL) {hashTable->table[index] = newNode;} else {HashNode* current = hashTable->table[index];while (current->next != NULL) {current = current->next;}current->next = newNode;}
}// 在哈希表中查找节点
int search(HashTable* hashTable, int key) {int index = hashFunction(key, hashTable->size);HashNode* current = hashTable->table[index];while (current != NULL) {if (current->key == key) {return current->value;}current = current->next;}return -1;
}// 从哈希表中删除节点
void deleteNode(HashTable* hashTable, int key) {int index = hashFunction(key, hashTable->size);HashNode* current = hashTable->table[index];HashNode* prev = NULL;while (current != NULL && current->key != key) {prev = current;current = current->next;}if (current == NULL) {return;}if (prev == NULL) {hashTable->table[index] = current->next;} else {prev->next = current->next;}free(current);
}

1. 哈希函数
   使用取模运算将键映射到数组索引。
   • 作用：决定键值对应该存储在哈希表的哪个 “桶” 中。
2. 插入操作
   • 通过哈希函数计算索引。
   • 如果对应索引为空，直接插入。如果不为空，遍历链表将新节点添加到尾部（尾插法）。
3. 查找操作
   • 通过哈希函数定位索引。
   • 遍历对应链表，比较键值。找到则返回值，未找到返回 - 1。
4. 删除操作
   • 通过哈希函数定位索引
   • 遍历链表查找目标节点，调整前驱节点指针跳过目标节点，释放目标节点内存。

// 释放哈希表内存
void freeHashTable(HashTable* hashTable) {for (int i = 0; i < hashTable->size; i++) {HashNode* current = hashTable->table[i];while (current != NULL) {HashNode* temp = current;current = current->next;free(temp);}}free(hashTable->table);free(hashTable);
}

1. 遍历哈希表数组
   • 获取当前桶的链表头指针，若链表不为空，则释放链表中的所有节点。
2. 释放链表节点
   • 保存当前节点指针到临时变量，移动到下一个节点，释放临时保存的节点内存，重复直到链表末尾。
3. 释放哈希表结构
   • 释放哈希表的数组（存储链表头指针的数组）。
   • 释放哈希表本身的结构体。

5. 哈希表的复杂度分析

• 插入操作：平均情况下，插入操作的时间复杂度为 (O(1))，因为哈希函数可以快速定位到插入位置。但在最坏情况下（所有键都映射到同一个位置），时间复杂度会退化为 (O(n))。
• 查找操作：平均情况下，查找操作的时间复杂度为 (O(1))。最坏情况下，时间复杂度为 (O(n))。
• 删除操作：平均情况下，删除操作的时间复杂度为 (O(1))。最坏情况下，时间复杂度为 (O(n))。

例题示例

一、四数相加2

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

1. 定义哈希表节点和哈希表结构体：

typedef struct HashNode {int key;int count;struct HashNode* next;
} HashNode;typedef struct HashTable {int size;HashNode** table;
} HashTable;

​ HashNode 结构体表示哈希表中的一个节点，包含一个键 key、一个计数 count（用于记录该键出现的次数）以及指向下一个节点的指针 next。HashTable 结构体表示整个哈希表，包含哈希表的大小 size 和一个指向 HashNode 指针数组的指针 table，用于存储哈希表的各个桶。

1. 创建哈希表函数 createHashTable：

HashTable* createHashTable(int size) {HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));hashTable->size = size;hashTable->table = (HashNode**)malloc(size * sizeof(HashNode*));for (int i = 0; i < size; i++) {hashTable->table[i] = NULL;}return hashTable;
}

​ 该函数动态分配一个 HashTable 结构体的内存，并设置其大小 size。然后，为哈希表的桶数组 table 分配内存，并将每个桶的指针初始化为 NULL，最后返回创建好的哈希表指针。

1. 哈希函数 hashFunction：

int hashFunction(int key, int size) { return (key % size + size) % size; }

​ 该函数接受一个键 key 和哈希表的大小 size，通过取模运算将键映射到哈希表的索引位置。(key % size + size) % size 确保了即使 key % size 为负数，也能得到一个有效的非负索引。

1. 插入节点到哈希表函数 insert：

void insert(HashTable* hashTable, int key) {int index = hashFunction(key, hashTable->size);HashNode* current = hashTable->table[index];while (current != NULL) {if (current->key == key) {current->count++;return;}current = current->next;}HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));newNode->key = key;newNode->count = 1;newNode->next = hashTable->table[index];hashTable->table[index] = newNode;
}

​ 该函数首先计算键 key 的哈希索引 index。然后，遍历哈希表中该索引位置的链表，如果找到相同的键，则将其计数 count 加 1 并返回。如果没有找到相同的键，则创建一个新的 HashNode，将其计数初始化为 1，并将其插入到链表的头部。

1. 获取键的计数函数 getCount：

int getCount(HashTable* hashTable, int key) {int index = hashFunction(key, hashTable->size);HashNode* current = hashTable->table[index];while (current != NULL) {if (current->key == key) {return current->count;}current = current->next;}return 0;
}

​ 该函数计算键 key 的哈希索引 index，然后遍历该索引位置的链表，查找键 key。如果找到，则返回其计数 count；如果没有找到，则返回 0。

1. 释放哈希表内存函数 freeHashTable：

void freeHashTable(HashTable* hashTable) {for (int i = 0; i < hashTable->size; i++) {HashNode* current = hashTable->table[i];while (current != NULL) {HashNode* temp = current;current = current->next;free(temp);}}free(hashTable->table);free(hashTable);
}

​ 该函数遍历哈希表的每个桶，释放链表中的每个节点的内存，然后释放桶数组的内存，最后释放哈希表结构体的内存。

1. 四数之和计数函数 fourSumCount：

int fourSumCount(int* nums1, int nums1Size, int* nums2, int nums2Size,int* nums3, int nums3Size, int* nums4, int nums4Size) {HashTable* hashTable = createHashTable(400);int result = 0;for (int i = 0; i < nums1Size; i++) {for (int j = 0; j < nums2Size; j++) {int sum12 = nums1[i] + nums2[j];insert(hashTable, sum12);}}for (int k = 0; k < nums3Size; k++) {for (int l = 0; l < nums4Size; l++) {int sum34 = nums3[k] + nums4[l];result += getCount(hashTable, -sum34);}}freeHashTable(hashTable);return result;
}

​ 首先，创建一个哈希表 hashTable。然后，遍历数组 nums1 和 nums2，计算它们元素的和 sum12，并将其插入到哈希表中，同时记录出现的次数。接着，遍历数组 nums3 和 nums4，计算它们元素的和 sum34，并在哈希表中查找 -sum34 的计数，将计数累加到 result 中。最后，释放哈希表的内存并返回 result。

二、随机链表的复制

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

1. 定义数据结构：

typedef struct HashNode {struct Node* key;struct Node* value;struct HashNode* next;
} HashNode;typedef struct HashTable {int size;HashNode** table;
} HashTable;

• 首先定义了链表节点 Node 的结构体，包含值 val、指向下一个节点的指针 next 和指向随机节点的指针 random。

• 接着定义了哈希表节点 HashNode 的结构体，包含键 key（指向原链表节点的指针）、值 value（指向复制链表节点的指针）和指向下一个哈希表节点的指针 next。

• 然后定义了哈希表 HashTable 的结构体，包含哈希表的大小 size 和一个指向 HashNode 指针数组的指针 table。

1. 创建链表节点函数 creatNode：

struct Node* creatNode(int val) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->val = val;newNode->next = NULL;newNode->random = NULL;return newNode;
}

该函数动态分配一个 Node 结构体的内存，并初始化其值 val，同时将 next 和 random 指针初始化为 NULL，最后返回创建好的链表节点指针。

1. 创建哈希表节点函数 createHashNode：

HashNode* createHashNode(struct Node* key, struct Node* value) {HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));newNode->key = key;newNode->value = value;newNode->next = NULL;return newNode;
}

该函数动态分配一个 HashNode 结构体的内存，并初始化其键 key 和值 value，同时将 next 指针初始化为 NULL，最后返回创建好的哈希表节点指针。

1. 创建哈希表函数 createHashTable：

HashTable* createHashTable(int size) {HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));hashTable->size = size;hashTable->table = (HashNode**)malloc(size * sizeof(HashNode*));for (int i = 0; i < size; i++) {hashTable->table[i] = NULL;}return hashTable;
}

该函数动态分配一个 HashTable 结构体的内存，并设置其大小 size。然后，为哈希表的桶数组 table 分配内存，并将每个桶的指针初始化为 NULL，最后返回创建好的哈希表指针。

1. 哈希函数 hashFunction：

int hashFunction(struct Node* key, int size) {return ((unsigned long)key) % size;
}

该函数接受一个指向链表节点的指针 key 和哈希表的大小 size，通过将指针转换为无符号长整型并取模运算，将键映射到哈希表的索引位置。

在 C 语言中：

• 指针本质：指针是一个内存地址，通常表示为无符号整数。
• 类型安全：直接对指针进行算术运算（如取模）会导致类型错误，因此需要将指针转换为整数类型。
• 平台兼容性：unsigned long 类型通常足够大，可以容纳指针的完整值（在 32 位和 64 位系统中均适用）。

通过 (unsigned long)key，将指针值转换为无符号长整型，确保其作为整数参与后续的取模运算。

1. 插入节点到哈希表函数 insert：

void insert(HashTable* hashTable, struct Node* key, struct Node* value) {int index = hashFunction(key, hashTable->size);HashNode* newNode = createHashNode(key, value);if (hashTable->table[index] == NULL) {hashTable->table[index] = newNode;} else {HashNode* current = hashTable->table[index];while (current->next != NULL) {current = current->next;}current->next = newNode;}
}

该函数首先计算键 key 的哈希索引 index。然后，创建一个新的 HashNode，并将其插入到哈希表中该索引位置的链表中。如果该索引位置的链表为空，则直接插入；否则，遍历链表并将新节点插入到链表的末尾。

1. 在哈希表中查找节点函数 search：

struct Node* search(HashTable* hashTable, struct Node* key) {int index = hashFunction(key, hashTable->size);HashNode* current = hashTable->table[index];while (current != NULL) {if (current->key == key) {return current->value;}current = current->next;}return NULL;
}

该函数计算键 key 的哈希索引 index，然后遍历该索引位置的链表，查找键 key。如果找到，则返回其对应的值 value；如果没有找到，则返回 NULL。

1. 释放哈希表内存函数 freeHashTable：

void freeHashTable(HashTable* hashTable) {for (int i = 0; i < hashTable->size; i++) {HashNode* current = hashTable->table[i];while (current != NULL) {HashNode* temp = current;current = current->next;free(temp);}}free(hashTable->table);free(hashTable);
}

该函数遍历哈希表的每个桶，释放链表中的每个节点的内存，然后释放桶数组的内存，最后释放哈希表结构体的内存。

1. 复制随机链表函数 copyRandomList：

struct Node* copyRandomList(struct Node* head) {if (head == NULL)return NULL;HashTable* hashTable = createHashTable(300);struct Node* cur = head;while (cur != NULL) {struct Node* newNode = creatNode(cur->val);insert(hashTable, cur, newNode);cur = cur->next;}cur = head;while (cur != NULL) {struct Node* newNode = search(hashTable, cur);if (cur->next != NULL) {newNode->next = search(hashTable, cur->next);}if (cur->random != NULL) {newNode->random = search(hashTable, cur->random);}cur = cur->next;}struct Node* new = search(hashTable, head);freeHashTable(hashTable);return new;
}

​ 首先，创建一个哈希表 hashTable。然后，遍历原链表，为每个节点创建一个复制节点，并将原节点和复制节点的对应关系插入到哈希表中。接着，再次遍历原链表，通过哈希表找到复制节点，并设置其 next 和 random 指针。最后，释放哈希表的内存，并返回复制链表的头节点。

三、有效的字母异位词

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

1. 检查字符串长度

if (strlen(s) != strlen(t))return false;

如果两个字符串的长度不相等，那么它们肯定不是字母异位词，直接返回 false。

1. 创建哈希表

int* hashTable = (int*)malloc(sizeof(int) * 26);
for (int i = 0; i < 26; i++) {hashTable[i] = 0;
}

动态分配一个大小为 26 的整型数组 hashTable，用于记录每个字符出现的次数。因为英文字母有 26 个，所以数组大小为 26。然后将数组的每个元素初始化为 0。

1. 统计字符串 s 中字符的出现次数

for (int i = 0; i < strlen(s); i++) {hashTable[(s[i] - 'a')] += 1;
}

遍历字符串 s，对于每个字符 s[i]，计算其在 hashTable 中的索引位置 s[i] - 'a'（假设字符都是小写英文字母），并将对应位置的计数器加 1。

1. 检查字符串 t 中字符的出现次数

for (int i = 0; i < strlen(t); i++) {if (hashTable[(t[i] - 'a')] == 0) {return false;} else {hashTable[(t[i] - 'a')] -= 1;}
}

遍历字符串 t，对于每个字符 t[i]，计算其在 hashTable 中的索引位置 t[i] - 'a'。如果对应位置的计数器为 0，说明字符串 t 中出现了字符串 s 中没有的字符，那么它们不是字母异位词，返回 false。否则，将对应位置的计数器减 1。

1. 检查哈希表中所有计数器是否为 0

for (int i = 0; i < 26; i++) {if (hashTable[i] != 0) {return false;}
}

遍历哈希表 hashTable，如果有任何一个计数器不为 0，说明两个字符串中字符的出现次数不相等，它们不是字母异位词，返回 false。

1. 返回结果

return true;

如果上述所有检查都通过，说明两个字符串包含相同的字符且出现次数相同，即它们是字母异位词，返回 true。