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)$ 。

[small-fresh-meet]

上面数组，链表和哈希表的对比表看蒙了，应该明确一点。数组如果根据下标查询应该是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)$ 。但哈希表确实比数组需要使用更多的内存空间。

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

[Jeffstarm]

哈希表的元素数量不是等于桶数量么，求高手解答一下

[Coolllh]

在不存在hash冲突时，哈希表的元素数量等于桶数量，但是如果存在哈希冲突的话，则桶数量小于哈希表元素数量，因为在存在哈希冲突时，一个桶内存了多个元素，比如存了一个有多个节点的链表，假设hash算法是对数字进行取余10，则1和11的结果是相同的，这个时候取余结果为1的1和11，会按照加入哈希表的顺序存放在桶中，一般来说是一个链表，但是在jdk1.8中改成了红黑树，别的语言的实现不太清楚

[roadxia1]

~ArrayHashMap() {
// 释放内存
for (const auto &bucket : buckets) {
delete bucket;
}
buckets.clear();
}
我想请教一下作者
&bucket为什么要加const呢，在后面的代码中不是需要对bucket进行修改吗

[3Ajfdjsdsk2]

同问。常量引用后不是不能更改原变量的相关值吗

[AlsoWereMe]

bucket在这里是指向buckets中Pair对象的指针，const关键字的确会阻止你修改bucket指针本身的值，但是delete只是删除了指向的对象并释放掉了指针指向的对象所占用的内存，并没有修改指针本身，bucket在使用delete后仍然指向原来的内存，但此时这一片内存已被释放，这和C的free()是类似的。

[3Ajfdjsdsk2]

感谢解答 @AlsoWereMe

[FrierenGreatDemonLord]

发现错误：表 6-1 元素查询效率对比 -> 链表删除 $O(n)$
链表删除改一下指针引用就行了，应该是 $O(1)$ 才对，之前的对应的章节也明确提到删除是 $O(1)$

[FrierenGreatDemonLord]

在不确定待删除节点在链表中的位置时，需要线性查找到该节点后才能指向删除，此时确实是 $O(n)$

[FrierenGreatDemonLord]

确实，还是得分情况。哈希表通过建直接就找到了值，“一键删除”了属于是，而链表需要考虑的事情就很多了

[FrierenGreatDemonLord]

C++ 字典也可以通花括号来初始化，如：

unordered_map<int, string> m = { {1, "one"}, {2, "two"}, {3, "three"} };

[FrierenGreatDemonLord]

来自C++ 小白的总结

C++ 的 for (auto it = map.begin(); it != map.end(); it++);
相当于最平常for 循环，只不过变量声明是auto

• 初始化：auto it = map.begin()
• 循环测试：it != map.end()
• 执行更新：it++

使用auto 的优点

• 简洁方便
• 易于维护
• 类型安全（类型自动推导）

[FrierenGreatDemonLord]

Python 中对于键值的遍历也可用列表解析式进行优化，如：

def entry_set(self) -> list[Pair]:
    return [pair for pair in self.buckets if pair]

[FrierenGreatDemonLord]

C 的remove() 可以加个非空判断，会更加鲁棒一点。
不像Python 直接赋值为None 即可，C 中还要释放值和键值对所分配的内存，一不小心控制程序去操控一个空对象，自然会碰溃掉。

void remove(HashMap* map, int key) {
	int i = hashFunc(key);
	if (!map->buckets[i])
		return;
	free(map->buckets[i]->val);
	free(map->buckets[i]);
	map->buckets[i] = NULL;
}

[JFWind-0323]

C#的Pair类是不是错了，？应该是运用于结构体的，对于类来说有无？都是一样的，而且类可以直接写构造函数吗？

[ZZY080]

1212

[ZZY080]

12121

[liuyang1858]

表 6-1 元素查询效率对比，关于数组和链表的访问、插入和删除的时间复杂度是不是弄错了，数组的访问应该时O(1),插入O(n),删除O(n),链表的访问O(n),插入O(1),删除O(1)。

[HarrryHe]

同问

[OrangeAlien]

插入和删除的方式不同，复杂度也不一样。
对于数组和链表，在第i个元素后插入或删除，时间复杂度是O(n)。数组需要移动后面的元素，链表需要从头数i个元素。
对于单链表，在给定节点后插入或删除，时间复杂度是O(1)，在给定节点前插入或删除，时间复杂度是O(n)，因为需要从头开始，查找给定节点的前节点，需要修改前节点的next指针。如果是双链表，在给定节点前后插入或删除，时间复杂度都是O(1)。

数组和链表可以用作动态查找表，主要用于查找元素，还需要支持插入和删除操作。
将数组作为动态查找表，在维护时，可以考虑在数组的尾部插入或删除，时间复杂度是O(1)。由于维护的查找表是无序的，删除时可以将尾部元素和待删除元素交换，然后删除尾部元素。
将链表作为动态查找表，在维护时，可以在链表头部或尾部插入或删除，时间复杂度是O(1)。尾部插入或删除的话需要一个尾指针。

[liuyang1858]

~ArrayHashMap() {
// 释放内存
for (const auto &bucket : buckets) {
delete bucket;
}
buckets.clear();
}这里已经delete内存了数据应该直接就没有了，怎么还需要再clear()

[carpentist]

因为buckets中存储的是bucket的指针，通过指针析构Pair，但没有清除buckets中存在的指针本身，clear是为了清空buckets动态数组的

[selfboot]

我做了一个哈希表的可视化页面，采用网格布局模拟哈希表的内部结构。

每个格子代表一个哈希桶，格子的颜色深浅直观地反映了该桶中存储的元素数量，颜色越深表示包含的元素越多。可以点击任意格子，系统会显示一个弹窗，展示该桶中存储的所有键值对详细信息。

在进行插入、查找、删除等操作时，系统会通过高亮效果显示当前操作涉及的桶，帮助理解哈希表的工作原理。

[HanHuiOnLine]

出现冲突了，那岂不是把之前的数据覆盖了，需要做其他处理的吧

[selfboot]

是的，处理冲突是hash必须要考虑的。比如开链法，二次hash等

[AndersonHJB]

图片是用什么软件制作的？求