地图如何工作？

哈希

一切都是整数

哈希碰撞

整合所有

奖励回合：套装

客观看待

结论

有时，作为开发人员，您需要存储键值对。例如，您可能希望通过用户名访问用户对象。最适合这种情况的数据结构是map。它允许我们通过 中的唯一键获取值O(1)。如果您不熟悉 Big-O 符号，请查看我的文章。

让我们以你能想到的最简单的映射为例：一个数组！它存储键值对，但键仅限于自然整数。数组中的随机访问是O(1)……。但为什么呢？

在内存中，数组是一块连续的内存块。你还需要知道数组在内存中的起始位置以及每个元素的大小。要访问随机元素，只需取索引，乘以元素大小（假设元素大小均匀），再加上数组的起始地址：

memory_location_to_fetch = index * size_of_single_element + start_of_array

哈希

好的，但是如果我们想使用字符串来索引元素怎么办？这里我们将使用一种称为散列的技术。散列函数接受任意长度的输入，并产生固定长度的确定性输出。这通常由模运算符实现。

hash(x) = f(x) ℅ size_of_map

f(x)是依赖于具体实现的任意函数。最简单的函数是恒等式：f(x) = x

那么用字符串作为键怎么样？或者用对象作为键怎么样？

一切都是整数

回到计算机内存，所有内容都以二进制形式存储。但没有什么能阻止您将该二进制解释为普通整数。让我们以一个简单的字符串为例。C 字符串只是位于连续内存块中的 ASCII 字符，后缀为零字节。要将（二进制）数字转换为 ASCII，需要使用ASCII 表。作为示例，我们将字符串转换Hello为其数字表示形式（这里使用十六进制，因为转换为二进制比十进制更容易）：

 H     e     l     l     o     \0
0x48  0x65  0x6C  0x6C  0x6F  0x00

现在我们可以简单地将这 6 个字节解释为一个数字，并且可以将该数字用作哈希函数的输入。

哈希碰撞

你可能已经问过自己，如果两个不同的值被哈希后得到相同的结果，会发生什么？例如，我们有一个大小为 的 map，10分别放入0、10、20等等。

为此，我们可以实施回避策略：

• 线性散列：如果位置已被占用，则将新值移动固定量（通常为 1）
• 双重哈希：如果游戏正在进行，只需再次哈希并将我们的元素放在那里
• 使用链表作为数组元素并附加碰撞。这实际上为我们提供了填充具有相同哈希值对象的“桶”。

整合所有

现在我们将实现一个仅适用于整数的映射。我将使用 Typescript 作为示例。

正如我们已经看到的，我们可以将每种类型表示为整数，因此我们现在只关心整数。

首先，我们在地图中实际存储的内容：

class OurMap<Value> {
    private array: [number, Value][];

    constructor(size: number) {
        this.array = new Array(size);
    }
}

我们只需定义一个固定长度的数组来存储我们的键值对。

现在我们添加一个insert方法：

class OurMap<Value> {
    private array: [number, Value][];

    constructor(size: number) {
        this.array = new Array(size);
    }

    public insert(key: number, value: Value) {
        const origIndex = this.hash(key);
        let index = origIndex;
        while(this.array[index] !== undefined
          && this.array[index][0] !== key) {
            index = (index + 1) % this.array.length;
            if(index === origIndex) {
                throw new Error('Map is already full');
            }
        }
        this.array[index] = [key, value];
    }
}

你能看出我们使用了什么防撞策略吗？如果你说的是线性哈希，那你就对了！如果我们的位置已经被占用了，我们就往右移动一个位置。

该get方法的工作方式与插入方法完全相同，只是它不检查undefined您传入的键。

删除操作也类似，但我们还必须检查右侧的元素。如果存在某个元素，它可能是通过线性哈希运算得到的，因此如果原始元素缺失，则get不会尝试查找右侧元素。我们必须将这些元素移回左侧。当然，这可能会导致进一步的修正。

奖励回合：套装

您可能还偶然发现了Sets。事实证明，您可以使用 Map 来实现 Set。在旧版本的 Google Chrome 中，您可以在 DevTools 中看到这一点。Set 具有与 Map 相同的属性（包括键和值，而不仅仅是值）。

让我们通过简单地使用键作为值来复制该方法。

class OurSet {
    private map: OurMap<number>;

    constructor(size: number) {
        this.map = new OurMap<number>(size);
    }

    public insert(value: number) {
        this.map.insert(value, value);
    }
}

这种方法之所以有效，是因为使用相同的键总是指向相同的内存位置。所以，如果已经存在该键，你可以覆盖它，但这不会改变任何内容。如果没有任何条目，则可以知道该键在 Set 中尚不存在。

客观看待

数据结构都是关于权衡和用例的。那么我们的地图该放在哪里呢？

Map 和数组一样，支持O(1)插入、随机访问和删除操作。不过，这取决于 Map 的具体实现。两者都需要预先分配固定大小。如果需要动态增长的数据结构，则应该使用链表。链表也O(1)支持插入和顺序访问，但支持O(n)删除和随机访问。

如果您只想存储多个元素以便于迭代，则可以使用数组。如果您需要键值查找，则可以使用映射。您可以使用数组，但是映射会处理哈希冲突，而数组只会覆盖旧值。

结论

希望您能从本文中学到一些新东西。这是我的数据结构系列文章的第二部分，第一部分（关于大 O 符号）可以在这里找到。欢迎分享任何反馈。