哈希表

哈希表是一种字典，它支持 INSERT, SEARCH, DELETE

为什么要采用哈希表
1. 显然，需要字典的时候

它可以用于快速搜索，用空间换时间

比如查找字符串中有没有某个字母，如果顺序查找，则O(n)，采用哈希表，O(1)????

特别是要多次进行如上的查找工作，采用哈希表

2. 字典中词的个数远远大于应用中出现的个数

哈希表的要素

• m: 哈希表大小
• Collision resolution
• 哈希函数

哈希函数
采用除法：h(k) = k mod m . A prime not too close to an exact power of 2 is often a good choice for m.
采用乘法：h(k) = floor (m (kA mod 1)), m 的取值没有影响，一般取 2^p, p \in N

上面的哈希函数是为了算法上的有效，但没有考虑到安全。而密码哈希函数具有如下特性：
* it is easy to compute the hash value for any given message,
* it is infeasible to find a message that has a given hash,
* it is infeasible to modify a message without changing its hash,
* it is infeasible to find two different messages with the same hash.
很明显，采用除法和乘法的哈希函数不满足2，3，4

密码哈希函数的一个应用是获得 message digest