为什么这样呢?我的意思是:我有一个键,我对它进行了哈希处理...我得到了哈希值...难道算法不应该将此哈希值与每个元素的哈希值进行比较吗?我认为内存布局背后肯定有一些诀窍,不是吗?
使用数组:如果你知道值,你必须平均搜索一半的值(除非已经排序)才能找到它的位置。
使用哈希表:位置是根据值生成的。因此,再次给定该值时,可以计算出插入时计算的相同哈希值。有时,多个值会导致相同的哈希值,因此在实践中,每个"位置"本身都是一个数组(或链接列表),包含所有哈希到该位置的值。在这种情况下,只需要搜索这个更小的数组(除非哈希函数很差)。
哈希表有些复杂。它们根据元素的哈希 % 某个值将元素放入不同的桶(bucket)中。在理想情况下,每个桶只包含极少量的项且没有太多的空桶。
一旦你知道了键,就可以计算哈希。根据哈希值,你知道要查找哪个桶。而且,如上所述,每个桶中的项目数量应该相对较小。
哈希表在内部做很多魔法以确保桶尽可能地小,同时不会为空桶消耗太多内存。此外,关键是键-哈希函数的质量。
维基百科提供了非常全面的哈希表说明。
哈希表不需要比较哈希表中的每个元素,它会根据键计算出哈希码。举例来说,如果键是4,则哈希码可能是-4*x*y。现在指针就知道要选择哪个元素了。
相比之下,如果使用数组,它将必须遍历整个数组来搜索该元素。
% num_buckets
的越界桶访问,因此如果有12个桶,则ideal + 4和ideal + 16搜索相同的桶。跟踪已搜索的桶可能很昂贵,因此很难知道何时放弃:实现可以乐观地假设它将始终找到值或未使用的桶(冒着永远旋转的风险),它可以拥有计数器,并在尝试阈值之后放弃或开始逐个桶进行线性搜索。std::unordered_set
则是一种闭地址法和分离链接的例子。index = hash%capacity
。unsigned int
和unsigned long long
。为了严谨起见,C ++技术上规定其原语的最小大小即至少32位和至少64位,但那不是重点。为了使代码具有可移植性,C ++还提供了一个相应的无符号整数size_t
。在良好编写的代码中,您会经常看到这种类型用于索引数组的for循环中。在像Python这样的语言中,整数原语会增长到所需的任何大小。这通常在其他语言的标准库中以“大整数”的名称实现。为了解决这个问题,Python编程语言会将您从__hash __()
方法返回的任何值截断为适当的大小。product = hash(31 * product + hash(array[index]))
这样的东西,而不是像product = 31 * product + hash(array[index])
这样的东西。内部hash()调用的主要目的是将可能不是数字的东西转换为数字,而外部hash()调用的主要目的是将潜在的超大数字截断。最后,我要注意的是,在像C++这样的语言中,整数基元具有固定的大小,每个操作后都会自动执行这个截断步骤。set
或dict
,或C++的std::unordered_set
或std::unordered_map
,主要通过以下两种方式处理这个问题。第一种被称为分离链接,第二种被称为开放地址。在分离链接中,充当哈希表的数组本身是一个列表数组(或在某些情况下,如果开发人员感觉想要使用其他数据结构,如二叉搜索树),每次元素哈希到给定索引时,它都会被添加到相应的列表中。在开放地址中,如果一个元素哈希到已经被占用的索引,数据结构会探测到下一个索引(或在某些情况下,如果开发人员感觉想要使用其他函数定义的索引,如二次探测),依此类推,直到找到一个空槽位,当然当它到达数组末尾时会回到开头。set
和dict
类使用最大负载因子2/3,而Java的java.util.HashSet
和java.util.HashMap
使用3/4,C++的std::unordered_set
和std::unordered_map
则以最大负载因子1获胜。毫不奇怪,Python的哈希表支持的数据结构使用开放地址法处理冲突,而它们的Java和C++对应物则使用分离链接法。
最后关于表格大小的评论。当超过最大负载因子时,哈希表的大小必须增加。由于这需要重新索引其中的每个元素,因此按固定量增加表格大小非常低效。这样做会在每次添加新元素时产生数量级的操作。解决此问题的标准方法与大多数动态数组实现所采用的方法相同。在我们需要增加表格的每个点上,我们只需将其大小增加到当前大小。不出所料,这被称为表格加倍。
我认为你已经回答了自己的问题。"算法不应该将此哈希与每个元素的哈希进行比较"。当它不知道你要搜索的索引位置时,这就是它所做的。它会比较每个元素以找到你要查找的元素:
例如,假设你正在查找一个名为"Car"的项目,该项目位于字符串数组中。你需要遍历每个项目并检查item.Hash() == "Car".Hash(),以找出那是你要查找的项目。显然,它并不总是在搜索时使用哈希,但这个例子仍然成立。然后你有一个哈希表。哈希表所做的是创建一个稀疏数组,或者有时是桶数组,如上面提到的。然后它使用"Car".Hash()来推断出你的"Car"项实际上在稀疏数组中的哪个位置。这意味着它不必搜索整个数组来找到你的项目。