哈希表
哈希表是一個數據結構，其中插入和搜索操作都非常快而不管哈希表的大小。 這幾乎是一個常數或 O(1)。哈希表使用數組作爲存儲介質，並使用散列技術來生成索引，其中的元素是被插入或查找。
哈希
散列是一種技術將範圍鍵值轉換爲一定範圍一個數組的索引。我們將使用模運算符來獲得一系列鍵值。考慮大小是 20 的哈希表的一個例子，下列的項目是要被存儲的。項目是（鍵，值）格式。
- (1,20)
- (2,70)
- (42,80)
- (4,25)
- (12,44)
- (14,32)
- (17,11)
- (13,78)
- (37,98)
Sr.No.
Key
Hash
數組索引
1
1
1 % 20 = 1
1
2
2
2 % 20 = 2
2
3
42
42 % 20 = 2
2
4
4
4 % 20 = 4
4
5
12
12 % 20 = 12
12
6
14
14 % 20 = 14
14
7
17
17 % 20 = 17
17
8
13
13 % 20 = 13
13
9
37
37 % 20 = 17
17
線性探測
正如我們所看到的，可能要發生的是所使用的散列技術來創建已使用數組的索引。在這種情況下，我們可以直到找到一個空的單元，通過查看下一個單元搜索數組中下一個空的位置。這種技術被稱爲線性探測。
Sr.No.
Key
Hash
數組索引
線性探測後，數組索引
1
1
1 % 20 = 1
1
1
2
2
2 % 20 = 2
2
2
3
42
42 % 20 = 2
2
3
4
4
4 % 20 = 4
4
4
5
12
12 % 20 = 12
12
12
6
14
14 % 20 = 14
14
14
7
17
17 % 20 = 17
17
17
8
13
13 % 20 = 13
13
13
9
37
37 % 20 = 17
17
18
基本操作
以下是這是繼哈希表的主要的基本操作。
搜索 − 在哈希表中搜索一個元素。
插入 − 在哈希表中插入元素。
刪除 − 刪除哈希表的元素。
數據項
定義有一些基於鍵的數據數據項，在哈希表中進行搜索。
struct DataItem {
int data;
int key;
};
散列方法
定義一個散列方法來計算數據項的 key 的散列碼。
int hashCode(int key){
return key % SIZE;
}
搜索操作
當一個元素要被搜索。通過計算 key 的散列碼並定位使用該哈希碼作爲索引數組的元素。使用線性探測得到元素，如果沒有找到，再計算散列代碼元素繼續向前。
struct DataItem *search(int key){
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL){
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;}
return NULL;
}
插入操作
當一個元素將要插入。通過計算鍵的哈希代碼，找到使用哈希碼作爲索引在數組中的索引。使用線性探測空的位置，如果一個元素在計算哈希碼被找到。
void insert(int key,int data){
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1){
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;}
hashArray[hashIndex] = item;
}
刪除操作
當一個元素要被刪除。計算通過鍵的哈希代碼，找到使用哈希碼作爲索引在數組中的索引。使用線性探測得到的元素，如果沒有找到，再計算哈希碼的元素向前。當找到，存儲虛擬項目也保持哈希表完整的性能。
struct DataItem* delete(struct DataItem* item){
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL){
if(hashArray\[hashIndex\]->key == key){
struct DataItem\* temp = hashArray\[hashIndex\];
//assign a dummy item at deleted position
hashArray\[hashIndex\] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;}
return NULL;
}
要查看 C語言的哈希實現，請點擊這裏