iOS开发中的哈希表

之前粗略的写过一篇哈希存储，回头看看感觉有些过于粗略了，没有真正的从理论讲到应用，此次打算较完整的对哈希存储做一次学习笔记。

哈希表(hash table)又叫散列表，是一个数组，散列意为将元素均匀分散在数组的索引下。

为什么要使用哈希表

哈希表通常适用于键值存储结构中，在数组中，我们通常可以直接通过数字下标直接定位到要查找的元素，但在很多键值存储中，关键字并不会直接反映元素所在的位置，打一个不太贴切的比方，例如你要在公司100人的名单中找到自己的位置，只能从上往下遍历一遍核对名字，这当然非常慢，但如果人事告诉你，每个人的位置编号就在自己名字笔画数除以100的余数上或在那之后，是不是立刻就缩小了查找的范围？

这其中“每个人名字笔画数除以100的余数”便是哈希表的索引，我们称之为哈希值，而这个计算方法则叫做哈希算法或者哈希函数，哈希函数要尽可能满足以下三个特性，以使得哈希表的效率最优，即：

一致性：等价的键必然产生相等的哈希值
高效性：计算简便
均匀性：均匀的散列所有的键

算法的均匀性直接关系到查询的效率，上面的名字笔画算法只是我随口一编，它能保证一致性和高效性，但应该不满足均匀性，毕竟名字笔画相同的人应该会有不少，可能会出现索引扎堆。并且名单是连续的且是满的，而哈希表则始终会保留一半的空位，稍后会做详细的解释。

哈希算法

假设要存储的元素的总量为N，而哈希表容量为M，也就是说要将N个元素存储在0到M-1的索引下。

而将它们均匀分散的任务就交给了研究算法的专家了，不难想象这其中一定包含了艰深的数学证明，对于不同类型的元素，也已经有了一些常用的哈希算法对应，这里列举几个:

正整数：除留余数法

对于任意正整数k，其哈希值为 i = k % m 。其中M常常选择质数。

为什么选用质数这里可以简单的做一下说明，之后的哈希算法不做详细说明，现阶段个人认为没有必要深究，只做了解。

floor(): 向下取整;

由于  i = k % m = k - floor(k / m) * m ;

设k与m的公因数为g，即 k = a * g，m = b * g ;

那么 i = k - floor(a / b) * m;

在k与m确定的情况下, i的取值种数和 floor(a / b) 相关;

而不难看出floor(a / b)的范围在[0, a]之间，也就是说哈希值i会有a + 1种取值可能;

而 a = k / g, 为了让i的取值范围尽可能大，这里我们需要让g尽可能小;

由于质数的因子除了自身就是1，因此选用质数取余可以大概率的让哈希值的取值范围扩大。

(0, 1)的浮点数

round(): 四舍五入取整

对于浮点数k, 其哈希值i = round(k * M)

字符串：除留余数法

int hash = 0;
//R取一个不会造成溢出的较小素数即可
for (int i = 0, i < s.length, i ++){
    hash = (R * hash + s.charAt(i)) % M;
}

针对不同的数据类型，高级语言中已经封装好了相应的哈希值计算方法，例如在OC中，计算一个元素的哈希值可以这样调用

NSString *str = @"hash";
NSUInteger hashValue = [str hash];

哈希表的存储

首先假设将N个元素保存在容量M的哈希表中，令 α = N/M, α代表哈希表的使用率，又叫做负载因子。

α越大，哈希表越拥挤(负载高，紧凑)，查询效率越低，空间效率越高。

α越小，哈希表越稀疏(负载小，松散)，查询效率越高，空间效率越低。

为了使得查询时间尽可能短，则要使α尽可能小，即M尽可能大，但也要控制空间占用。

获得了索引，接下来就是存储的过程，假设一个空的哈希表的容量为100，现在计算出第一个元素的哈希值为5，那么直接将这个元素放在下标为5的位置即可，第二个元素的哈希值为8，以此类推，但也可能遇到索引位置已经有元素的情况，即不同元素的哈希值相等，一般称之为“碰撞”，对于碰撞的处理一般有两种方法。

拉链法

在碰撞元素的位置上建立一条链表，之后碰撞的所有元素都加入到这条链表的后面，查询时只需要遍历索引位置的链表即可。

在拉链法中，α也代表链表的平均长度，在哈希值分布均匀的前提下，由概率论知，链表长度在α以下的概率无限趋近于1（详请参考《算法第四版》）

线性探测法

继续遍历碰撞元素后的位置，找到第一个空位则插入，如果没有空位则回到数组头部继续遍历。查询时则从索引出开始向后遍历直到遇见空则证明没有这个元素。

这就要求哈希表不能被填满，否则加入新元素会陷入死循环。

在线性探测法中，M > N， α 经验证最好保持在0.5左右。