hash table - hash map - 哈希表 - 散列表 - C

- 日理万妓 2022-12-25 01:45 193阅读 0赞

# **hash table - hash map - 哈希表 - 散列表 - C** #

hash：散列，杂凑，哈希
    hash table，hash map：哈希表，散列表
    hash function：哈希函数，散列函数
    key-value pair，KVP：键值对
    key：键
    hash：散列值
    value：值
    collision [kə'lɪʒ(ə)n]：n. 抵触，碰撞 (或相撞) 事故

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.  
因此，它成为一种数据结构，其中无论数据大小如何，插入和搜索操作都非常快。哈希表使用数组作为存储介质，并使用哈希技术生成索引，以在该索引中插入元素或从中定位元素。

irrespective [.ɪrɪ'spektɪv]：adj. 不顾 [不考虑，不问] … 的

## 1. Hashing ##

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.  
散列是一种将键值范围转换为数组索引范围的技术。我们将使用模运算符来获取一系列键值。考虑一个大小为 20 的哈希表的示例，以下各项将被存储。项目采用 (key, value) 格式。

![在这里插入图片描述][20201129233304107.png_pic_center]

(1, 20)
    (2, 70)
    (42, 80)
    (4, 25)
    (12, 44)
    (14, 32)
    (17, 11)
    (13, 78)
    (37, 98)

<table> 
 <thead> 
  <tr> 
   <th>Sr.No.</th> 
   <th>Key</th> 
   <th>Hash</th> 
   <th>Array Index</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>1 % 20 = 1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>2</td> 
   <td>2 % 20 = 2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>42</td> 
   <td>42 % 20 = 2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>4</td> 
   <td>4 % 20 = 4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>12</td> 
   <td>12 % 20 = 12</td> 
   <td>12</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>14</td> 
   <td>14 % 20 = 14</td> 
   <td>14</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>17</td> 
   <td>17 % 20 = 17</td> 
   <td>17</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>13</td> 
   <td>13 % 20 = 13</td> 
   <td>13</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>37</td> 
   <td>37 % 20 = 17</td> 
   <td>17</td> 
  </tr> 
 </tbody> 
</table>

serial number，sr. no.：序列号，编号

## 2. 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.  
如我们所见，可能会发生这种情况，即使用哈希技术来创建数组的已使用索引。在这种情况下，我们可以通过查看下一个单元格直到找到一个空单元格来搜索数组中的下一个空单元。这种技术称为线性探测。

<table> 
 <thead> 
  <tr> 
   <th>Sr.No.</th> 
   <th>Key</th> 
   <th>Hash</th> 
   <th>Array Index</th> 
   <th>After Linear Probing, Array Index</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>1 % 20 = 1</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>2</td> 
   <td>2 % 20 = 2</td> 
   <td>2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>42</td> 
   <td>42 % 20 = 2</td> 
   <td>2</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>4</td> 
   <td>4 % 20 = 4</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>12</td> 
   <td>12 % 20 = 12</td> 
   <td>12</td> 
   <td>12</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>14</td> 
   <td>14 % 20 = 14</td> 
   <td>14</td> 
   <td>14</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>17</td> 
   <td>17 % 20 = 17</td> 
   <td>17</td> 
   <td>17</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>13</td> 
   <td>13 % 20 = 13</td> 
   <td>13</td> 
   <td>13</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>37</td> 
   <td>37 % 20 = 17</td> 
   <td>17</td> 
   <td>18</td> 
  </tr> 
 </tbody> 
</table>

## 3. Basic Operations ##

Search - Searches an element in a hash table.  
Insert - Inserts an element in a hash table.  
Delete - Deletes an element from a hash table.

### 3.1 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 key;
        int data;  // value
    };

### 3.2 Hash Method ###

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

int HashCode(const int key) {
        return key % SIZE;
    }

## 4. hash\_table ##

/home/yongqiang/CLionProjects/hash\_table  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

//======================================================================================================================
    // Yongqiang Cheng
    //======================================================================================================================
    
    #include <stdio.h>
    #include <iostream>
    
    #define SIZE 20
    
    struct DataItem {
        int key;
        int data;  // value
    };
    
    struct DataItem *hash_array[SIZE] = {nullptr};
    struct DataItem *dummy_item = nullptr;
    
    int HashCode(const int key) {
        return key % SIZE;
    }
    
    struct DataItem *Search(const int key) {
        int hash_index = HashCode(key);
    
        // move in array until an empty
        while (hash_array[hash_index] != nullptr) {
            if (hash_array[hash_index]->key == key) {
                return hash_array[hash_index];
            }
    
            ++hash_index;
    
            // wrap around the table
            hash_index %= SIZE;
        }
    
        return nullptr;
    }
    
    void Insert(const int key, const int data) {
        struct DataItem *item = (struct DataItem *) malloc(1 * sizeof(struct DataItem));
        item->key = key;
        item->data = data;
    
        int hash_index = HashCode(key);
    
        // move in array until an empty or deleted cell
        while (hash_array[hash_index] != nullptr) {
            // go to next cell
            ++hash_index;
    
            // wrap around the table
            hash_index %= SIZE;
        }
    
        hash_array[hash_index] = item;
    }
    
    int Delete(const int key) {
        int hash_index = HashCode(key);
    
        // move in array until an empty
        while (hash_array[hash_index] != nullptr) {
            if (hash_array[hash_index]->key == key) {
                free(hash_array[hash_index]);
                hash_array[hash_index] = nullptr;
                return 1;
            }
    
            // go to next cell
            ++hash_index;
    
            // wrap around the table
            hash_index %= SIZE;
        }
    
        return -1;
    }
    
    void Display() {
        for (int i = 0; i < SIZE; ++i) {
            if (hash_array[i] != nullptr) {
                printf(" (%d, %d) ", hash_array[i]->key, hash_array[i]->data);
            } else {
                printf(" ~~ ");
            }
        }
    
        printf("\n");
    }
    
    void Release() {
        for (int i = 0; i < SIZE; ++i) {
            if (hash_array[i] != nullptr) {
                free(hash_array[i]);
                hash_array[i] = nullptr;
            }
        }
    }
    
    int main() {
        dummy_item = (struct DataItem *) malloc(1 * sizeof(struct DataItem));
        dummy_item->key = -1;
        dummy_item->data = -1;
    
        Insert(1, 20);
        Insert(2, 70);
        Insert(42, 80);
        Insert(4, 25);
        Insert(12, 44);
        Insert(14, 32);
        Insert(17, 11);
        Insert(13, 78);
        Insert(37, 97);
    
        Display();
    
        const int key = 37;
        struct DataItem *item = nullptr;
        item = Search(key);
    
        if (item != nullptr) {
            printf("Element: %d\n", item->data);
        } else {
            printf("NULL\n");
        }
    
        Delete(key);
        item = Search(key);
    
        if (item != nullptr) {
            printf("Element: %d\n", item->data);
        } else {
            printf("NULL\n");
        }
    
        Release();
    
        if (dummy_item) {
            free(dummy_item);
            dummy_item = nullptr;
        }
    
        std::cout << "Hello, World!" << std::endl;
        return 0;
    }

/home/yongqiang/CLionProjects/hash\_table/CMakeLists.txt

cmake_minimum_required(VERSION 3.14)
    project(hash_table)
    
    set(CMAKE_CXX_STANDARD 11)
    
    add_executable(hash_table main.cpp)

/home/yongqiang/CLionProjects/hash_table/cmake-build-debug/hash_table
     ~~  (1, 20)  (2, 70)  (42, 80)  (4, 25)  ~~  ~~  ~~  ~~  ~~  ~~  ~~  (12, 44)  (13, 78)  (14, 32)  ~~  ~~  (17, 11)  (37, 97)  ~~ 
    Element: 97
    NULL
    Hello, World!
    
    Process finished with exit code 0

## References ##

[https://www.tutorialspoint.com/data\_structures\_algorithms/hash\_data\_structure.htm][https_www.tutorialspoint.com_data_structures_algorithms_hash_data_structure.htm]  
[https://www.tutorialspoint.com/data\_structures\_algorithms/hash\_table\_program\_in\_c.htm][https_www.tutorialspoint.com_data_structures_algorithms_hash_table_program_in_c.htm]

[20201129233304107.png_pic_center]: /images/20221120/ed644585d16a40faa56a5c27384437db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4ebdbb4035c440f8b8492c52e7c5a50b.png
[https_www.tutorialspoint.com_data_structures_algorithms_hash_data_structure.htm]: https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
[https_www.tutorialspoint.com_data_structures_algorithms_hash_table_program_in_c.htm]: https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm