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

[RoryWee]

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

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

[AndersonHJB]

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

[Guan-shy]

简单哈希表C语言实现中， MapSet结构应该如何定义？

[SuperZhangRui]

数组添加元素O(1) ？ 还是我 有问题

[SuperZhangRui]

往数组最后一个位置添加元素时O（1） 在中间插入时O（n）

[Cynthia-lab521]

感觉是O(n)吧

[Joanna-0427]

数组写错了吧，添加元素O（n），查找元素O（1）

[Joanna-0427]

错了，根据索引查找是O（1），查找元素是O（n）

[zhangxp93]

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

[Hacker-C]

Java 实现 HashMap

ArrayList 实现，兼容 String、Integer、Boolean 作为 KEY，一起学习：dsa

package top.mphy.algo.basic.core.hashmap;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiConsumer;

public class ArrayListHashMap<K, V> {

    private static final int NOT_FOUND = -1;
    
    
    private static final int MAX_SIZE = 100;

    /**
     * 键值对节点 接口定义
     * @param <K>
     * @param <V>
     */
    public interface Entry<K, V> {
        K getKey();
        V getValue();
    }


    /**
     * 键值对节点实现
     * @param <K>
     * @param <V>
     */
    private static class Node<K, V> implements ArrayListHashMap.Entry<K, V> {
        private K key;
        private V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }

    /**
     * 桶列表，一个桶存放一个结果
     */
    private List<Node<K, V>> buckets;

    public ArrayListHashMap() {
        buckets = new ArrayList<>(MAX_SIZE);
        for (int i = 0; i < MAX_SIZE + 1; i++) {
            buckets.add(null);
        }
    }

    /**
     * 哈希函数：int
     * @param key
     * @return
     */
    private int hashFunc(Integer key) {
        return key % MAX_SIZE;
    }

    /**
     * 哈希函数：String
     * @param key
     * @return
     */
    private int hashFunc(String key) {
        int hash = 0;
        for (int i = 0; i < key.length(); i++) {
            hash = (31 * hash + key.charAt(i)) % MAX_SIZE; // 使用 31 作为乘数，取模 MAX_SIZE
        }
        return hash;
    }

    /**
     * 哈希函数：Boolean
     * @param key
     * @return
     */
    private int hashFunc(Boolean key) {
        if (key == null) {
            return MAX_SIZE;
        }
        if (key) {
            return 1;
        }
        return 0;
    }

    /**
     * 获取 hash 值
     * @param key
     * @return
     */
    private int getHash(K key) {
        if (key == null) {
            return MAX_SIZE;
        }
        if (key instanceof Integer) {
            return hashFunc((Integer) key);
        }
        if (key instanceof String) {
            return hashFunc((String) key);
        }
        if (key instanceof Boolean) {
            return hashFunc((Boolean) key);
        }
        return NOT_FOUND;
    }

    public V get(K key) {
        int index = getHash(key);
        if (index == NOT_FOUND) return null;
        Node<K, V> node = buckets.get(index);
        if (node == null) return null;
        return node.value;
    }

    public void put(K key, V value) {
        int index = getHash(key);
        if (index == NOT_FOUND) return;
        buckets.set(index, new Node<>(key, value));
    }

    public void remove(K key) {
        int index = getHash(key);
        if (index == NOT_FOUND) return;
        buckets.set(index, null);
    }

    /**
     * 获取所有键
     * @return
     */
    public List<K> keySet() {
        List<K> list = new ArrayList<>();
        for (Node<K, V> bucket : buckets) {
            if (bucket != null) {
                list.add(bucket.key);
            }
        }
        return list;
    }

    /**
     * 获取所有值
     * @return
     */
    public List<V> valueSet() {
        List<V> list = new ArrayList<>();
        for (Node<K, V> bucket : buckets) {
            if (bucket != null) {
                list.add(bucket.value);
            }
        }
        return list;
    }

    /**
     * 获取所有键值对
     * @return
     */
    public List<ArrayListHashMap.Entry<K, V>> entrySet() {
        List<ArrayListHashMap.Entry<K, V>> list = new ArrayList<>();
        for (ArrayListHashMap.Entry<K, V> bucket : buckets) {
            if (bucket != null) {
                list.add(bucket);
            }
        }
        return list;
    }

    /**
     * 遍历接口
     * @param consumer
     */
    public void forEach(BiConsumer<K, V> consumer) {
        for (Node<K, V> node : buckets) {
            if (node != null) {
                consumer.accept(node.key, node.value);
            }
        }
    }
}

[yugithubqi]

牛！

[xiaozhuge123]

day05

[zhuwantong1]

学习学习

[mygit10636]

我问百度什么是哈希，百度是这么说的：
哈希技术的基本原理是将任意长度的输入通过哈希算法转换成固定长度的输出，这个输出被称为哈希值。
由于这种转换过程类似于将数据“压缩”或“散列”成更小的形式，因此哈希也被称为散列（Hashing）或杂凑（Hashing）‌

[2450635073]

我第一次接触哈希值这个概念是在区块链技术上，玩币圈的时候每次交易有个什么局部哈希值

[rainnnnnnnnnnnnnnnnnnnnnn]

哈希函数：将较大的输入空间映射到较小的输出空间上
哈希表：键值对之间的映射集合。可以实现插入、删除、查找的O(1)快速操作。
（基于一个数组实现的哈希表中查找过程：key通过哈希函数得到哈希值再除以数组容量得到value在数组中的索引值）
哈希冲突：由于哈希函数的性质导致的哈希表中多个键映射到一个值上的问题。

[zhangxp93]

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

[guanshangshui]

哈希表有三种常用的遍历方式：遍历键值对、遍历键和遍历值。示例代码如下：
这段话有问题吧,如何通过值去遍历哈希表,键值对 对Vaule又没有要求,可以允许重复,何况给出C++代码当中也不存在第三种遍历方式
好吧打完这段字跑去看别的语言的代码发现真的有,可是为啥C++不支持呢?还是我才疏学浅?

[zhangxp93]

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

[JK233MAXD]

请教大佬，表6-1与表4-1的部分复杂度是冲突的？个人认为表4-1表述是正确的，也许是表6-1中写错了？？

[JK233MAXD]

请教大佬，表6-1与表4-1的部分复杂度是冲突的？个人认为表4-1表述是正确的，也许是表6-1中写错了？？

[guanshangshui]

4-1不是数组的内存图吗?
有什么问题,具体点

[JK233MAXD]

数组和链表的复杂度错了

[JK233MAXD]

表4-1在4.2.2 小节

[guanshangshui]

还是要看具体的结构实现,像是链表要是记录了尾指针,那么插入可以认为是O(1),删除元素如果只是指的找到元素然后可以改变指针的指向,可以认为是O(1),要是把查找元素的时间也算入也可以是认为O(N).
像数组的尾删操作是O(1),要是随机删除,比如中间删除那就是O(N),这个结构操作的时间复杂度分析,如果不能具体到结构是如何实现的,基本记住是没有多大的意义,还是要看具体的实现,不同的实现甚至对于一个操作不同的评判角度分析出来的复杂度都是不一样的,这个东西自己心里分析的清楚就行

[guanshangshui]

我看了一下,你注意一下查找元素和访问元素的不同之处.
至于下面两种操作的复杂度分析那就是不同人不同的看法了,有的人认为删除操作要带上查询的时间,有的人又认为不需要带上,仁者见仁,智者见智吧.
要是为了面试那就随大众,按照你在4.2.2节看到的那个来理解

[Canne11ia]

哈希斌かわいいね🥹

[EricCTHH]

你C语言哈希表里MapSet的实现都没写就直接用？😅