hash-function - 就哈希函数而言，桶是什么？

Question

看书Mining of Massive Datasets ，第 1.3.2 节概述了哈希函数。没有计算机科学背景，这对我来说很新鲜； Ruby 是我的第一门语言，其中有一个 hash似乎相当于Dictionary<object, object> .而我从来没有考虑过怎么样这种数据结构放在一起。

书中提到哈希函数 ，作为实现这些字典数据结构的一种手段。本段:

First, a hash function h takes a hash-key value as an argument and produces a bucket number as a result. The bucket number is an integer, normally in the range 0 to B − 1, where B is the number of buckets. Hash-keys can be of any type. There is an intuitive property of hash functions that they “randomize” hash-keys

就 hash function 而言，桶究竟是什么？ ?听起来像是桶是 array-like结构，以及 hash function是某种算法/ array-like-structure每次生成相同桶号的搜索？这个比喻性的桶里面是什么？

我一直读到 javascript 对象/ruby 哈希/等不保证顺序。在实践中，我发现键的顺序没有改变(实际上，我认为使用旧版本的 Mozilla 的 Rhino 解释器，JS 对象顺序确实改变了，但我不能确定......)。

这是否意味着这些 hash functions 不能解析哈希(Ruby)/对象(JS) ?

做词 hashing根据您使用计算机的级别而具有不同的含义？即似乎 Ruby 哈希与 C++ 哈希不同......

Answer 1

当你散列一个值时，任何有用的散列函数通常都有一个较小的 范围 比域 .这意味着在输入值的大列表(例如所有可能的字母组合)中，它将输出任何一个较小的值列表(以特定长度为上限的数字)。这意味着多个输入值可以映射到同一个输出值。

在这种情况下，输出值称为桶。

考虑函数 f(x) = x mod 2

这会生成以下输出；

1 => 1
2 => 0
3 => 1
4 => 0

在这种情况下，有两个桶(1 和 0)，每个桶都有一堆输入值。

一个好的散列函数将平均填充所有这些“桶”，因此可以实现更快的搜索等。最初搜索，因为每个桶中的结果少于整个输入集。在理想情况下，散列计算速度很快，并且每个桶中只有一个结果，这使得查找所需的时间与应用散列函数所需的时间一样长。

这当然是一个简化的例子，但希望你明白了吗？