一、哈希表概念

1. 哈希表的基本概念

? 哈希表（Hash Table），也稱為散列表，是一種根據鍵（Key）直接訪問存儲位置的數據結構。哈希表的核心構成部分有兩個：哈希函數和數組。

? 它通過哈希函數（Hash Function）將鍵映射到一個固定大小數組的索引上，這個數組被稱為哈希表，存儲在該索引位置的數據被稱為值（Value）。我們能把鍵（Key）轉換為數組的索引，進而快速地進行數據的插入、查找和刪除操作。

2. 哈希表的核心組件

2.1 哈希函數

? 哈希函數是哈希表的核心，它的作用是將鍵轉換為哈希表中的一個索引。一個好的哈希函數應該滿足以下幾個條件：

• 確定性：對于相同的鍵，哈希函數必須始終返回相同的索引。
• 均勻性：哈希函數應該盡可能均勻地將鍵分布到哈希表的各個位置，以減少沖突的發生。
• 高效性：哈希函數的計算應該盡可能快，以保證哈希表的操作效率。

常見的哈希函數有取模法，直接定址法，除留余數法，平方取中法。

• 取模法：

index = key % table_size，其中 key 是鍵，table_size 是哈希表的大小。

• 直接定址法：一種將鍵值直接作為哈希地址的方法。具體來說，它通過一個線性變換來確定哈希地址。

H(key) = a·key + b。

假設要統計不同年齡的人數，年齡范圍是 0-100，那么可以直接用年齡作為索引，即：

int count[101] = {0};  // 索引0-100對應年齡0-100

• 除留余數法：一種較為常用的哈希函數構造方法，它通過取鍵值除以哈希表大小的余數來得到哈希地址。

H(key) = key % m 。

若哈希表的大小 m 為 10，對于鍵值 23，其哈希地址為：

H(23) = 23 % 10 = 3

若 m 是 2 的冪次方，那么哈希地址就相當于鍵值的低位部分，這可能會導致更多的沖突。

• 平方取中法：先計算鍵值的平方，然后取中間的幾位作為哈希地址。

步驟：

1. 計算鍵值的平方，即key2。
2. 取平方結果中間的幾位數字作為哈希地址。

示例：假設哈希表的大小為 1000（即需要 3 位哈希地址）：

• 若鍵值為 25，252 = 625，那么哈希地址就是 625。
• 若鍵值為 400，4002 = 160000，取中間三位為 000，所以哈希地址是 0。

方法	優點	缺點	適用場景
直接定址法	無沖突，簡單直接	可能浪費大量空間	鍵分布連續且密集
除留余數法	實現簡單，應用廣泛	m 選擇不當易產生沖突	大多數場景
平方取中法	分布均勻，對鍵的每一位都敏感	計算相對復雜	鍵的每一位都有影響的場景
取模法	空間利用率為 100%，鍵值任意	擴容時，m 值改變，所有鍵需要重新計算哈希地址	鍵的分布較為隨機且均勻，哈希表大小固定且不需要動態擴容

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);const aCode: number = 'a'.charCodeAt(0);

2. Set（集合）

特點：

• 存儲唯一值
• 快速判斷元素是否存在
• 添加、刪除、查找時間復雜度：O(1)

適用場景：

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

示例：查找數組中的重復元素

const numSet: Set<number> = new Set<number>();

在 TypeScript 中，const numSet = new Set<number>(); 創建了一個強類型的集合（Set），它只能存儲 數值類型（number） 的元素。下面詳細解釋其功能、用法和注意事項：

1. Set 基礎概念

Set 是 ES6 引入的一種數據結構，類似于數組，但具有以下特點：

• 元素唯一：不允許重復值。
• 無序性：元素沒有固定順序。
• 高效查找：基于哈希表實現，插入、刪除、查找的時間復雜度接近 O (1)。

2. TypeScript 泛型約束

<number> 是泛型語法，用于約束 Set 中元素的類型。

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)。

4.哈希表性能分析

1. 時間復雜度

哈希表的核心操作（插入、查找、刪除）的時間復雜度在平均情況下為 O(1)，但在最壞情況下可能退化為 O(n)。具體分析如下：

操作	平均時間復雜度	最壞時間復雜度	說明
插入（Insert）	O(1)	O(n)	需計算哈希值并處理沖突（如鏈表遍歷）。
查找（Search）	O(1)	O(n)	需計算哈希值并遍歷可能存在的沖突鏈表。
刪除（Delete）	O(1)	O(n)	需先查找元素，再從鏈表或數組中刪除。

最壞情況發生在所有鍵都映射到同一哈希地址時。

2. 影響性能的關鍵因素

（1）哈希函數的質量

• 均勻性：好的哈希函數應使鍵均勻分布在哈希表中，減少沖突。
• 計算效率：哈希函數本身的計算復雜度應盡量低（如取模法）。

（2）沖突處理方式

• 鏈地址法：每個槽位維護一個鏈表，沖突元素依次插入鏈表。
  • 優點：實現簡單，適用于沖突頻繁的場景。
  • 缺點：鏈表過長時查詢效率下降，需額外指針空間。
• 開放尋址法：沖突時通過探測序列（如線性探測、二次探測）尋找下一個空位。
  • 優點：無需額外指針，空間利用率高。
  • 缺點：易產生聚集現象，導致后續沖突概率增加。

（3）負載因子（Load Factor）

負載因子定義為：

α = 鍵的數量 / 哈希表大小

• α 越小：沖突概率越低，性能越好，但空間利用率低。
• α 越大：沖突概率越高，性能下降，需擴容以維持效率。

經驗法則：

• 鏈地址法：通常將 α 控制在 0.75~1.0 之間。
• 開放尋址法：α 應控制在 0.5 以下，避免聚集。

3. 性能優化策略

（1）選擇高效的哈希函數

• 除留余數法：H(key) = key % m，其中 m 取質數以減少沖突。
• 字符串哈希：使用多項式哈希（如 DJB2 算法）：

DJB2 算法是一種由 Daniel J. Bernstein 設計的字符串哈希函數，其核心思想是通過移位和加法操作將字符串轉換為一個無符號整數哈希值。

hash(i) = hash(i-1) * 33 + str[i]

其中：

• hash(i) 是前 i 個字符的哈希值。
• str[i] 是字符串的第 i 個字符（ASCII 值）。
• 初始值：hash(0) = 5381。

unsigned int hash(char* str) {unsigned int hash = 5381;//研究表明，這個值能減少哈希沖突的概率。//33 是一個奇質數，實驗證明它在哈希函數中表現良好，能有效減少沖突。while (*str) hash = ((hash << 5) + hash) + (*str++); return hash;
}

（2）優化沖突處理

• 鏈地址法改進：
  • 使用紅黑樹代替鏈表，將最壞時間復雜度從 O (n) 降至 O (log n)（如 Java 的 HashMap 在鏈表長度超過 8 時轉換為紅黑樹）。

（3）動態擴容

當負載因子超過閾值時，擴容并重新哈希：

• 步驟：
  1. 創建更大的新哈希表（通常擴容為原大小的 2 倍）。
  2. 遍歷原哈希表，將所有鍵重新計算哈希值并插入新表。

4. 實際應用中的性能對比

場景	鏈地址法哈希表	紅黑樹
平均查找時間	O(1)	O(log n)
最壞查找時間	O(n)	O(log n)
空間利用率	中等（需額外指針）	低（需左右子樹指針）
適用負載因子	α ≤ 1.0	無限制
動態擴容開銷	較高（需重新哈希）	低（支持動態調整）

結論：

• 哈希表在平均情況下性能遠優于樹結構（如紅黑樹）。
• 當鍵數量不確定或沖突頻繁時，鏈地址法更靈活。

5.與其他數據結構對比

1. 時間復雜度對比

數據結構	插入（平均）	插入（最壞）	查找（平均）	查找（最壞）	刪除（平均）	刪除（最壞）
哈希表	O(1)	O(n)	O(1)	O(n)	O(1)	O(n)
數組	O(1)	O(n)	O(1)	O(1)	O(n)	O(n)
鏈表	O(1)	O(1)	O(n)	O(n)	O(n)	O(n)
二叉搜索樹	O(log n)	O(n)	O(log n)	O(n)	O(log n)	O(n)
紅黑樹	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)

說明：

• 哈希表的最壞情況發生在所有鍵沖突時（如哈希函數設計不當）。
• 數組的插入 / 刪除最壞情況發生在需要擴容或移動元素時。
• 二叉搜索樹的最壞情況發生在樹退化為鏈表時（如插入有序數據）。

2. 空間復雜度對比

數據結構	空間復雜度	額外開銷
哈希表	O(n)	哈希表數組、鏈表指針
數組	O(n)	連續內存塊，可能浪費空間
鏈表	O(n)	每個節點的指針
二叉搜索樹	O(n)	每個節點的左右子樹指針
紅黑樹	O(n)	每個節點的顏色位、指針

說明：

• 哈希表的空間利用率取決于負載因子（通常為 0.75~1.0）。
• 紅黑樹的每個節點額外存儲一個顏色位（1 bit），用于維持平衡。

3. 特性與適用場景對比

數據結構	有序性	動態擴容	優勢場景	劣勢場景
哈希表	無序	支持	快速查找、插入、刪除（平均 O (1)），適合鍵值對存儲（如緩存、數據庫索引）	不支持有序遍歷，哈希函數設計不當會導致性能下降
數組	有序	需重建	隨機訪問（O (1)），元素類型一致且數量固定	插入 / 刪除效率低，擴容成本高
鏈表	有序	動態	頻繁插入 / 刪除（O (1)），元素數量不確定	隨機訪問效率低（O (n)）
二叉搜索樹	有序	動態	有序遍歷（O (n)），支持范圍查詢	最壞情況退化為鏈表（O (n)），需維護平衡性
紅黑樹	有序	動態	高效的插入、刪除、查找（O (log n)），適合需頻繁修改的有序集合	實現復雜，空間開銷略高

4. 典型應用場景

數據結構	應用場景
哈希表	緩存（如 Redis）、編程語言內置字典（如 Python 的 dict）、數據庫索引
數組	科學計算（如 NumPy）、矩陣運算、需要隨機訪問的固定大小數據
鏈表	內存管理（如操作系統的空閑內存塊管理）、LRU 緩存淘汰策略
二叉搜索樹	文件系統目錄結構、簡單的排序與查找
紅黑樹	C++ STL 中的 map/set、Java 的 TreeMap/TreeSet、Linux 內核進程調度

5. 選擇建議

• 優先選哈希表：若需快速查找且無需有序遍歷（如緩存、去重）。
• 優先選數組：若需隨機訪問且元素數量固定（如矩陣、向量）。
• 優先選鏈表：若需頻繁插入 / 刪除且無需隨機訪問（如實現棧、隊列）。
• 優先選紅黑樹：若需有序遍歷或范圍查詢（如數據庫索引、有序集合）。

6.哈希表的內存管理

1. 基本內存結構

哈希表通常由兩部分組成：

• 哈希數組：存儲桶（Bucket）的固定大小數組，每個桶可指向一個鏈表或其他數據結構。
• 鏈表 / 紅黑樹：處理哈希沖突時，每個桶可能鏈接多個元素。

示例：
鏈地址法哈希表的內存布局：

2. 內存分配策略

（1）靜態分配

• 特點：哈希數組大小固定，初始化時分配內存。
• 優點：實現簡單，無需動態擴容。
• 缺點：可能浪費空間或導致沖突頻繁。

示例：

#define SIZE 100
Node* table[SIZE];  // 靜態數組，大小為100

（2）動態分配

• 特點：運行時根據需要調整哈希數組大小。
• 優點：空間利用率高，減少沖突。
• 缺點：擴容操作耗時（O (n)）。

示例：

int size = 100;
Node** table = (Node**)calloc(size, sizeof(Node*));  // 動態分配

3. 沖突處理與內存開銷

（1）鏈地址法

• 每個桶維護鏈表：每個節點包含鍵值對和指向下一個節點的指針。
• 內存開銷：
  • 哈希數組：O(m)（m 為桶數量）。
  • 鏈表節點：O(n)（n 為鍵值對數量），每個節點需額外指針。

優化：
當鏈表過長時，可將鏈表轉換為紅黑樹（如 Java 的 HashMap），將最壞時間復雜度從 O (n) 降至 O (log n)，但會增加每個節點的內存開銷（額外存儲顏色位和父節點指針）。

4. 動態擴容與內存重分配

（1）觸發條件

當負載因子（α = n/m）超過閾值（通常為 0.75）時，需擴容。

（2）擴容步驟

1. 創建更大的新哈希數組（通常擴容為原大小的 2 倍）。
2. 遍歷原哈希表，重新計算每個元素的哈希值并插入新數組。
3. 釋放原哈希數組內存。

示例：

void resize(HashTable* ht) {int new_size = next_prime(ht->size * 2);  // 擴容為原大小的2倍Node** new_table = (Node**)calloc(new_size, sizeof(Node*));// 重新哈希所有元素for (int i = 0; i < ht->size; i++) {Node* curr = ht->table[i];while (curr) {Node* next = curr->next;unsigned int idx = hash(curr->key, new_size);curr->next = new_table[idx];new_table[idx] = curr;curr = next;}}free(ht->table);  // 釋放原數組內存ht->table = new_table;ht->size = new_size;
}

（3）內存開銷

• 擴容期間需額外 O(m) 空間存儲新數組。
• 若元素數量波動較大，頻繁擴容會導致內存碎片。

5. 內存優化策略

（1）預分配與分批擴容

• 預分配：預估元素數量，初始化時分配足夠空間。
• 分批擴容：在高并發場景下，將擴容操作分攤到多次插入中，減少單次擴容的內存壓力。

（2）內存池技術

• 預先分配大塊內存，按需分配給節點，減少頻繁 malloc/free 的開銷。
• 降低內存碎片，提高內存利用率。

示例：

// 內存池結構
typedef struct MemoryPool {Node* free_list;size_t block_size;
} MemoryPool;// 從內存池分配節點
Node* pool_alloc(MemoryPool* pool) {if (!pool->free_list) {// 分配新塊Node* block = (Node*)malloc(pool->block_size * sizeof(Node));// 將新塊中的節點連接到空閑列表for (int i = 0; i < pool->block_size - 1; i++) {block[i].next = &block[i + 1];}block[pool->block_size - 1].next = NULL;pool->free_list = block;}Node* node = pool->free_list;pool->free_list = node->next;return node;
}

（3）壓縮哈希表

• 對于稀疏哈希表（負載因子極低），可使用壓縮技術減少空間浪費。
• 例如，使用 BitArray 標記已使用的桶，僅存儲有效元素。

6. 內存泄漏風險

• 未釋放鏈表節點：刪除元素時，若未正確釋放鏈表節點內存，會導致泄漏。
• 循環引用：在雙向鏈表或樹結構中，若存在循環引用，垃圾回收機制無法回收內存。

正確釋放示例：

void free_hash_table(HashTable* ht) {for (int i = 0; i < ht->size; i++) {Node* curr = ht->table[i];while (curr) {Node* temp = curr;curr = curr->next;free(temp->key);  // 釋放鍵內存free(temp);       // 釋放節點內存}}free(ht->table);  // 釋放哈希數組free(ht);         // 釋放哈希表結構
}

7. 不同語言的實現差異

語言	內存管理方式	特點
C	手動管理（malloc/free）	需自行處理內存分配、釋放和擴容，靈活性高但易出錯
Java	自動垃圾回收（GC）	無需手動釋放內存，但擴容時可能觸發 GC，影響性能
Python	引用計數 + GC	字典底層使用哈希表，內存由解釋器自動管理
Go	自動垃圾回收 + 內存池	標準庫 map 使用哈希表，并發場景下通過內存池優化

總結

哈希表的內存管理需平衡空間利用率和性能：

• 鏈地址法：空間開銷較大，但實現簡單，適合沖突頻繁的場景。
• 開放尋址法：空間利用率高，但需嚴格控制負載因子，避免聚集。
• 動態擴容：需權衡擴容時機，避免頻繁擴容導致的性能下降和內存碎片。
• 內存池和壓縮技術：可進一步優化內存使用，但會增加實現復雜度。

二、C 語言實現哈希表

// 定義哈希表節點結構
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. 釋放哈希表結構
   • 釋放哈希表的數組（存儲鏈表頭指針的數組）。
   • 釋放哈希表本身的結構體。

三、例題示例

（1）四數相加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。

（2）隨機鏈表的復制

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 指針。最后，釋放哈希表的內存，并返回復制鏈表的頭節點。

（3）有效的字母異位詞

有效的字母異位詞

給定兩個字符串 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。