mysql - 哈希表是如何工作的？它比 "SELECT * from .."快吗

Question

比方说，我有:

Key | Indexes | Key-values
----+---------+------------
001 | 100001  | Alex
002 | 100002  | Micheal
003 | 100003  | Daniel

Lets say, we want to search 001, how to do the fast searching process using hash table?

Isn't it the same as we use the "SELECT * from .. " in mysql? I read alot, they say, the "SELECT *" searching from beginning to end, but hash table is not? Why and how?

By using hash table, are we reducing the records we are searching? How?

Can anyone demonstrate how to insert and retrieve hash table process in mysql query code? e.g.,

SELECT * from table1 where hash_value="bla" ...

另一种情况: 如果索引像 S0001、S0002、T0001、T0002 等。在 mysql 中我可以使用:

SELECT * from table WHERE value = S*

是不是一样而且更快？

Answer 1

一个简单的哈希表通过将项目保存在多个列表中而不是一个列表中来工作。它使用一种非常快速且可重复(即非随机)的方法来选择将每个项目保留在哪个列表中。因此，当需要再次查找该项目时，它会重复该方法以发现要查找的列表，然后在该列表中进行正常(缓慢)的线性搜索。

通过将项目分成 17 个列表，搜索速度提高了 17 倍，这是一个很好的改进。

虽然这当然只有在列表长度大致相同的情况下才是正确的，所以选择一种在列表之间分配项目的好方法很重要。

在您的示例表中，第一列是键，是我们查找项目所需的东西。假设我们将维护 17 个列表。为了插入一些东西，我们对键执行一个称为散列的操作。这只是把 key 变成了一个数字。它不返回随机数，因为它必须始终为相同的 key 返回相同的数字。但与此同时，数字必须广泛“传播”。

然后我们获取结果数并使用模数将其缩小到列表的大小:

Hash(key) % 17

这一切发生得非常快。我们的列表在一个数组中，所以:

_lists[Hash(key % 17)].Add(record);

然后，使用该键查找项目:

Record found = _lists[Hash(key % 17)].Find(key);

请注意，每个列表可以是任何容器类型，或者您手写的链表类。当我们在该列表中执行 Find 时，它的工作速度很慢(检查每条记录的键)。