chapter_hashing/hash_map/

[giscus[bot]]

chapter_hashing/hash_map/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_hashing/hash_map/

[iron-irax]

大佬，在”哈希表优势“那一小节中，在“有序数组： 将 1. 中的数组按照学号从小到大排序”中，“1.”找不到对照。4种数据结构用有序列表列出会不会更好一些？

[krahets]

感谢指正！好细心，想请你点击右上角的铅笔按钮修正该内容

[iron-irax]

没有编辑经验>-<，参照后文提交了修改。

[zoujia]

@krahets，突然发现评论写错地方了😅最近在学习您的算法教程，每个代码（JS）都自己写一遍，学到了不少~感谢！！

[mingxin0528]

文章中对比五种数据结构各操作的时间复杂度中，链表的插入元素应该是O(n)。

[mingxin0528]

我指那个表格

[krahets]

哈喽，因为存储是无序的，因此可以直接插入在头部或尾部，复杂度为 O(1)

[mingxin0528]

明白了，感谢！

[chencaize]

数据结构操作时间复杂度那，链表删除不是O(1)吗？

[krahets]

这里的删除操作需要先查询，在一个无序链表中查询元素的时间复杂度为 $O(n)$ ，单独的删除操作是 $O(1)$

[yoke2002]

在初始化哈希表中（JavaScript 代码）：const map = new ArrayHashMap();，JavaScript 中没有这个 API，后面看到这个构造函数是在自己实现哈希表那里取的名称，但是作为介绍哈希表的部分，使用系统（Map）的是否更合适一些？

[krahets]

谢谢建议，一般会用一个和 built-in 不太一样的名字，以提醒读者这是我们自己实现的，比如 MyList, ArrayStack 等。

[thatshinji]

/* 获取所有键值对 */
public entries(): (Entry | null)[] {
    let arr: (Entry | null)[] = [];
    for (let i = 0; i < this.bucket.length; i++) {
        if (this.bucket[i]) {
            arr.push(this.bucket[i]);
        }
    }
    return arr;
}

这一块儿 typescript 代码是不是不对？获取所有键值对，看起来只 push 了键？

[justin-tse]

你好，数组this.bucket里的放的元素是我们自己定义的类Entry的实例
下面给出array_hash_map.ts里对类Entry的定义

/* 键值对 Number -> String */
class Entry {
    public key: number;
    public val: string;

    constructor(key: number, val: string) {
        this.key = key;
        this.val = val;
    }
}

下面给出例子，给自己定义的map添加元素

const map = new ArrayHashMap();
/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.set(12836, '小哈');

ArrayHashMap里的添加操作这个方法是这样定义的

/* 添加操作 */
public set(key: number, val: string) {
    let index = this.hashFunc(key);
    this.bucket[index] = new Entry(key, val);
}

this.bucket里面存的是Entry的实例，所以是有key和value的，这里代码应该是没问题的

[thatshinji]

啊 不好意思，我的问题，我脑子自动忽略了 Entry 实例，感谢解答！

[AliksFan]

哈希表底层实现是数组、链表、二叉树，那为什么效率可以更高呢

[krahets]

Hi! 首先，哈希表的时间效率变高，但空间效率变低了。我们可以将哈希表想象成一个具有许多槽位的收纳盒，那么不可避免地，相当一部分槽位是空置的。相反地，链表则可根据需求来申请内存，数组虽然也有扩容机制导致的空间浪费，但和哈希表相比不是一个级别。

其次，只是在特定使用场景下时间效率变高了。如果一个功能能够在相同的时间复杂度下使用数组或链表实现，那么一般来说都是要比哈希表更快的。虽然时间复杂度都是 $O(1)$ ，但哈希表各种操作更复杂（需要经过哈希函数），被化简的那个“常数项”更大。

• 举个例子，给定一堆小球，实现一个“随机抽出一个小球”的函数。这个函数使用数组和哈希表都很容易实现，时间复杂度也都是 $O(1)$ ，此时我们应该选择数组，因为它更快更省空间。

最后，哈希表的时间复杂度可能发生劣化，例如在拉链法中，我们不得不在链表或红黑树种执行查找操作。在实际中，多多少少都会发生一点儿劣化，只是太难解决 + 影响不大而已。

[AliksFan]

理解了，谢谢！ o(*≧▽≦)ツ┏━┓

[woLQL]

问一下，为什么不使哈希函数f(x) = x 呢。这样就不会有冲突了。

[krahets]

很好的问题。f(x) = x 的情况与数组等价，即每个元素对应唯一的数组索引。换句话说，哈希表的目标是将一个较大的状态空间 map 到一个较小的空间，并提供 O(1) 的查询效率。

[woLQL]

也就是说，当 f(x) = x 的情况下，会导致空间比较大，不太符合哈希表的目标。那样我是不是可以理解为，哈希表就是不太希望出现0冲突这种情况，这种情况会导致需要的空间非常大。最佳的情况就是有一部分冲突。使“键值对占用空间 / 哈希表总占用空间”比例最大化。
那样衍生出一个问题，在C++底层STL容器框架中，它是不知道我要放多少键值对，也不知道我要放的键值的。在这种未知的情况下它是怎么去设置这个 f(x) 的呢？

[krahets]

是的。哈希表希望零冲突，但这是无法做到的。因为输入空间往往远远大于哈希表空间，所以哈希冲突无法被完全避免。换言之，我们希望的是哈希函数可以将冲突平均分布在每个桶内，最大化地保证查询效率。

[woLQL]

谢谢解答

[ThreeAurora]

受教了，才知道哈希表算的是key和数组下标的关系，之前居然还以为是key 和 value的关系，实在是一点不懂啊哈哈

[libai-ovo]

array_hash_map.java

public ArrayHashMap() {
        // 初始化数组，包含 100 个桶
        buckets = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            buckets.add(null);
        }
    }
有点好奇初始化这么写有什么好处么，为什么不直接传入容量呢

[krahets]

Hi, 可以传入容量

buckets = new ArrayList<>(100);

以上代码虽然指定了 HashMap 的容量，但其中仍不包含任何元素。此时 get() 和 set() 方法都会报错 IndexOutOfBoundsException 。 因此，通过 for-loop 添加元素是必须的。

[libai-ovo]

好的，谢谢解答，这是使用ArrayList的妥协，它的set和get方法检查的是实际的size而不是数组的length，都需要有元素时才能调用，我只想到了底层是Object数组，那应该有null的初值，所以显示写入初值null让我有点奇怪

[zrcoder]

哈希表是一个神奇的数据结构。但其实需要细较下它的复杂度，我们仅拿查找 key 为例，人人都说是常数时间复杂度，实际上是过于笼统了，因为没有考虑求 key 的哈希值的复杂度。

比如对于key类型为 string 的哈希表，要在其中找到一个 key，首先需要对这个key做一次哈希计算，字符串的话至少要遍历一次这个字符串，也就是哈希计算的复杂度为 O(m)，m 指key的长度，总的查询复杂度也是 O(m)。

当然，对于 int 类型的key，哈希计算的复杂度确实是常数级。

综上，如果 key 是 string 或复合类型（元组等）且 key 的平均长度很长，用哈希表效率非常低。

[chusifeng]

有个疑惑，hash表 时间复杂度为啥是O(1)，不应该是O(n) 吗？
计算出key的hash值这个是1，但是从hash表查询，不可能第一个就命中吧，是不是需要逐个比对？这个过程来说是不是就取决于hash表的容量大小了

[krahets]

是的，由于哈希冲突的存在，很有可能无法一次命中，因此哈希表的最差时间复杂度是 $O(n)$ 。当哈希函数设计的比较好、容量设置比较合理、冲突比较平均时，时间复杂度是 $O(1)$ 。我们一般使用哈希表无需关心底层工作方式，一律认为是 $O(1)$ 。

[liweijian199011]

上面数组，链表和哈希表的对比表看蒙了，应该明确一点。数组如果根据下标查询应该是O(1)，而插入元素平均复杂度也应该是O(n)，怎么就成了O(1)。链表的插入元素的复杂度为啥是O(1)，不是应该是O(N)吗？

[krahets]

Hi，这里需要正确理解查询元素的含义。我们想要实现的是在一组元素中，查询一个指定元素。

• 在数组中，我们需要遍历数组来查询一个指定元素，因此时间复杂度是 $O(n)$ 。
• 向数组或链表插入元素时，只需要添加到尾部即可，因此时间复杂度为 $O(1)$ 。

我更新一下文中的用词

[riiyn]

大佬，这里的数组查询，是不是给定一个值，查询这个值在数组中的位置，这样时间复杂度O(n)才解释得通啊

[krahets]

@riiyn 是的

[ellem2023]

链表插入尾部，是不是还额外需要尾指针，不然时间复杂度是O(n)吧

[li199-code]

我感觉哈希冲突示例图那里容易引起误会。哈希冲突是在添加新元素时发生的，新的元素可能顶掉旧元素，而不是查找时发生的。图里面呈现的是查找过程。

[krahets]

Hi，哈希冲突是指多个不同的 key 被映射到同一桶索引的情况。无论是查询、添加或删除，都有可能发生。图中展示的是因为冲突导致的查询错误问题。

[zhuasdfg]

打卡，手敲了一遍哈希表的数组实现，对index和key才真正分清楚

[krahets]

动手学 才是 真的学

[wkyfasttank]

也就是理解为哈希表比数组链表拥有更小的时间复杂度是用更大的空间复杂度换的吗？

[krahets]

一般来说，我们认为哈希表和数组的空间复杂度都是 $O(n)$ 。但哈希表确实比数组需要使用更多的内存空间。

哈希表使用哈希函数直接定位到数据的存储位置，因此查询效率比数组更高。哈希函数的运作机制导致其使用了更多的内存空间。

[cipual]

~ArrayHashMap() {
    // 释放内存
    for (const auto &bucket : buckets) {
        delete bucket;
    }
    buckets.clear();
}

请问这里内存释放为什么需要传入引用

[oopfjp]

避免拷贝操作吧，直接传引用少了拷贝操作，提高算法效率。

[condi15]

想问一下，关于void pairSet(ArrayHashMap* hmap, MapSet* set),此函注中首次出现“MapSet”类型，但是我没有找到该类型的定义。我使用的是C语言版代码。

[condi15]

现在找到了，问题已解决。

[condi15]

出现这个问题的原因是，网页上的代码片段与源代码中的代码内容不一致。所以大家下载使用源代码好一点。

[Nhckdvrl]

这哈希表我觉得写的一坨啊

[1435646097]

简单实现，理解概念就好了

[wHwangw]

请问为什么我在CLion运行源文件 array_hash_map.c 会报错:

添加完成后，哈希表为
Key -> Value

进程已结束，退出代码为 -1073741819 (0xC0000005)

[quirkybird]

这个哈希表就算我容量很大，如果我就只有两个值，哈希函数key % 100，刚好都是36这样，那如何保证准确性啊

[ZWZ28]

哈希函数也要跟着变吧

[krahets]

Hi，这个就是“哈希冲突”的情况，下一节会讲如何解决

[yehongdu]

 /* 获取所有键值对 */
    vector<Pair *> pairSet() {
        vector<Pair *> pairSet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                pairSet.push_back(pair);
            }
        }
        return pairSet;
    }

    /* 获取所有键 */
    vector<int> keySet() {
        vector<int> keySet;
        for (Pair *pair : buckets) {
            if (pair != nullptr) {
                keySet.push_back(pair->key);
            }
        }
        return keySet;
    }

这两个函数的函数名和里面的变量名是一样的，这样是可以的吗？
请大神指教

[yalesohn]

go语言版本map写的是链式寻址，查了一下，好像是开放寻址

[krahets]

Hi，可以分享一下来源吗？

[luommy]

是结合的不是单一的；https://mp.weixin.qq.com/s?__biz=MzkxMjQzMjA0OQ==&mid=2247483868&idx=1&sn=6e954af8e5e98ec0a9d9fc5c8ceb9072

[chumingqian]

你好， 作者：
表6-1 中， 能否确认一下， 数组的 插入和删除是 O(N), 查询 是O(1), 而链表的 插入和删除是 O(1), 查询是 O(N), 能否核实一下。

[Daryl-Dixon-boy]

表6-1中有误，链表删除应该是O(1)，表中误写为O(n)

[Royatina]

表6-1是正确的，表上方三行文字有解释，这里的删除包含先查找再删除，复杂度是O(n)

[ruomu007]

buckets= vector<Pair * > (100) 这只是给buckets确定容量，这样确定容量的方式好像 不怎么常见。为什么不用buckets.reserve(100)的方式确定容量？

[simplast]

话说，我直接用数组索引当key，不就不用hash了吗

[Thatonewall]

同问

[krahets]

在 key 的范围不大的情况下，可以这样做，例如：

• key 是 26 个字母，那么我们用一个长度为 26 的数组就可以；
• key 是 [0, 10000] 的数字，那么用一个长度为 10000 的数组就可以；

但实际情况下，key 的范围可能是很大的（甚至是无限的），例如：

• key 是全体整数；
• key 是全体字符串；

哈希表的设计使得它可以适用于这些情况，即将一个较大的输入空间映射到一个较小的空间内（取决于桶的数量）。

[Thatonewall]

为什么不直接把学号当做数组的索引呢

[zhangxp93]

哈希表是不是不适用于python呀？python的字典本身就是用哈希表实现的，操作性更强，还不会有冲突，时间复杂度O(1)

[jaffe-fly]

示列用python 感觉绕了一圈一样，没看懂。python的字典好像更简单

[Blueman123456]

Mapset是什么类别？

[just-shine]

//MapSet
typedef struct {
void *set;
int len;
}MapSet;

[Blueman123456]

为什么添加操作里还要为pair->val开辟一块空间，直接将两个指针像等不就可以了吗？

[zhangxp93]

您好！       收到————张贤平