Hash Table基础

目录

1.1 什么是哈希Hash 
1.2 哈希函数 Hash Function 
    1.2.1 哈希函数性质
    1.2.2 哈希函数的选择
    1.2.3 Perfect Hash Function (PHF) 
    1.2.4 Minimal Perfect Hash Function (MPHF)  
          [Note]
    
1.3 什么是哈希表 Hash Table
    1.3.1 Key statistics 
    1.3.2 Dynamic Resizing
    1.3.3 ReHashing
1.4 冲突 Collsion
1.4 性能 
1.5 哈希表的实现 Implementation 
    1.5.1 PHF以及MPHF的实现
    1.5.2 Java Python 实现
1.6 应用 Applications 
1.7 總結 Summary 
1.7 References & External Links

1.1 什么是哈希Hash？

哈希表的实现 称之为 哈希，抑或 散列。(雜湊 For 台灣 )
哈希表在【平均】情况下以常数时间constant time 执行「插入」，「删除」和「查找」的技术。

为什么平均O(1)？原理？
最坏情况下呢？ O(n) 为什么？

但是对于元素间的【排序】操作将不会得到有效的支持。
譬如FindMax,FindMin以及按序打印元素都是散列表所不支持的。^[1]

哈希/散列 接收一个值，输出这个值的哈希值

维基百科^[2]中有一段对其的介绍：

Selected From Wiki-Hash Table [2]: 
The idea of hashing is to distribute the entries (key/value pairs) across an 
array of buckets. Given a key, the algorithm computes an index that suggests 
where the entry can be found.

1.2 哈希函数 Hash Function ？

哈希函数是可以将【任意大小】的数据映射为【固定】大小数据的一个函数。其返回数据的哈希值。
哈希函数的一个用处是用来实现哈希表Hash Table. 哈希表在计算机科学中被广泛应用以提高查询性能。
哈希函数在密码学，Cache , 布隆过滤器，等中也有所应用。^[3]

关于具体的哈希函数，请参见List of hash_functions

维基百科[3]：
    A hash function is any function that can be used to map data of arbitrary size to data of fixed size. 
    The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. 
    One use is a data structure called a hash table, widely used in computer software for rapid data lookup. 
    Hash functions accelerate table or database lookup by detecting duplicated records in a large file.

1.2.1 哈希函数性质

一个好的哈希函数通常需要满足下列属性。当然，一个哈希函数要满足哪些性质，还要看具体的应用决定。
Determinism
Uniformity
Defined range
Variable range
Data normalization
Continuity
Non-invertible.

关于哈希函数的若干性质，参见Hash Function 维基百科

1.2.2 哈希函数的选择

存在着很多各种各样的哈希函数，这些函数都不尽相同。
对于特定的应用而言，如何选取合适的哈希函数是一个重要的问题。
函数的选择强烈依赖于输入数据的性质, 以及它们在预期应用程序中的概率分布。^[3]

Trivial hash function 平凡哈希函数，
Perfect hashing 完美哈希，
Minimal perfect hashing，最小完美哈希，
Hashing uniformly distributed data 哈希均匀分布数据，
Universal hashing,Rolling hash ...
等等。具体描述参见Hash Function 维基百科

下面对PHF,与MPHF作进一步学习。
当键值是【static(即固定不变)】的时候，我们可以涉及方案使得最差情况下的查询性能也很出色。
由此引入了

• PHF 最坏时间O(1),
• 与MPHF 最坏时间O(1),空间O(n)。

1.2.3 Perfect Hash Function (PHF)?

即【沒有冲突】的哈希函数^[2] no collisions
即：^[5]

 函数 Hash 将 N 个 Key 值映射到 M 个整数上，这里 M>=N 
     对于任意的 Key1 ，Key2 ，
     Hash( Key1 ) != Hash( Key2 )   

如何construct? 见[4]

拓展：

• Dynamic perfect hashing 【动态完美哈希函数】
• Minimal perfect hash function 【最小完美哈希函数 】
• Order preservation 【保序最小完美哈希函数】
  • key _I < key _J 等价于 Hash(key _I ) < Hash(key _J )
  • 满足 Minimal perfect hash function

1.2.4 Minimal Perfect Hash Function (MPHF)?

在1.2.3 Perfect Hash Function (PHF)中，若M==N,则为MPHF.

维基百科[4]:
A minimal perfect hash function is a perfect hash function that maps n keys to n
consecutive integers – usually the numbers from 0 to n − 1 or from 1 to n

NOTE:
静态
[5]
通常情况下，PHF或MPHF是针对静态集合的。也就是，在使用PHF或MPHF时，
所有的 KEY 值是事先已知并且固定的。
不过，这里有针对动态集合的一个算法（我没有仔细看，不敢肯定）

[6]
缺点：
一是必须事前必须知道原数据集，二是需要花一定的CPU来生成这个函数。
我认为，对于数据仓库类的线下搜索应用，这个算法是有用武之地的。
但对于强调实时的数据业务，这个算法是不适合的。  

1.3 什么是哈希表^[7] ?

哈希表是一种基于键-值(key-index) 的数据结构。
哈希表通过哈希函数实现key , index的转换。

[7]
Selected From Wiki-Hash Table : 
    In computing, a hash table (hash map) is a data structure which implements an 
associative array abstract data type, a structure that can map keys to values. A 
hash table uses a hash function to compute an index into an array of buckets or
slots, from which the desired value can be found.

在很多情况下，哈希表在平均性能上【优于】 搜索树以及 table lookup structure。
因此哈希表在计算机领域中得到广泛应用，尤其是涉及数组，数据库索引，Cache和Set.

1.3.1 Key statistics

• load factor = n/k
  • n is the number of entries
  • k is the number of slots

load factor 过大，冲突可能性增加；
load factor 过小，空间的浪费。

1.3.2 Dynamic Resizing

动态调整大小

 For example, in Java's HashMap class the default load factor threshold for
 table expansion is 3/4 and in Python's dict, table size is resized when load 
 factor is greater than 2/3

1.3.3 Rehashing

O(n)

1.4 冲突

冲突问题

优于哈希函数不一定是完美哈希函数或者是slots过少，因此可能会导致冲突发生，产生冲突可以有多重方法加以解决。

解决办法

• 分离链接法
• 开放定址法
  • 线性探测
  • 平凡探测
• Rehash

1.4 性能

[7]
In the simplest model, the hash function is completely unspecified and the table does not resize. For the best possible choice of hash function, a table of size k with open addressing has no collisions and holds up to k elements, with a single comparison for successful lookup, and a table of size k with chaining and n keys has the minimum max(0, n − k) collisions and O(1 + n/k) comparisons for lookup. For the worst choice of hash function, every insertion causes a collision, and hash tables degenerate to linear search, with Ω(n) amortized comparisons per insertion and up to n comparisons for a successful lookup.

Adding rehashing to this model is straightforward. As in a dynamic array, geometric resizing by a factor of b implies that only n/bi keys are inserted i or more times, so that the total number of insertions is bounded above by bn/(b − 1), which is O(n). By using rehashing to maintain n < k, tables using both chaining and open addressing can have unlimited elements and perform successful lookup in a single comparison for the best choice of hash function.

In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires Θ(1 + n/k) comparisons on average for an unsuccessful lookup, and hashing with open addressing requires Θ(1/(1 − n/k)).[25] Both these bounds are constant, if we maintain n/k < c using table resizing, where c is a fixed constant less than 1.

1.5 Implementation 实现

1.5.1 PHF以及MPHF的实现

关于PHF以及MPHF的实现，这位博主已经给了较好的总结，
我不认为我可以比他总结的更好。于是就照搬过来吧。
参见 ：
完美哈希函数（Perfect Hash Function） 的【PHF和MPHF生成程序库】以及【PHF和MPHF生成算法】部分。

1.5.2 Java Python 实现

待续

1.6 应用 Applications

待续

1.7 總結 Summary

哈希表作为常数平均时间查询与插入的数据结构。采用哈希函数实现。
哈希函数常常是不完美的因此会产生冲突问题，对此也有一系列的解决方法。
哈希表也可以动态调整。
完美哈希函数在一些库中已经得到了较好的实现。哈希表在Java等编程语言中也得到了实现。
哈希表作为一个优秀的数据结构在计算机科学的很多领域都发挥着重要的作用。

1.8 References & External Links

References

[1] 数据结构与算法-C语言描述[Mark Allen Weiss] Chapter 5

[2] Hash Table维基百科

[3] Hash Function 维基百科

[4] Perfect Hash Function维基百科

[5] 完美哈希函数（Perfect Hash Function）- Blog

[6] 最小完美哈希函数简介-Blog

[7] Hash_table维基百科

External Links

Distributed hash table

Calculate hash of a given value by Timo Denk