# 哈希表 > 原文： [https://www.programiz.com/dsa/hash-table](https://www.programiz.com/dsa/hash-table) #### 在本教程中，您將學習什么是哈希表。 此外，您還將找到 C，C++ ，Java 和 Python 中哈希表操作的工作示例。 哈希表是一種數據結構，以**鍵值**對的形式表示數據。 每個鍵都映射到哈希表中的一個值。 這些鍵用于索引值/數據。 關聯數組也采用了類似的方法。 * * * 數據通過鍵在鍵值對中表示，如下圖所示。 每個數據都與一個鍵相關聯。 鍵是指向數據的整數。  * * * ## 1.直接地址表 當程序使用的表空間量不是問題時，將使用直接地址表。 在這里，我們假設 * 鍵是小整數 * 鍵的數量不是太大，并且 * 沒有兩個數據具有相同的鍵 采用整數池稱為總體`U = {0, 1, ……., n-1}`。 直接地址表`T[0...n-1]`的每個插槽都包含一個指向與數據相對應的元素的指針。 數組`T`的索引是鍵本身，`T`的內容是指向集合`[key, element]`的指針。 如果沒有鍵的元素，則保留為`NULL`。  有時，鍵本身就是數據。 **操作的偽代碼** ``` directAddressSearch(T, k) return T[k] directAddressInsert(T, x) T[x.key] = x directAddressDelete(T, x) T[x.key] = NIL ``` **直接地址表的限制** * 鍵的值應該很小。 * 鍵的數量必須足夠小，以使其不超過數組的大小限制。 * * * ## 2.哈希表 在哈希表中，鍵被處理以生成映射到所需元素的新索引。 此過程稱為哈希。 假設`h(x)`為哈希函數，`k`為鍵。 計算 `h(k)`，并將其用作元素的索引。  **哈希表的限制** * 如果散列函數為多個鍵產生相同的索引，則會發生沖突。 這種情況稱為碰撞。 為避免這種情況，選擇了合適的哈希函數。 但是，由于`|U|>m`，不可能產生所有唯一的鍵。 因此，良好的哈希函數可能無法完全防止沖突，但是可以減少沖突次數。 但是，我們還有其他解決沖突的技術。 * * * **哈希表優于直接地址表的優點**： 直接地址表的主要問題是數組的大小和鍵的可能很大的值。 哈希函數減小了索引的范圍，因此數組的大小也減小了。 例如，如果`k = 9845648451321`，則為`h(k) = 11`（通過使用某些哈希函數）。 這有助于節省浪費的內存，同時為數組提供`9845648451321`的索引 * * * ### 鏈接解決沖突 在此技術中，如果哈希函數為多個元素生成相同的索引，則使用雙向鏈表將這些元素存儲在相同的索引中。 如果`j`是多個元素的插槽，則它包含一個指向元素列表開頭的指針。 如果不存在任何元素，則`j`包含`NIL`。  **操作的偽代碼** ``` chainedHashSearch(T, k) return T[h(k)] chainedHashInsert(T, x) T[h(x.key)] = x //insert at the head chainedHashDelete(T, x) T[h(x.key)] = NIL ``` * * * ## Python，Java，C 和 C++ 實現 ```py # Python program to demonstrate working of HashTable hashTable = [[],] * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable[index] = [key, data] def removeData(key): index = hashFunction(key) hashTable[index] = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) ``` ```java // Java program to demonstrate working of HashTable import java.util.*; class HashTable { public static void main(String args[]) { Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); } } ``` ```c // Implementing hash table in C #include <stdio.h> #include <stdlib.h> struct set { int key; int data; }; struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) { return (key % capacity); } int checkPrime(int n) { int i; if (n == 1 || n == 0) { return 0; } for (i = 2; i < n / 2; i++) { if (n % i == 0) { return 0; } } return 1; } int getPrime(int n) { if (n % 2 == 0) { n++; } while (!checkPrime(n)) { n += 2; } return n; } void init_array() { capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) { array[i].key = 0; array[i].data = 0; } } void insert(int key, int data) { int index = hashFunction(key); if (array[index].data == 0) { array[index].key = key; array[index].data = data; size++; printf("\n Key (%d) has been inserted \n", key); } else if (array[index].key == key) { array[index].data = data; } else { printf("\n Collision occured \n"); } } void remove_element(int key) { int index = hashFunction(key); if (array[index].data == 0) { printf("\n This key does not exist \n"); } else { array[index].key = 0; array[index].data = 0; size--; printf("\n Key (%d) has been removed \n", key); } } void display() { int i; for (i = 0; i < capacity; i++) { if (array[i].data == 0) { printf("\n array[%d]: / ", i); } else { printf("\n key: %d array[%d]: %d \t", array[i].key, i, array[i].data); } } } int size_of_hashtable() { return size; } int main() { int choice, key, data, n; int c = 0; init_array(); do { printf("1.Insert item in the Hash Table" "\n2.Remove item from the Hash Table" "\n3.Check the size of Hash Table" "\n4.Display a Hash Table" "\n\n Please enter your choice: "); scanf("%d", &choice); switch (choice) { case 1: printf("Enter key -:\t"); scanf("%d", &key); printf("Enter data -:\t"); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d\n", n); break; case 4: display(); break; default: printf("Invalid Input\n"); } printf("\nDo you want to continue (press 1 for yes): "); scanf("%d", &c); } while (c == 1); } ``` ```cpp // Implementing hash table in C++ #include <iostream> #include <list> using namespace std; class HashTable { int capacity; list<int> *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) { int i; if (n == 1 || n == 0) { return 0; } for (i = 2; i < n / 2; i++) { if (n % i == 0) { return 0; } } return 1; } int getPrime(int n) { if (n % 2 == 0) { n++; } while (!checkPrime(n)) { n += 2; } return n; } int hashFunction(int key) { return (key % capacity); } void displayHash(); }; HashTable::HashTable(int c) { int size = getPrime(c); this->capacity = size; table = new list<int>[capacity]; } void HashTable::insertItem(int key, int data) { int index = hashFunction(key); table[index].push_back(data); } void HashTable::deleteItem(int key) { int index = hashFunction(key); list<int>::iterator i; for (i = table[index].begin(); i != table[index].end(); i++) { if (*i == key) break; } if (i != table[index].end()) table[index].erase(i); } void HashTable::displayHash() { for (int i = 0; i < capacity; i++) { cout << "table[" << i << "]"; for (auto x : table[i]) cout << " --> " << x; cout << endl; } } int main() { int key[] = {231, 321, 212, 321, 433, 262}; int data[] = {123, 432, 523, 43, 423, 111}; int size = sizeof(key) / sizeof(key[0]); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key[i], data[i]); h.deleteItem(12); h.displayHash(); } ``` * * * ## 良好的哈希函數 良好的哈希函數具有以下特征。 1. 它不應生成太大且存儲桶空間小的鍵。 空間被浪費了。 2. 生成的鍵的范圍不能太近，也不能太遠。 3. 必須盡可能減少碰撞。 用于散列的一些方法是： ### 除法 如果`k`是鍵，并且`m`是哈希表的大小，則哈希函數`h()`的計算公式為： `h(k) = k mod m` 例如，如果哈希表的大小為`10`和`k = 112`，則`h(k) = 112 % 10 = 2`。`m`的值不得為`2`的冪。 這是因為`2`的二進制格式的功率為`10, 100, 1000, …`。 當我們找到`k mod m`時，我們將始終獲得較低階的`p`位。 ``` if m = 22, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 01 if m = 23, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 001 if m = 24, k = 17, then h(k) = 17 mod 22 = 10001 mod 100 = 0001 if m = 2p, then h(k) = p lower bits of m ``` ### 乘法 `h(k) = ?m(kA mod 1)?` 其中， * `kA mod 1`給出小數部分`kA`， * `? ?`給出底值 * `A`是任何常數。`A`的值在 0 到 1 之間。但是，最佳選擇是 Knuth 建議的`≈ (√5-1)/2`。 ### 通用哈希 在通用哈希中，哈希函數是獨立于鍵隨機選擇的。 * * * ## 開放式尋址 多個值可以存儲在普通哈希表的單個插槽中。 通過使用開放式尋址，每個插槽要么用單個鍵填充，要么向左`NIL`填充。 所有元素都存儲在哈希表本身中。 與鏈接不同，不能將多個元素放入同一插槽。 開放式尋址基本上是一種沖突解決技術。 開放式尋址使用的一些方法是： ### 線性探測 在線性探測中，通過檢查下一個插槽來解決沖突。 `h(k, i) = (h′(k) + i) mod m` 其中， * `i = {0, 1, ….}` * `h'(k)`是新的哈希函數 如果在`h(k, 0)`發生碰撞，則檢查`h(k, 1)`。 這樣，`i`的值線性增加。 線性探測的問題是相鄰槽的簇被填充。 插入新元素時，必須遍歷整個集群。 這增加了對哈希表執行操作所需的時間。 ### 二次探測 在二次探測中，通過使用以下關系，可以增大槽之間的間距（大于 1）。 `h(k, i) = (h′(k) + c1 i + c2 i^2) mod m` 其中， * `c1`和`c2`是正輔助常數， * `i = {0, 1, ….}` ### 雙重哈希 如果在應用哈希函數`h(k)`之后發生沖突，則將計算另一個哈希函數以查找下一個時隙。 `h(k, i) = (h1(k) + i h2(k)) mod m` * * * ## 哈希表應用 哈希表在以下位置實現 * 需要常數時間的查找和插入 * 密碼學應用 * 需要索引數據