《数据结构》学习-- Hash(1) --Hash简介

本系列是《数据结构与算法分析-C语言描述》（Data Structures and Algorithm Analysis in C，作者Mark Weiss）一书的学习笔记，当我在做cc150需要补某个知识点时，就会把这本书翻出来学习一下，同时分享~

如果你有任何问题和建议，希望能与我分享.

1. Hash Table（哈希表）的优缺点

优点：平均常数时间（constant average time）内完成插入、删除和寻找（insert，delete，find）操作。
缺点：任何顺序信息（order information）将不被有效记录，因此诸如findMax，findMin或者按顺序打印全表，都无法在线性时间内被完成。

2. Hash Table 概览

一个最简单的Hash Table例子就是一个（非常大的）数组。举例来说，如果我们知道输入数据是[0，999] 范围内的整数，那么我们只要创建一个长度为1000的int数组，那么对于插入一个数据（把相应数组位置置1），寻找一个数据（判断数组位置是否为1），删除一个数据（把数组位置置0），都非常容易。

3. Practical Hash Table

当然，实际上我们的输入数据可能范围非常大，以至于无法创建一个那么大的数组，或者输入数据不是整数而是字符串、浮点数或者用于自定义的类型。因此，直接映射、纯数组方式构成的Hash Table不能满足我们的所有需求。

3.1 Hash Table要素

要构成实用的Hash Table，有几大要素：

1. Hash表主体
   Hash表的主体一般是一个由和输入数据相同的数据结构构成的数组。如，输入数据是int，那么就是int数组，如输入数据是string，那么就是string数组。
2. Hash表大小
   一般来说，Hash表的大小应该是一个质数，且表的大小和填充内容的多少也有关。（在下一章中详细介绍）
3. Hash Function
   用来将输入数据映射到一个整数，从而找到应该放在Hash表中哪个位置。
4. 冲突解决方案（Collision Resolution）
   实际中，Hash的大小可能没有输入数据范围大，又因为Hash Function不可能保证所有输入数据都映射到不同的位置，因此两个不同的输入数据被分配到同一个Hash表位置是常有的事，如何解决这种冲突是非常非常重要的。（在下一章中详细介绍）
   
   

3.2 Hash Function

正如上面说的，Hash Function的作用是将输入数据映射到不同的Hash表位置。举例来说，如果Hash表大小为10，输入数据是正整数，那么我们可以将输入数据模10以后的结果作为Hash表位置，这样保证每个数据都存在一个对应的合法的位置。

3.2.1 Hash Function如何选择呢？

答案是不一定。具体情况具体分析。但有几个主要的参考要素：

1. 尽可能减少冲突。
   如果你的Hash表大小为10，输入数据都是10的倍数，那么用模10作为Hash Function显然非常愚蠢。
2. 尽可能均匀分布。
   如果你的Hash表大小为10000，输入数据范围是[0,100]，那么用模10000作为Hash Function显然非常愚蠢。

3.2.2 常用的Hash Function

1. 最常用的Hash Function就是数据模Hash表的大小。

2. 如果是字符串数据，一个常用的操作是
   $Position=sum_{i=0}^{DataSize-1}Data[DataSize-i-1]cdot32^i$

   具体在字符串中的实现是（假设data是输入字符串首字符）

   unsigned Position=0;
   while(*data!='')
   Position=(Position<<5) + *data++;
   return Position % TableSize;

   
   

4.总结

根据Gayle McDowell（Cracking the coding interview作者）所述，Hash表是在面试时最最常用的数据结构之一，因此必须牢固掌握。 以上是关于Hash Table最最基础的概念，还不足以让你编写出一个实际可用的Hash表。那么具体实现细节该怎么做呢？冲突解决方案有哪些经典方法呢？期待下一篇“《数据结构学习》–Hash(2)–Separate Chaining”吧！