小白入门——哈希算法
哈希
哈希（Hash）也称为散列，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，这个输出值就是散列值。
哈希表
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列表是算法在时间和空间上作出权衡的经典例子
如果没有内存限制，我们可以直接将键作为（可能是一个超大的）数组的索引，那么所有查找操作只需要访问内存一次即可完成。但这种理想情况不会经常出现，因为当键很多时需要的内存太大。另一方面，如果没有时间限制，我们可以使用无序数组并进行顺序查找，这样就只需要很少的内存。而散列表则使用了适度的空间和时间并在这两个极端之间找到了一种平衡。事实上，我们不必重写代码，只需要调整散列算法的参数就可以在空间和时间之间作出取舍。我们会使用概率论的经典结论来帮组我们选择适当的参数。
使用Hash的查询算法分为两步：
① 用Hash函数将被查找的键转化为数组的一个索引。 理想情况下，不同的键都能转化为不同的索引值。当然，这只是理想情况，所以我们需要面对两个或者多个键都会散列到相同的索引值的情况。 ② 处理碰撞冲突的过程
Hash函数
一个好的Hash函数应满足下列两个要求：
- 一致性 —— 等价（equal）的key必然产生相等的hash code
- 高效性 —— 高效的计算
- 均匀性 —— 均匀地散列所有的key
几种常见的Hash算法：
① 除法哈希法
公式：hash(key) = key mod M
注意：M 通常为“素数”
② 乘法哈希法
公式：hash(key) = floor( M/W * ( a * key mod W) )
其中 floor 表示对表达式进行下取整
注意：
- 通常设置 M 为 2 的幂次方。
- W 为计算机字长大小（也为2的幂次方）。
- a 为一个非常接近于W的数。
其实，“乘法哈希”的思想就是：提取关键字 key 中间 k 位数字。
③ 斐波那契（Fibonacci）哈希法
也就是当 “乘法哈希法” 的 a ≈ W/φ，1/φ ≈ (√5-1)/2 = 0.618 033 988 时情况。而，1/φ ≈ (√5-1)/2 = 0.618 033 988，可称为黄金分割点。
Q：那，为什么“斐波那契（Fibonacci）哈希法”能够更好的将关键字 key 进行散列了? A：Why is 'a ≈ W/φ' special? It has to do with what happens to consecutive keys when they are hashed using the multiplicative method. As shown in Figure ‘Fibonacci Hashing’ , consecutive keys are spread out quite nicely. In fact, when we use 'a ≈ W/φ' to hash consecutive keys, the hash value for each subsequent key falls in between the two widest spaced hash values already computed. Furthermore, it is a property of the golden ratio, φ , that each subsequent hash value divides the interval into which it falls according to the golden ratio!
常见的两种解决碰撞的方法
① 拉链法（separate chaining）
一个Hash函数能够将键转换为数组索引，Hash算法的第二部是碰撞处理，也就是处理两个或多个键的Hash值相同的情况。一种直接的办法是将大小为 M 的数组中的每个元素指向一条链表，链表中的每个结点都存储了Hash值为该元素的索引的键值对。这种方法被称为“拉链法”，因此发生冲突的元素都被存储在一个链表中。
- 基本思想 这种方法的基本思想就是选择足够大的M，使得所有链表都尽可能短以保证高效的查找。查找分两步：首先根据Hash值找到对应的链表，然后沿着链表顺序查找对应的键。 当你能够预知所需要的符号表的大小时，该方法能够得到不错的性能。一种更可靠的方案是动态调整链表数组的大小，这样无论在符号表中有多少键值对都能保证链表较短。
- 基于拉链法的符号表（实现）
public class SeparateChainingHashST<Key, Value>
{
private int N; // number of key-value pairs
private int M; // hash table size
private SequentialSearchST<Key, Value>[] st; // array of ST objects
public SeparateChainingHashST()
{
this(997);
}
public SeparateChainingHashST(int M)
{
// Create M linked lists.
this.M = M;
st = (SequentialSearchST<Key, Value>[])new SequentialSearchST[M];
for (int i = 0; i < M; i++)
{
st[i] = new SequentialSearchST();
}
}
private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % M;
}
public Value get(Key key)
{
return (Value)st[hash(key)].get(key);
}
public void put(Key key, Value val)
{
st[hash(key)].put(key, val);
}
public Iterable<Key> keys() // See Exercise 3.4.19
}public class SequentialSearchST<Key, Value>
{
private Node first; // first node in the linked list
private class Node
{
// linked-list node
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next)
{
this.key = key;
this.val = val;
this.next = next;
}
}
public Value get(Key key)
{
// Search for key, return associated value.
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
{
return x.val; // search hit
}
}
return null; // search miss
}
public void put(Key key, Value val)
{
// Search for key. Update value if found; grow table if new.
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
{
x.val = val;
return; // Search hit : update val.
}
}
first = new Node(key, val, first); // Search miss: add new node.
}
}- 有序性相关的操作 Hash 最主要的目的在于均匀地将键散布开来，因此在计算 Hash 后键的顺序信息就丢失了。 对于需要快速找到最大或者最小的键，或是查找某个范围内的键，哈希表都不是合适的选择，因为这些操作的运行时间都将会是线性的。
② 线性探测法（linear probing）
- “开放地址”哈希表 实现哈希表的另一种方式就是用大小为 M 的数组保存 N 个键值对，其中 M > N。我们需要依靠数组中的空位解决碰撞冲突。基于这种策略的所有方法被统称为“开放地址”哈希表
- 线性探测法（“开放地址”哈希表的一种实现方式） 开放地址哈希表中最简单的方法叫做“线性探测”法：当碰撞发生时（当一个键的Hash值已经被另一个不同的键占用），我们直接检测哈希表中的下一个位置（将索引值加 1）。这样的线性探测可能会产生三种结果： a）命中，该位置的键和被查找的键相同； b）未命中，键为空（该位置没有键） c）继续查找，该位置的键和被查找的键不同。 我们用Hash函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不同则继续查找（将索引增大，到达数组结尾时折回数组的开头），直到找到该键或者遇到一个空元素。 我们习惯将检查一个数组位置是否含有被查找的键的操作称作探测。在这里它可以等价于我们一直使用的比较，不过有些探测实际上是在测试键是否为空。
- 核心思想 “开放地址”哈希表的核心思想是与其将内存用于链表，不如将它们作为哈希表的空元素。这些空元素可以作为查找结束的标志。
- 基于线性探测的符号表（实现）
public class LinearProbingHashST<Key, Value>
{
private int N; // number of key-value pairs in the table
private int M = 16; // size of linear-probing table
private Key[] keys; // the keys
private Value[] vals; // the values
public LinearProbingHashST()
{
keys = (Key[])new Object[M];
vals = (Value[])new Object[M];
}
private int hash(Key key)
{
return (key.hashCode() & 0x7fffffff) % M;
}
private void resize() // see page 474
public void put(Key key, Value val)
{
if (N >= M/2)
{
resize(2*M); // double M (see text)
}
int i;
for (i = hash(key); keys[i] != null; i = (i+1) % M)
{
if (keys[i].equals(key))
{
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
N++;
}
public Value get(Key key)
{
for (int i = hash(key); keys[i] != null; i = (i+1) % M)
{
if (keys[i].equals(key))
{
return vals[i];
}
}
return null;
}
}要查找一个键，我们从它的Hash值开始顺序查找，如果找到则命中，如果遇到空元素则未命中。
- 删除操作 如何从基于线性探测的哈希表中删除一个键？仔细想一想，你会发现直接将该键所在的位置设为null是不行的，因为这会使得在此位置之后的元素无法被查找。 因此，我们需要将簇中被删除键的右侧的所有键重新插入哈希表。
public void delete(Key key)
{
if (!contains(key))
{
return;
}
int i = hash(key);
while (!key.equals(keys[i]))
{
i = (i+1) % M;
}
keys[i] = null;
vals[i] = null;
i = (i+1) % M;
while (keys[i] != null)
{
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i+1) % M;
}
N--;
if (N > 0 && N == M/8)
{
resize(M/2);
}
}- 键簇 线性探测的平均成本取决于元素在插入数组后聚集成的一组连续的条目，也叫做键簇。 如图?所示，例如，在示例中插入键 C 会产生一个长度为 3 的键簇（ A C S ）。这意味着插入 H 需要探测 4 次，因为 H 的Hash值为该键簇的第一个位置。
显然，短小的键簇才能保证较高的效率。随着插入的键越来越多，这个要求很难满足，较长的键簇也会越来越多。另外因为（基于均匀性假设）数组的每个位置都有相同的可能性被插入一个新键，长键簇被选中的可能被短键簇更大，同时因为新键的Hash值无论落在簇中的任何位置都会使簇的长度加 1（甚至更多，如果这个簇和相邻的簇之间只有一个空元素相隔的话）
- 线性探测法的性能分析 开放地址哈希表的性能依赖于 α = N/M 的比值。我们将 α 称为哈希表的使用率。对于基于拉链法的哈希表，α 是每条拉链表的长度，因此一般大于 1 ；对于基于线性探测的哈希表，α 是表中已被占用的空间的比例，它是不可能大于 1 的。事实上，在 LinearProbingHashST 中我们不允许 α 达到 1 （列表被占满），因为此时未命中的查找会导致无限循环（因为，在元素不存在的情况下，空元素作为查找结束的标志）。为了保证性能，我们会动态调整数组的大小来保证使用率在 1/8 到 1/2 之间。
假设J（均匀哈希假设）。我们使用的Hash函数能够均匀并独立地将所有的键散布于 0 到 M-1 之间。 讨论。我们在实现Hash函数时随意指定了很多参数，这显然无法实现一个能够在数学意义上均匀并独立地散布所有键的Hash函数。事实上，深入的理论研究报告告诉我们想要找到一个计算简单但又拥有一致性和均匀性的Hash函数是不太可能的。在实际应用中，和使用 Math.random() 生成随机数一样，大多数程序员都会满足于随机数生成器类的Hash函数。很少人会去检验独立性，而这个性质一般都不会满足。
命题 M ：在一张大小为 M 并含有 N = α * M 个键的基于线性探测的哈希表中，基于假设 J ，命中和未命中的查找所需的探测次数分别为：
特别是当 α 约为 1/2 时，查找命中所需要的探测次数约为 3/2，未命中所需要的约为 5/2。当 α 趋于 1 时，这些估计值的精确度会下降，但不需要担心这些情况，因为我们会保证哈希表的使用率小于 1/2。 当哈希表快满的时候查找所需的探测次数是巨大的（α 越趋近于1，由公式可知探测的次数也越来越大），但当使用率 α 小于 1/2 时探测的预计次数只在 1.5 到 2.5 之间。
参考：
Multiplication Method Fibonacci Hashing 《算法 第4版》