8

假设，我有：

钥匙 | 索引 | 键值
----+----------+------------
001 | 100001 | 亚历克斯
002 | 100002 | 迈克尔
003 | 100003 | 丹尼尔

比方说，我们要搜索 001，如何使用哈希表进行快速搜索过程？

不是和我们在mysql中使用“SELECT * from ..”一样吗？我读了很多，他们说，“SELECT *”从头到尾搜索，但哈希表不是吗？为什么以及如何？

通过使用哈希表，我们是否减少了我们正在搜索的记录？如何？

谁能演示如何在 mysql 查询代码中插入和检索哈希表过程？例如，

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

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

SELECT * from table WHERE value = S*

不是一样而且更快吗？

4

5 回答 5

14

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

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

当然，这仅在列表长度大致相同时才适用，因此选择一种在列表之间分配项目的好方法很重要。

在您的示例表中，第一列是键，我们需要找到该项目。假设我们将维护 17 个列表。要插入一些东西，我们对键执行一个称为散列的操作。这只是将密钥转换为数字。它不返回随机数，因为它必须始终为同一个键返回相同的数字。但与此同时，数字必须广泛“分散”。

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

Hash(key) % 17

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

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

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

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

请注意，每个列表可以是任何容器类型，也可以是您手动编写的链表类。当我们在该列表中执行 aFind时，它的工作方式很慢（检查每条记录的键）。

于 2009-02-12T08:59:49.603 回答
4

不要担心 MySQL 在内部做什么来快速定位记录。数据库的工作就是为你做那种事情。只需运行一个SELECT [columns] FROM table WHERE [condition];查询，让数据库为您生成一个查询计划。请注意，您不想使用SELECT *，因为如果您向表中添加一列，这将破坏所有依赖于以特定顺序存在一定数量列的旧查询。

如果您真的想知道幕后发生了什么（很高兴知道，但不要自己实现它：这就是数据库的目的！），您需要知道索引是什么以及它们是如何工作的。如果表在 WHERE 子句中涉及的列上没有索引，那么，正如您所说，数据库将不得不搜索表中的每一行以找到符合您条件的行。但是如果有索引，数据库会搜索索引以找到你想要的行的确切位置，并直接跳转到它们。索引通常实现为B+-trees，一种使用很少比较来定位特定元素的搜索树。在 B 树中搜索特定键非常快。MySQL 也能够使用散列索引，但这些索引对于数据库的使用往往较慢。散列索引通常只在长键（尤其是字符串）上表现良好，因为它们将键的大小减小到固定的散列大小。对于整数和实数等数据类型，它们具有明确定义的排序和固定长度，B-tree 的易搜索性通常提供更好的性能。

您可能想查看MySQL 手册和PostgreSQL 手册中关于索引的章节。

于 2009-02-12T07:42:25.357 回答
1

http://en.wikipedia.org/wiki/Hash_table

哈希表可以用作内存数据结构。哈希表也可以用于持久数据结构；数据库索引有时使用基于哈希表的基于磁盘的数据结构，尽管平衡树更受欢迎。

于 2009-02-12T07:45:54.617 回答
0

哈希表非常适合以 O(1) 的成本定位条目，其中密钥（用于哈希）是已知的。它们在馆藏库和数据库引擎中都广泛使用。您应该能够在互联网上找到大量有关它们的信息。你为什么不从维基百科开始，或者只是做一个谷歌搜索？

我不知道mysql的详细信息。如果那里有一个称为“哈希表”的结构，那可能是一种使用哈希来定位键的表。我相信其他人会告诉你这件事。=)

编辑：（回应评论）

行。我将尝试做一个非常简单的解释：哈希表是一个表，其中条目基于键的函数定位。例如，假设您要存储有关一组人的信息。如果将其存储在一个普通的未排序数组中，则需要按顺序遍历元素才能找到您要查找的条目。平均而言，这将需要 N/2 次比较。

相反，如果您将所有条目放在基于人员名字的第一个字符的索引中。（A=0、B=1、C=2 等），只要您知道名字，您就可以立即找到正确的条目。这是基本思想。您可能意识到，为了支持具有相同首字母的多个条目，需要进行一些特殊处理（重新散列或允许条目列表）。如果您有一个尺寸良好的哈希表，您应该能够直接找到您正在搜索的项目。这意味着与我刚刚提到的特殊处理的免责声明进行了大约一次比较。

于 2009-02-12T07:01:25.330 回答
0

我想您可以使用哈希函数来获取要从中选择的 ID。像

SELECT * FROM table WHERE value = hash_fn(whatever_input_you_build_your_hash_value_from)

然后您不需要知道要选择的行的 id 并且可以进行精确查询。由于您知道该行将始终具有相同的 id，因为您构建了散列值形式的输入，并且您始终可以通过散列函数重新创建此 id。

然而，这并不总是正确的，具体取决于表的大小和散列值的最大数量（您通常在散列中的某处有“X mod hash-table-size”）。为了解决这个问题，您应该有一个确定性策略，每次您获得两个具有相同 id 的值时都使用该策略。您应该查看Wikipedia以获取有关此策略的更多信息，它称为冲突处理，并且应该在与哈希表相同的文章中提及。

由于提到的 O(1) 特性 norheim.se (up)，MySQL 可能在某处使用哈希表。

于 2009-02-12T07:37:23.590 回答