数据结构和算法 - 哈希表

哈希表是一种以关联方式存储数据的数据结构.在哈希表中，数据以数组格式存储，其中每个数据值都有自己唯一的索引值.如果我们知道所需数据的索引，数据的访问就会变得非常快.

因此，它成为一种数据结构，无论数据大小如何，插入和搜索操作都非常快.哈希表使用数组作为存储介质，并使用哈希技术生成索引，其中要插入元素或将要从中定位元素.

哈希

散列是一种将一系列键值转换为数组索引范围的技术.我们将使用模运算符来获取一系列键值.考虑大小为20的哈希表的示例，并且要存储以下项目.项目采用(键，值)格式.

• (1,20)

• (2,70)

• (42,80)

• (4,25)

• (12,44)

• (14,32)

• (17,11)

• (13,78)

• (37,98)

线性探测

正如我们所看到的，可能会使用散列技术来创建已经使用过的数组索引.在这种情况下，我们可以通过查看下一个单元格来搜索阵列中的下一个空位置，直到找到一个空单元格.这种技术称为线性探测.

基本操作

以下是哈希表的基本主要操作.

• 搜索 : 搜索哈希表中的元素.

• 插入 : 在哈希表中插入一个元素.

• 删除 : 从哈希表中删除元素.

DataItem

定义包含一些数据的数据项和密钥，在此基础上搜索将在哈希表中进行.

struct DataItem {   int data;   int 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;        }

插入操作

每当要插入一个元素时，计算该元素的哈希码key传递并使用该哈希代码作为数组中的索引定位索引.如果在计算的哈希码中找到元素，则对空位置使用线性探测.

示例

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;        }

删除操作

每当要删除一个元素时，计算该元素的哈希码key传递并使用该哈希代码作为数组中的索引定位索引.如果在计算的哈希码中找不到元素，则使用线性探测来获取元素.找到后，在那里存储一个虚拟项目以保持哈希表的性能不变.

示例

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编程语言中的哈希实现.