Data Structures Algorithms 简明教程
Hash Table Data structure
散列表是一种以关联方式存储数据的的数据结构。在散列表中，数据以数组格式存储，其中每个数据值都有自己唯一的索引值。如果我们知道所需数据的索引，那么数据的访问速度就会非常快。
因此，它变成了一个插入和搜索操作非常快的数据结构，而与数据大小无关。散列表使用数组作为存储介质，并使用散列技术生成索引，其中元素将被插入或从中找到。
Hashing
哈希是一种将一系列键值转换为一系列数组索引的技术。我们将使用模运算符来获取一系列键值。考虑一个大小为 20 的散列表示例，以及要存储以下项。项采用（键，值）格式。
-
(1,20)
-
(2,70)
-
(42,80)
-
(4,25)
-
(12,44)
-
(14,32)
-
(17,11)
-
(13,78)
-
(37,98)
Search Operation
每次搜索元素时，计算传递的键的哈希代码，并使用该哈希代码作为在数组中的索引来找到元素。如果在计算的哈希代码中找不到元素，则使用线性探测来获取前一个元素。
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;
}Insert Operation
每次插入元素时，计算传递的键的哈希代码，并使用该哈希代码作为在数组中的索引来定位索引。如果在计算的哈希代码中找到了元素，则使用线性探测来查找空位置。
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;
}Delete Operation
每次删除一个元素时，计算传递的键的哈希代码，并使用该哈希代码作为在数组中的索引来定位索引。如果在计算的哈希代码中找不到元素，则使用线性探测来获取前一个元素。找到后，存储一个虚拟项目以保持哈希表的性能。
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;
}