chapter_hashing/hash_algorithm/

[giscus[bot]]

chapter_hashing/hash_algorithm/

动画图解、一键运行的数据结构与算法教程

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

[Desperado1001]

Mark

[Ak5mai]

看不明白，如果整数的哈希值就是本身的话，不就没有映射了吗？求解答 orz

[krahets]

是的，index = hash(key) % capacity 最后还要对 capacity 取余

[Hyrmm]

我的理解是,数值本身就具备单项性，是唯一的

[is-liu]

大佬们这个上一页和下一页能把不能挪到评论区上面，或者是映射个快捷键，总是去点目录感觉有些不舒服

[krahets]

好的收到，已移动至评论区上方～

[malone6]

• 上一页用 P 键 (previous page) 或者 , 键 (也是键盘符号<)
• 下一页用 N 键 (next page) 或者 . 键 (也是键盘符号>)

[zoujia]

我更习惯使用左、右方向键来切换上一页、下一页😅👍

[zzzpppy]

mac m2 快捷键貌似无效

[insomnia-city]

也就是说完备的哈希算法可以广泛运用于数据安全验证中，防篡改

[TechnologyK]

现在政府项目开始使用SM3了。

[52coder]

// hash example
#include <iostream>
#include <functional>
#include <string>

int main ()
{
  int num = 3;
  size_t hashNum = std::hash<int>()(num);
  bool bol = true;
  size_t hashBol = std::hash<bool>()(bol);
  double dec = 3.14159;
  size_t hashDec = std::hash<double>()(dec);
  std::string str = "Hello 算法";
  size_t hashStr = std::hash<std::string>()(str);

  std::cout << "hash(num):" << hashNum <<'\n';
  std::cout << "hash(bol):" << hashBol <<'\n';
  std::cout << "hash(dec):" << hashDec <<'\n';
  std::cout << "hash(str):" << hashStr <<'\n';

  return 0;
}
root@52coder:~/workspace/cpp# ./a.out
hash(num):3
hash(bol):1
hash(dec):17027819519382460022
hash(str):12677847606289151974

为什么我用c++代码跑出来的hash值和文章中的不一致？
g++ --version g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
编译命令:
g++ hash.cc && ./a.out

[krahets]

std::hash 在不同的平台和编译器中可能采用不同的哈希算法实现，因此无法保证哈希值相同

[zzqshishui]

hash(num):2613195814
hash(bol):67918732
hash(dec):2064320989
hash(str):1853464
请问为什么我的值是这样的？

[zengcheng123]

在C++中，整数和布尔值（true和false）在某些情况下可能会直接被用作哈希值，尤其是对于那些简单的数据类型，因为编译器或实现可能会选择直接使用它们的内存地址作为哈希。然而，这并不是一种通用的做法，也不是语言标准规定的行为。

通常，哈希函数的设计目的是生成一个数据的唯一标识，而不仅仅是原始值。对于整数和布尔值，更常见的做法是通过某种算法将这些值转换为一个范围内的整数，这个整数作为哈希值，这样可以确保即使两个相同的原始值也会得到不同的哈希结果，有助于在哈希表中快速查找。

如果是在自定义哈希函数或者使用标准库提供的哈希容器（如unordered_map或unordered_set）时，程序员通常会手动定义一个哈希函数来处理这些基本类型，而不是依赖于它们的内存地址。

[fancyop]

我使用g++跟楼主的结果一致（gcc version 8.3.0 (x86_64-posix-seh, Built by strawberryperl.com project)）

3
1
17027819519382460022
12677847606289151974

另外 Visual Studio 2022 (v143) 的结果为：

17086694953553481862
12638152016183539244
4418545003319772381
2313268924304215928

[daifee]

细心的你可能发现在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（Salt）值。

hash算法其中一个重要原则是“确定性”，与上面“随机盐”就矛盾了

[pycat13]

我对“随机盐”的加入也不是很理解，大佬能解释下吗？

[Claw-some]

这并不矛盾，所谓的确定性，只需要在这个哈希表的生命周期内就行。加盐就是加入随机数，不同的盐可以让同样的key通过hash算法后得到不同的值，当然，在new 一个 HashMap的时候这个盐必须是确定的。

[kubawell]

这里说的“输出的哈希值是不同的” 这句话有歧义，这里应该不能叫哈希值了，哈希在任何时间输出的值都是确定的，不然不可能做完整性校验，只是Python 解释器启动过程中利用到了Hash，再加了随机盐，并不是说Hash值每次随着Python 解释器启动都会变。

[tineline]

大佬可以推荐几个相应的练习题网站或者leecode题库吗

[krahets]

Hi～可以看看这里

[Curyain]

讲得很透彻，对于入门级来说，是一个不可多得学习资料，谢谢大佬

[Roy-rb2]

关于哈希函数，推荐一篇文章，可以配合着看
https://samwho.dev/hashing/

[HangSeven]

打不开啊哥哥

[Roy-rb2]

链接是正常的，可能需要翻个墙

[Purdre]

书中说加法哈希无法区分内容相同但顺序不同的字符串，是不是内容不同加法哈希也可能产生哈希冲突，比如“ad"和"cb"，"cam"和"nab"

[krahets]

Hi，对于所有哈希算法，不同的内容都可能产生哈希冲突。没有哈希算法可以做到 0% 的冲突概率

[Purdre]

好的，谢谢！

[louis100]

请问大佬，旋转哈希中的这个旋转(hash << 4) ^ (hash >> 28)，是什么原理呀？

/* 旋转哈希 */
function rotHash(key) {
    let hash = 0;
    const MODULUS = 1000000007;
    for (const c of key) {
        hash = ((hash << 4) ^ (hash >> 28) ^ c.charCodeAt(0)) % MODULUS;
    }
    return hash;
}

[lonelychinaday]

(hash << 4) ^ (hash >> 28) 是 MurmurHash3 算法的一部分。MurmurHash3 是一种快速的非加密哈希函数，它在性能和质量方面都表现良好。它被广泛用于数据库、文件系统和其他需要高性能哈希函数的应用程序。

MurmurHash3 算法使用 32 位整数作为输入，并生成 32 位整数作为输出。它使用一个 128 位初始化向量和一个 32 位随机数作为种子。

MurmurHash3 算法的工作原理如下：

1. 将输入整数转换为 128 位二进制字符串。
2. 将 128 位二进制字符串分成 16 个 8 位字节。
3. 对每个 8 位字节执行以下操作：
   1. 将字节左移 4 位。
   2. 将字节右移 28 位。
   3. 对这两个结果进行异或运算。
4. 将所有 16 个结果异或在一起，得到 32 位哈希值。

MurmurHash3 算法是快速、高效且安全的。它在性能和质量方面都表现良好，并且在许多应用程序中都得到了广泛使用。

[Hyrmm]

如果说数值的hash值是本身，那么意味着存在某个字符串和某个数值的key， 映射冲突吗？

[jiuerya7]

是有可能的，但是哈希表的设计会避免这种冲突，比如前面讲的链式地址和开放寻址，以及后面还没讲的二叉树代替链式地址

[bnufw]

这一节的哈希算法是对上两节的value做key吧。也就是对要存的字符串赋予编号

[bnufw]

是做key还是做index呀？

[Gipsyfine]

我的理解是通过哈希算法计算数据（也就是key）对应的哈希值，然后对桶数量（数组长度）capacity 取模，从而得到index，也就是index = hash(key) % capacity

[bnufw]

数据结构的哈希值中，是不是将数据看成value,其哈希值看成是key?

[krahets]

Hi，这里没有 key-value 的概念。我们只是用哈希算法计算得到数据对应的哈希值（可以把数据看作 key ）

[shinehhht]

hash & mod ,mod不应该是二进制数吗？感谢

[krahets]

Hi，应为 hash % mod ，这里的 mod 是一个数字，它可以表示为十进制、二进制等任何进制类型

[Fulin-Gao]

python里面 hash(-1)=-2，hash(-2)=-2，这是咋回事啊

[krahets]

Hi，在 Python 中，哈希值 -1 为保留值（因为在 Python 的内部实现中，-1 通常被用作错误标记或特殊情况的标志），Python 的设计者决定让 hash(-1) = -2

[f820602h]

在許多程式語言中，只有不可變對象才可作為雜湊表的 key
請問可以舉個例子嗎？就我所知 js 或 python 若是以對象或陣列作為 key 時，都會以其「引用」作為 key 而非其本身，應該就沒有該變其值就無法查詢的問題。

[krahets]

这个具体要看对象的 hash value 是如何实现的，举个例子：

• Python 中的元组 tuple 不可变，可以用作字典的 key ；
• Python 中的列表 list 可变，因此不可用作字典的 key ，因为当列表元素变化时，它的 hash value 也会改变。

[kang-int]

数据完整性检查：数据发送方可以计算数据的哈希值并将其一同发送；接收方可以重新计算接收到的数据的哈希值，并与接收到的哈希值进行比较。如果两者匹配，那么数据就被视为完整。
如果发送方发送的哈希值在传输过程中发生了改变，而数据是完整的，接收方再用这个错的哈希值去比较，不是会误报吗

[krahets]

如果发送方发送的哈希值在传输过程中发生了改变

这个几率极低，因为哈希值很短（还不如有些网址长），和文件内容大小完全不是一个量级

[1435646097]

也不是完全没有道理，所以软件都是除了给软件的下载链接外，边上还会对应一个hash码（不用下载，直接看就可以了），方便你下载玩后去校验软件的完整性

[1i9htning]

作者您好，在C++中，std::vector的底层实现为迭代器。也就是说动态数组中的元素并不是其成员。那么一个std::vector对象是否为可哈希的呢？因为其成员的内存地址不变，只是其存放元素的地址在变化（即成员迭代器的值变化了）

[Xinkun666]

作者你好
/* 异或哈希 */
int xorHash(string key) {
int hash = 0;
const int MODULUS = 1000000007;
for (unsigned char c : key) {
hash ^= (int)c;
}
return hash & MODULUS;
}
这段代码里，最后将总的哈希与大质数进行“与”运算，请问这里本来是取模操作，还是就是进行“与”运算，如果进行与运算那么这个质数有很多位是0，进行取与后也势必使最终的哈希值对应位置为0，那么这样就不符合哈希函数要尽量满足均匀分布这一条件了，所以我猜测这里大概率是进行取模操作。

[wangx77]

同问这个问题，这个“与”操作的含义是什么？

[jiuerya7]

二进制的位与运算，每一位比较，1为真，0为假，真+ 真 = 真，真+假=假，假+假=假

[jiuerya7]

我感觉应该是作者写错了，应该是取余操作，否则哈希值有可能会变得很大。@krahets，这里是不是应该是取余操作？

[jiuerya7]

你往前翻一翻，up回复过别人了，这里就是写错了，应该是%，不是&

[selfboot]

感觉缺少一致性 hash 的介绍。包括 hashring 环法，或者 jumphash 这些。这些在负载均衡领域很通用。
我这里做了个一致性 hash，hash 环的可视化演示，支持影子节点的演示，可以配合理解。

[huih99]

哈希表章节看完了，但还是没有明白这个哈希表到底起什么用，容量如何设计的。如果哈希表是一个数组存储，那么这个章节中讲的hash算法计算key，这个key怎么确保是数组长度内的索引呢？如果哈希表不是数组存储，那么上一章节讲到的线性探测、平方探测等如何能实现呢

[xuaidongx]

取模运算就是把哈希值映射到数组索引范围内，
比如 hash_value%capacity 的结果就是落到[0, capacity)的左闭右开区间

[huih99]

实在是无法理解哈希表的作用

[huih99]

什么情况下，需要将大的输入空间映射到小的输出空间呢？为什么哈希表采用数组结构，而不是直降将key作为字符串索引存储到对象中呢

[gfzum]

输入空间总是会大于输出空间，用户可以输入的数字、字符串是无限的。使用哈希表映射后的好处是可以在 O(1) 内实现查找、添加、删除，而这是基于数组 index 的方式实现的，连续内存空间的地址访问不需要像字符串那样遍历比较查找。

[hasban12138]

例如相似1,100000，和5000这种数据 如果要用数组要开很大 但是如果用哈希实际只需要3个就够了

[majiang213]

我有一个问题，MD5、SHA-1、SHA-2 和 SHA-3 这些Hash 摘要算法输出的不是一个整数，而编程语言使用的 Hash 算法为什么计算出来是整数？编程语言的 Hash 算法不是使用这些已有的吗？

[copyman471]

现有的流行哈希算法输出的都是整数。你觉得不是整数应该是因为十六进制显示的原因，把结果换算成十进制你就明白了

[xuaidongx]

#ifndef __CUSTOMHASHMAP_HPP__
#define __CUSTOMHASHMAP_HPP__

/**
 * @file customHashMap.hpp
 * @brief 基于vector数组实现哈希表,哈希冲突解决方式:链式地址
 */

#include <vector>
#include <list>
#include <tuple>
#include <functional>

template<typename Key, typename Value>
class HashChainContainer;

template<typename Key, typename Value, template<typename, typename> typename Container = HashChainContainer>
class CustomHashMap
{
    using Base = CustomHashMap;
public:
    const Value& get(const Key& key) const {return m_elements.get(key);}
    Value& get(const Key& key){return const_cast<Value&>(const_cast<const Base*>(this)->get(key));}
    
    void put(const Key& key, const Value& value){m_elements.put(key, value);}
    void remove(const Key& key){m_elements.remove(key);}
    bool empty() const {m_elements.empty();}

    Value& operator[](const Key& key){return m_elements[key];}
private:
    Container<Key, Value> m_elements;
};

template<typename Key, typename Value>
class HashChainContainer
{
public:
    HashChainContainer(){m_elements.resize(m_capacity);};
    void put(const Key& key, const Value& value)
    {
        if ((m_size / (double)m_capacity) >= m_load_factory)
            expand();

        auto& list = m_elements[std::hash<Key>{}(key) % m_capacity];
        auto finder = std::find_if(std::begin(list), std::end(list), [&](auto& element)
        {
            auto& [e_key, e_value] = element;
            return e_key == key;
        });
        if (finder != std::end(list))
            std::get<1>(*finder) = value;
        else
        {
            list.emplace_back(key, value);
            ++m_size;
        }
    }

    const Value& get(const Key& key) const
    {
        auto& list = m_elements[std::hash<Key>{}(key) % m_capacity];
        auto finder = std::find_if(std::begin(list), std::end(list), [&](auto& element)
        {
            auto& [e_key, e_value] = element;
            return e_key == key;
        });
        if (finder == std::end(list))
            throw std::out_of_range("key not found");

        return std::get<1>(*finder);
    }

    void remove(const Key& key)
    {
        auto& list = m_elements[std::hash<Key>(key) % m_capacity];
        auto finder = std::find_if(std::begin(list), std::end(list), [&](auto& element)
        {
            auto& [e_key, e_value] = element;
            return e_key == key;
        });
        if (finder != std::end(list))
        {
            list.erase(finder);
            --m_size;
        }
    }

    void expand()
    {
        m_capacity *= m_expand;
        m_elements.resize(m_capacity);
    }

    bool empty() {return m_size == 0;}

    Value& operator[](const Key& key)
    {
        auto& list = m_elements[std::hash<Key>{}(key) % m_capacity];
        auto finder = std::find_if(std::begin(list), std::end(list), [&](auto& element)
        {
            auto& [e_key, e_value] = element;
            return e_key == key;
        });
        if (finder == std::end(list))
            return std::get<1>(list.emplace_back(key, Value{}));

        return std::get<1>(*finder);
    }
private:
    std::size_t m_size{0};
    std::size_t m_expand{2};
    std::size_t m_capacity{1007};
    double m_load_factory{0.75};
    std::vector<std::list<std::tuple<Key, Value>>> m_elements;
};



#endif //__CUSTOMHASHMAP_HPP__

[xiaozhuge123]

day05

[Lovi-Dzy]

打卡第二天

前面身体不舒服，生病漏了几天

[Guts-g20]

请问：6.3.1均匀分布 均匀分布会降低冲突后的查询的时间复杂度，但是为什么会降低冲突概率，冲突概率应该是与输入有关吧？求解🤔

[halofu]

首先补充你的结论，是从输入经过哈希函数后得到哈希值的分布越均匀，这串输入在哈希表上的冲突概率越低。

要看不同的输出分布，以哈希表-链式地址的图6-8可以很明确看出来。当分布集中在一个桶的时候，这个桶上的所有key都是冲突的，则所谓的冲突概率越高。而当分布均匀分散开来的时候，每个桶的对象数量要远远小于集中分布，此时便可以说在输出分布趋向均匀分布的时候，冲突概率会降低。

最后，如果要讨论冲突概率和哈希函数的关系，这在哈希算法设计中已经提到了。即便是均匀分布的输入，在不同的模数下也会得到不同的分布，也会导致冲突概率的不同。