1. Hash Map簡介

????????Hash Map是一種基于鍵值對的數據結構，通過散列函數將鍵映射到存儲位置，實現快速的數據查找和存儲。它可以在常數時間內完成查找、插入和刪除操作，因此在需要頻繁進行這些操作時非常高效。

2. Hash Map的定義

????????散列表（Hash table，也叫哈希表）是一種根據鍵（Key）直接訪問內存存儲位置的數據結構。通過計算一個鍵值的函數，將數據映射到表中的一個位置，以加快查找速度。這個映射函數稱為散列函數，存放記錄的數組稱為散列表。

3. 為什么要使用Hash Map？

????????理想的搜索方法是不經過任何比較，一次直接從表中得到要搜索的元素，即查找的時間復雜度為 O(1)。哈希表通過哈希函數將元素的存儲位置與其關鍵碼之間建立一種映射關系，從而實現快速查找。

4. 鍵值對

????????鍵值對是一種常見的數據結構，用于表示兩個相關聯的數據項：一個是“鍵”（Key），另一個是“值”（Value）。鍵用于標識和查找與之關聯的值。鍵值對在許多編程語言中都有特定的表示方法，例如C++的std::pair和Python的字典（dictionary）。

????????python

dictionary = {"name": "Alice", "age": 30}

????????在C++中：

std::pair<std::string, int> person("Alice", 30);

5. Hash Map的基本實現

????????通過一個簡單的數學公式實現Hash Map：

????????假設有數據集合 {1, 7, 6, 4, 5, 9}，哈希函數為：hash(key) = key % capacity，其中capacity為10。存儲位置如下：

- 1 -> 1
- 7 -> 7
- 6 -> 6
- 4 -> 4
- 5 -> 5
- 9 -> 9

6. 哈希沖突

????????如果插入元素66，會與元素6沖突，因為它們的哈希地址相同（都是6）。哈希沖突是指不同關鍵字通過相同哈希函數計算出相同哈希地址的現象。為了避免沖突，需要設計合理的哈希函數。

7. 改進哈希函數

????????哈希函數設計原則包括：

????????哈希函數的定義域必須包括需要存儲的全部關鍵碼。

????????哈希函數計算出來的地址能均勻分布在整個空間中。

????????哈希函數應該比較簡單。

????????常用哈希函數設計方法：

????????1. 直接定址法：Hash(Key) = A * Key + B

????????2. 除留余數法：Hash(key) = key % p (p <= m)

????????3. 平方取中法：假設關鍵字為1234，對其平方得到1522756，取中間的3位227作為哈希地址。

????????4. 折疊法：將關鍵字分割成幾部分，將這些部分疊加求和，取后幾位作為哈希地址。

????????5. 隨機數法：選擇一個隨機函數，取關鍵字的隨機函數值為其哈希地址。

8. 解決哈希沖突的方法

????????解決哈希沖突的兩種常見方法是閉散列和開散列。

8.1 閉散列（開放定址法）

????????當發生哈希沖突時，將元素存放到沖突位置的下一個空位置中。

????????線性探測：從沖突位置開始，依次向后探測，直到找到下一個空位置。

????????查找公式：hashi = hash(key) % N + i（i = 0, 1, 2, 3, ...）

????????二次探測：為了避免線性探測中的堆積問題，使用平方探測法。找下一個空位置的方法為：hashi = hash(key) % N + i^2（i = 1, 2, 3, 4 ...）

8.2 開散列（鏈地址法）

????????將具有相同地址的元素歸于同一桶，桶中的元素通過單鏈表鏈接起來。哈希桶的極端情況是所有元素都產生沖突，最終都放入一個桶中，此時效率退化為 O(N)。

????????可以將桶中的鏈表結構改為紅黑樹結構，以提高效率。在JDK1.7中，HashMap由數組和鏈表組成；在JDK1.8中，引入了紅黑樹，當鏈表超過8且數組長度超過64時，鏈表會轉換為紅黑樹，以提高性能。

9. 閉散列實現

????????以下是閉散列法的具體實現代碼：

????????在python中

class ClosedHashMap:def __init__(self, capacity):self.capacity = capacityself.table = [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index = self.hash_function(key)while self.table[index] is not None:index = (index + 1) % self.capacityself.table[index] = (key, value)def search(self, key):index = self.hash_function(key)while self.table[index] is not None:if self.table[index][0] == key:return self.table[index][1]index = (index + 1) % self.capacityreturn Nonedef delete(self, key):index = self.hash_function(key)while self.table[index] is not None:if self.table[index][0] == key:self.table[index] = Nonereturn Trueindex = (index + 1) % self.capacityreturn False

10. 開散列實現

????????以下是開散列法的具體實現代碼：

????????在python中

class Node:def __init__(self, key, value):self.key = keyself.value = valueself.next = Noneclass OpenHashMap:def __init__(self, capacity):self.capacity = capacityself.table = [None] * capacitydef hash_function(self, key):return key % self.capacitydef insert(self, key, value):index = self.hash_function(key)if self.table[index] is None:self.table[index] = Node(key, value)else:current = self.table[index]while current.next is not None:current = current.nextcurrent.next = Node(key, value)def search(self, key):index = self.hash_function(key)current = self.table[index]while current is not None:if current.key == key:return current.valuecurrent = current.nextreturn Nonedef delete(self, key):index = self.hash_function(key)current = self.table[index]prev = Nonewhile current is not None:if current.key == key:if prev is None:self.table[index] = current.nextelse:prev.next = current.nextreturn Trueprev = currentcurrent = current.nextreturn False

????????這些實現展示了如何通過不同的方法來解決哈希沖突，確保Hash Map能夠高效地插入和查找元素。