查找表究竟是如何工作的以及如何实现它们？

Question

我最近做了一个程序，它处理了很多 if/else 语句来返回特定的值。有人建议改用查找表。我的问题是，

1. 它们如何工作以及您如何实施它们？
2. 映射、哈希表和查找表之间有什么区别。

Answer 1

我的问题是，它们如何工作以及如何实施？stl 映射、哈希表和查找表之间有什么区别。

您正在寻找的是一种有效的机制，您可以通过它查找与给定键对应的值。

您当前的机制（一长串 if/else-if 命令）效率很低，因为如果您有 N 个可能的值可供选择，您（平均而言）必须将您的候选键与 (N/2) 个其他键进行比较在您找到匹配的那个之前，您可以停止查找。（这被称为 O(N) 复杂度）

那么还有哪些选择呢？

最简单的实际上只是一个值数组，例如

const char myLookupTable[1000] = {
    "zero",
    "one",
    "two",
    [...]
    "nine hundred and ninety-nine"
};

...使用这样的查找表，您需要一个键（在这种情况下是一个介于 0 和 999 之间的数字，包括 0 和 999），并使用单个数组查找查找相应的值：

 const char * val = myLookupTable[500];

这是超级高效的（O(1) 复杂度——它总是在恒定时间内完成，无论数组有多大！），但它仅适用于您的键是连续（且相对较小）范围内的无符号整数的情况值。例如，如果您的键是字符串，则此方法不适用。

为了获得更大的灵活性，下一个选项是 STL 的std::map. std::map为您提供从任何键类型到任何值类型的快速键->值查找。在内部，它被实现为树：每个键值对都以这样的方式插入到树中，使得树保持排序，最小的键在树的左边，最大的键在右边。因此，在一个std::map只是从树的根节点开始并将该节点处的键与您正在查找的键进行比较的问题：它是否小于您的键？然后移动到右边的孩子。或者它比你的钥匙大？然后移动到左手孩子。重复此操作，直到到达树的底部，此时您要么会找到要查找的键值对，要么会发现它不存在。这是一个复杂度为 O(log(N)) 的算法，因为对于其中包含 N 个值的树，需要进行 log(N) 次比较才能完成查找。O(log(N)) 被认为是非常好的效率。

您提到的最终数据结构是哈希表（如 中所示std::unordered_map）。哈希表的作用略有不同——在内部它是一个数组，但为了避免查找表方法的局限性，它还附带了一种算法，用于确定给定的键/值对在其数组中的位置存储。它通过为您传入的键对象计算哈希码来实现这一点——然后使用该代码计算数组中的偏移量（例如int array_offset = hash_code % array_size) 并查看数组中的该插槽以查看请求的键值对是否存在。如果是，那么就完成了（再次 O(1) 性能！）；或者如果插槽为空，则它知道您的密钥不在表中并且可以立即返回失败（再次 O(1)）。如果插槽被其他一些键/值对占用，那么哈希表将需要回退到另一个算法来整理hash collision；不同的哈希表以不同的方式处理，但通常仍然相当有效。

Answer 2

你的问题确实太广泛了，因为 StackOverflow 不是一个教程网站，但今天早上我感觉很友善......

“查找表”只是一个容器（任何类型的容器），其中包含您查找的值，并且通常映射到其他值。

以最简单的形式，请考虑以下内容：

struct MapIntToString
{
    int value;
    char* string;
};

MapIntToString my_map[] = {
    { 1, "one" },
    { 2, "two" },
    { 3, "three" },
    // ...
};

上面可以被认为是一个查找表。您可以迭代（循环）my_map来查找（查找）整数2，然后从中选取字符串"two"。

根据您的需求和用例，上面的示例可能还不够。上面的代码基本上是用纯 C（而不是 C++）通常完成的。对于 C++，有更好的容器用于映射值，例如std::map和std::unordered_map。

然而，有时标准类型可能还不够，并且可以实现许多其他数据结构来查找事物。