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)$ 。但哈希表确实比数组需要使用更多的内存空间。

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

[bnufw]

Hi,我用上面的代码创建一个实例a=ArrayHashMap()，并且a.put(1,'a')
然后，当执行print(a.value_set())，输出的是空列表，问题在哪？

[hpstory]

Hi @bnufw , 请问是python代码吗，我这边运行没有问题，如果可以的话，请提供一些详细信息，比如python版本，使用的完整代码等等。

[bnufw]

不好意思，我抄的过程中缩进出现错误了。value_set方法中最后的return往里缩进了一下

[krahets]

@bnufw 建议直接从仓库下载源代码哦～

[Mrzhang007]

元素数量除以桶数量为负载因子，当负载因子超过 时，系统会将哈希表扩容至原先的2倍。那么当hash map容量为100的时候，存放75个pair就要扩容了对吧？

[hazel-hammer]

哈希表的底层逻辑是动态数组。但是各个键值对的数据类型可能不一样，占用内存空间也不一眼，为什么可以用数组进行存储呢？

[qw124341789]

我的理解是哈希函数就是找 ：输入数和输出值地址的关系，关系越牢靠，哈希冲突就越少。

[qw124341789]

重新琢磨了下哈希函数，上述我的理解是错误的，所有的数都有一个值，就算是字符都有对应的数值，输入key经过哈希函数把他变成数组的下标，输出的索引的需求值

[hazel-hammer]

但是哈希函数是不能用来反解的呀，所以键值对还是要分别存储的，但不同的键值对占用的空间不一致

[qw124341789]

不太懂你疑惑的是啥，分别存储的话，创建在C里面创建一个结构体就行了

[shinehhht]

为什么在获取entries.val是不能直接赋值，而必须strcpy？只是为了防止因修改hsmp的val的值而导致指针指向无效内存吗？

[simploo]

哈希表6.1节，数组、链表、哈希对比图中，数组和链表部分的时间复杂度不对

[simploo]

数组查找是O(1),新增和删除是O(n);链表差查询是O(n),新增和删除是O(1)，才对

[NicholasGGW]

个人理解如下，
1.查找
- 1.1数组不知道索引的情况，需要从头到尾遍历是O(n)；
- 1.2链表查找需要从头到尾遍历是O(n)；
2.添加元素
- 2.1尾部新增，如果是将元素添加至尾部则都是O(1)；
- 2.2添加至中间，数组在不知道索引的情况下和链表需要添加至中间某一元素之前或之后，则都需要先查找后插入，且插入操作数组需要对后续的元素后移赋值，为O(n)；而链表的插入操作是O(1)。查找+插入的总的复杂度不会算=v=；
3.删除元素
- 与添加元素同理，若为中间元素需要查找后删除，数组还需要后续元素前移的操作。

[xiaoqingma0]

都对，就是不同角度理解:-)

[CCCCCC777]

/* 遍历哈希表 */
// 遍历键值对 key->value
for (auto kv: map) {
cout << kv.first << " -> " << kv.second << endl;
}
// 使用迭代器遍历 key->value
for (auto iter = map.begin(); iter != map.end(); iter++) {
cout << iter->first << "->" << iter->second << endl;
}
他这个的运行机制是什么为什么我看不懂，kv.frist 代表什么，kv.second又代表什么
它是如何实现键值对的遍历的，迭代器遍历又是怎么遍历的，有哪些知识需要补充？

[MingyuW488]

在 C++ 的标准库中，std::pair 是用来存储一对值的模板类，其中第一个值可以通过 first 成员访问，第二个值可以通过 second 成员访问。在 std::map 这样的关联容器中，每个元素都是一个键值对，其中键和值被存储在一个 std::pair 对象中。

因此，当你使用 auto kv 来迭代一个 std::map 容器时，kv.first 表示当前键值对中的键，而 kv.second 则表示当前键值对中的值。这是因为 std::pair 的设计使得键值对的第一个元素可以通过 first 访问，第二个元素可以通过 second 访问。

[CCCCCC777]

将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。

index = hash(key) % capacity
那他的意思是不是就是key上有对应的index，通过index来找相应的value
这个后面的公式是什么意思啊

[CCCCCC777]

公式看懂了，知道怎么计算，但是原理不太懂，为什么要这样写，作者有什么推荐的知识点补充吗？

[Campbell0]

哈希函数的作用是尽可能将键均匀的分布到桶中，减少冲突

[YMMdrq]

这个公式的意义就是通过key可以在O（1）时间内查到vaule。

[cipual]

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

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

[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，可以分享一下来源吗？

[chumingqian]

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