查看大规模数据集挖掘一书,第1.3.2节概述了散列函数.没有计算机科学背景,这对我来说是一个新的东西; Ruby是我的第一语言,hash似乎相当于Dictionary<object, object>.我从未考虑过如何将这种数据结构组合在一起.
本书提到了哈希函数,作为实现这些字典数据结构的一种手段.本段:
首先,散列函数h将散列键值作为参数,并产生桶号作为结果.桶号是一个整数,通常在0到B-1的范围内,其中B是桶的数量.哈希键可以是任何类型.散列函数有一个直观的属性,它们可以"随机化"散列键
桶的确切含义是hash function什么？听起来像桶是array-like结构,而且每次都会产生相同的桶号的hash function某种算法/ array-like-structure搜索？这个隐喻桶里面有什么？
我一直都读到javascript对象/ ruby哈希/ etc不保证顺序.在实践中我发现键的顺序没有改变(实际上,我认为使用旧版本的Mozilla的Rhino解释器,JS对象命令DID改变了,但我不能确定......).
这是否意味着哈希(Ruby)/对象(JS)没有被这些解决hash functions？
hashing根据您使用计算机的级别,该词是否具有不同的含义？即看起来Ruby散列与C++散列不一样......
散列值时,任何有用的散列函数通常都具有比域小的范围.这意味着在大量输入值(例如所有可能的字母组合)中,它将输出任何较小的值列表(以特定长度限制的数字).这意味着多个输入值可以映射到相同的输出值.
在这种情况下,输出值被称为存储桶.
考虑函数f(x)= x mod 2
这会产生以下输出;
1 => 1
2 => 0
3 => 1
4 => 0
在这种情况下,有两个桶(1和0),每个桶都有一堆输入值.
一个好的哈希函数将同等地填充所有这些"桶",因此可以更快地搜索等.如果您使用任何数字的mod,您可以查看桶,因此必须搜索比您刚刚搜索更少的结果最初搜索,因为每个桶的结果都比整个输入集少.在理想情况下,哈希计算速度很快,每个桶中只有一个结果,这使得只有应用哈希函数才能进行查找.
这是一个简化的例子当然,但希望你能得到这个想法？