See also 负载均衡算法

Algorithm/Hash Function

Hash Function,又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values,hash codes,hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。

A perfect hash function for the four names shown

hash-function.svg

1. 应用

1.1. Hash Tables

散列表是散列函数的一个主要应用,使用散列表能够快速的按照关键字查找数据记录。例如,在英语字典中的关键字是英文单词,和它们相关的记录包含这些单词的定义。在这种情况下,散列函数必须把按照字母顺序排列的字符串映射到为散列表的内部数组所创建的索引上。

散列表散列函数的几乎不可能/不切实际的理想是把每个关键字映射到唯一的索引上(参考完美散列),因为这样能够保证直接访问表中的每一个数据。

1.2. Caches

散列函数还用于为慢媒体中存储的大型数据集构建缓存。缓存通常比散列搜索表简单,因为任何冲突都可以通过丢弃或回写两个冲突项中的旧项来解决。

散列函数也可以用于文件比较。

2. 属性

良好的哈希函数,通常需要满足下面列出的某些属性,这些属性也被称作哈希函数的术语。

2.1. Determinism

哈希过程必须是确定性的——这意味着对于给定的输入值,它必须总是生成相同的哈希值。换句话说,它必须是要散列的数据的函数,从数学意义上讲就是这个术语。这个要求排除了依赖于外部变量参数的哈希函数,例如伪随机数生成器或一天的时间。它还排除了依赖于被散列对象的内存地址的函数,以防在执行过程中地址可能会改变(在使用某些垃圾收集方法的系统上可能会发生这种情况),尽管有时可以重新散列项。

2.2. Uniformity

一个好的哈希函数应该尽可能均匀地映射其输出范围内的预期输入。也就是说,输出范围中的每个哈希值都应该以大致相同的概率生成。最后一个需求的原因是,基于哈希的方法的成本急剧上升,因为映射到相同哈希值的输入对对的数量增加了。如果某些哈希值比其他值更可能发生,那么查找操作的更大一部分将不得不搜索大量的冲突表条目。

注意,这个标准只要求值是均匀分布的,而不是随机分布的。一个好的随机化函数(不考虑计算效率问题)通常是作为哈希函数的一个不错的选择,但反过来不一定是正确的。

2.3. Defined range

通常希望哈希函数的输出具有固定的大小。例如,如果输出限制为32位整数值,那么可以使用哈希值索引到数组中。这种哈希通常用于加速数据搜索。另一方面,加密哈希函数产生更大的哈希值,以确保蛮力反演的计算复杂度。例如,SHA-1是使用最广泛的加密哈希函数之一,它产生一个160bit的值。

2.4. Data normalization

在某些应用场景中,输入数据可能包含与比较目的无关的特性。例如,在查找个人姓名时,可能需要忽略大写字母和小写字母的区别。对于此类数据,必须使用与所使用的数据等效性标准兼容的哈希函数:即,任何两个被认为等效的输入都必须产生相同的哈希值。这可以通过在对输入进行哈希之前对其进行规范化来实现,比如将所有字母都用大写字母表示。

2.5. Continuity

一个用来搜索相似(而不是等效)数据的哈希函数必须尽可能连续;两个稍有不同的输入应该映射为相等或几乎相等的哈希值。

2.6. Non-invertible

在加密应用程序中,哈希函数通常被认为是实际上不可逆转的,这意味着不花费大量计算时间就仅从哈希值h(x)重新构造输入数据x是不现实的。

3. 算法

对于大多数类型的散列函数,函数的选择很大程度上取决于输入数据的性质,以及它们在预期应用程序中的概率分布。

3.1. Trivial hash function

如果要散列的数据足够小,可以使用数据本身(重新解释为整数)作为散列值。计算这个“平凡”(标识)哈希函数的成本实际上为零。这个哈希函数非常完美,因为它将每个输入映射到一个不同的哈希值。

3.2. Perfect hashing

一个被注入的哈希函数——也就是说,将每个有效的输入映射到一个不同的哈希值——被认为是完美的。使用这样的函数,您可以直接在哈希表中查找所需的条目,而无需进行任何额外的搜索。

4. Reference


CategoryAlgorithm

MainWiki: Hash (last edited 2013-10-27 06:11:13 by twotwo)