Hash思想与hashTable

Hash就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。Hash算法没有一个固定的公式，只要符合Hash思想的算法都可以被称为是Hash算法

hash表

哈希表：数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系，可以根据这种关系快速查询

哈希算法是一种特殊的算法，能将任意数据散列后映射到有限的空间上，通常计算机软件中用作快速查找或加密使用。

哈希冲突：由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突。

解决哈希冲突的方法

解决哈希冲突的方法一般有：开放地址法、链地址法（拉链法）、再哈希法、建立公共溢出区等方法

开放地址法（open addressing）

从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。

在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。

线行探查法

线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。

平方探查法

平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空闲单元。
在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。

双散列函数探查法

这种方法使用两个散列函数hl和h2。其中hl和前面的h一样，以关键字为自变量，产生一个0至m—l之间的数作为散列地址；h2也以关键字为自变量，产生一个l至m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值l；对于平方探查法，探查序列的步长值是探查次数i的两倍减l；对于双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。

链地址法（拉链法） chaining

链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。

如下一组数字,(32、40、36、53、16、46、71、27、42、24、49、64)哈希表长度为13，哈希函数为H(key)=key%13,则链表法结果如下：

0       
1  -> 40 -> 27 -> 53 
2
3  -> 16 -> 42
4
5
6  -> 32 -> 71
7  -> 46
8
9
10 -> 36 -> 49
11 -> 24
12 -> 64

Java hashmap就是这么做的,在调用HashMap的put方法或get方法时，都会首先调用hashcode方法，去查找相关的key，当有冲突时，再调用equals方法.
JDK1.8对HashMap底层的实现进行了优化，例如引入红黑树的数据结构和扩容的优化等

再哈希法

就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。

建立公共溢出区

将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

OC中的Hash

NSHashTable & NSMapTable

对于NSSet，对象在存储时会被强引用，NSDicionary中值的存储也是一样，对健来说，在NSDictionary中会被拷贝

如果想存储弱引用的值，或者使用一个没有遵守<NSCopying>的对象作为key，可以使用NSValue +valueWithNonretainedObject或者，在iOS 6 上可以使用NSHashTable或NSMapTable分别对应NSSet 和 NSDictionary，是它们的通用版本。

NSHashTable
NSHashTable 是 NSSet 的通用版本，和 NSSet / NSMutableSet 不同的是，NSHashTable 具有下面这些特性：

NSSet / NSMutableSet 持有成员的强引用，通过 hash 和 isEqual: 方法来检测成员的散列值和相等性。
NSHashTable 是可变的，没有不可变的对应版本。
NSHashTable 可以持有成员的弱引用。
NSHashTable 可以在加入成员时进行 copy 操作。
NSHashTable 可以存储任意的指针，通过指针来进行相等性和散列检查。

NSMapTable

NSMapTable 是 NSDictionary 的通用版本。和 NSDictionary / NSMutableDictionary 不同的是，NSMapTable 具有下面这些特性：

NSDictionary / NSMutableDictionary 对键进行拷贝，对值持有强引用。
NSMapTable 是可变的，没有不可变的对应版本。
NSMapTable 可以持有键和值的弱引用，当键或者值当中的一个被释放时，整个这一项就会被移除掉。
NSMapTable 可以在加入成员时进行 copy 操作。
NSMapTable 可以存储任意的指针，通过指针来进行相等性和散列检查。

常见Hash的算法及应用

MD5,SHA1, SHA256

Hash算法广泛应用于 错误校正、语音识别、信息安全 中，其在信息安全的应用主要体现在以下几个方面：

文件校验

校验文件是否被篡改。
数字签名

由于非对称算法的运算速度较慢，所以在数字签名协议中，先对文件进行运算得到其Hash值（其Hash值又被称为【数字摘要】），然后对数字摘要进行数字签名，在统计上认为与对文件本身进行数字签名是等效的。
鉴权协议

鉴权协议又被称作挑战–认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

Hash算法加密的对象是文件的二进制内容，只要文件的二进制内容没发生改变，其Hash值不变。

参考

1.Hash与对称加密算法
2.解决哈希冲突的常用方法分析
3.深入探讨HashMap的底层结构、原理、扩容机制
4.NSHashTable & NSMapTable