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) 格式。

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

Sr.No.	Key	Hash	Array Index
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

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

Sr.No.	Key	Hash	Array Index	After Linear Probing, Array Index
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

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.

References

https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
https://www.tutorialspoint.com/data_structures_algorithms/hash_table_program_in_c.htm