了解哈希存储法

这里写的只是我个人对于哈希存储的简单理解，并没有特别详细的介绍，想要详细学习推荐阅读Robert Sedgewick的《算法第四版》。

什么是哈希(hash)存储法

简而言之，使用这种方法进行存储，我们可以非常快的找到数据的位置。

我们先来回忆一下查字典的过程。

比如说我们现在要通过读音查“正”字的释义。

如果要用从第一页开始向后遍历的方式去查找它，当然是可以找到的，但是这太慢了。

我们日常的做法是，翻到目录，我们知道“正”的读音是“zheng”,于是很快找到z的条目，然后只需要遍历z条目下的文字，很快就能找到“正”所在的位置。

哈希存储法利用的就是这种查字典的思想，我们将元素分布在一个个的索引（类似字典中的a到z）下，当我们要查找某个元素时，由于我们知道它的索引，因此只需要遍历索引下的元素就能快速找到它。

为了将这种经验应用在编程中，我们需要一个算法来计算出各种元素的索引。

那么应该按照什么样的标准来计算呢？

我们注意到在查字典时查z开头的字要比查b开头的要轻松很多。

原因是z开头的汉字明显少于b开头的。

查询时我们当然不希望出现查某些元素很快而查另一些元素却很慢的情况。

这拖慢了查询整体的平均时间，因此理想的情况是每个索引下的元素数目是均衡的。

专家们研究出了一种可以使计算出的每个索引下的元素数目是尽可能均衡的算法。

这就是哈希函数，hash的意思是“把…弄乱”，这里我们可以译作“散列”，这个过程是指将元素平均的分散到各个索引下，哈希是hash的音译。

上面提到的“索引”我们也称为“哈希值”。

哈希存储的过程分为两步：

下面我们就来简单了解。

对于不同类型的数据，例如正整数、浮点数、字符串、组合类型等等，计算它们的哈希值的算法是各不相同的。

具体的方法可以参考《算法第四版》，这里就不提了。

OC语言中可哈希的对象都可以通过发送hash消息或是get方法来获取它的哈希值。

NSNumber *num = @1;
NSUInteger i = num.hash;
i = [num hash];

计算出元素的索引值后，我们就可以将元素存储在数组相应的位置了。

比如，目前要存储的第一个元素A的哈希值是3，我们就把它放在数组下标为3的位置。

0	1	2	3	…
			A

第二个元素是B，它的哈希值是1，我们就放在1的位置。

0	1	2	3	…
	B		A

第三个元素是C，它的哈希值是3，这个时候问题就来了，3的位置上已经有了一个元素A，我们称之为碰撞，此时C应该如何存储呢？

通常我们有两种办法。

就像字典的目录所做的一样，我们让数组的每个元素都指向一个链表的头结点，这样一来每个元素都对应了一条链表，当一个哈希值对应多个元素时，这些元素都在一条链表上，我们只需要找到这条链表然后遍历它就能找到要查询的元素。

拉链法将哈希值对应的元素存储在了链表中，而线性探测法下，发生碰撞时我们继续从哈希值所在的位置出发遍历下一个位置，到达数组末尾时就返回数组开头，直到找到了没有被占用的位置，就将元素放置在这里，在查询时只需要从哈希值所在的位置出发向后做同样的遍历，直至遇到了要查询的元素或是空元素（证明没有这个元素）。

这里需要注意到的一个问题就是，在对拉链法实现的哈希表进行删除操作时，只需要做普通的链表删除节点操作就行了，但线性探测法却不能简单的将当前元素置空，因为这可能导致哈希值在这个位置及以前的元素无法查询，因此我们在置空当前元素后，还要将该位置后的所有元素重新插入哈希表。