Data Structures Algorithms 简明教程

Hash Table Data structure

散列表是一种以关联方式存储数据的的数据结构。在散列表中,数据以数组格式存储,其中每个数据值都有自己唯一的索引值。如果我们知道所需数据的索引,那么数据的访问速度就会非常快。

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value. Access of data becomes very fast if we know the index of the desired data.

因此,它变成了一个插入和搜索操作非常快的数据结构,而与数据大小无关。散列表使用数组作为存储介质,并使用散列技术生成索引,其中元素将被插入或从中找到。

Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located from.

Hashing

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

Hashing is a technique to convert a range of key values into a range of indexes of an array. We’re going to use modulo operator to get a range of key values. Consider an example of hash table of size 20, and the following items are to be stored. Item are in the (key,value) format.

hash function
  1. (1,20)

  2. (2,70)

  3. (42,80)

  4. (4,25)

  5. (12,44)

  6. (14,32)

  7. (17,11)

  8. (13,78)

  9. (37,98)

Linear Probing

如我们所见,哈希技术可能会用来创建数组的已用索引。在这样的情况下,我们可以通过查看下一个单元,直到找到空单元,来搜索数组中的下一个空位置。此技术称为线性探查。

As we can see, it may happen that the hashing technique is used to create an already used index of the array. In such a case, we can search the next empty location in the array by looking into the next cell until we find an empty cell. This technique is called linear probing.

Basic Operations

以下是散列表的基本主要操作。

Following are the basic primary operations of a hash table.

  1. Search − Searches an element in a hash table.

  2. Insert − Inserts an element in a hash table.

  3. Delete − Deletes an element from a hash table.

DataItem

定义一个具有部分数据和键的数据项,用于在哈希表中执行搜索。

Define a data item having some data and key, based on which the search is to be conducted in a hash table.

struct DataItem {
   int data;
   int key;
};

Hash Method

定义一种哈希方法,用于计算数据项键的哈希代码。

Define a hashing method to compute the hash code of the key of the data item.

int hashCode(int key){
   return key % SIZE;
}

Search Operation

每次搜索元素时,计算传递的键的哈希代码,并使用该哈希代码作为在数组中的索引来找到元素。如果在计算的哈希代码中找不到元素,则使用线性探测来获取前一个元素。

Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.

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

Example

以下是各种编程语言中此操作的实现 -

Following are the implementations of this operation in various programming language −

Insert Operation

每次插入元素时,计算传递的键的哈希代码,并使用该哈希代码作为在数组中的索引来定位索引。如果在计算的哈希代码中找到了元素,则使用线性探测来查找空位置。

Whenever an element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

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

Example

以下是该操作在各种编程语言中的实现 −

Following are the implementations of this operation in various programming languages −

Delete Operation

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

Whenever an element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing to get the element ahead if an element is not found at the computed hash code. When found, store a dummy item there to keep the performance of the hash table intact.

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

Example

以下是各种编程语言中哈希表删除操作的实现 -

Following are the implementations of the deletion operation for Hash Table in various programming languages −

Complete implementation

以下是各种编程语言中上述操作的完整实现 -

Following are the complete implementations of the above operations in various programming languages −