关于哈希表

前言：（一般都是一些废话，可以不看）

        我一开始学习哈希表的时候真的觉得哈希表是一种很高大上的东西，然后我就对这种东西有一种莫名的害怕。最近突然想起之前朋友和我说起的哈希冲突又让我回忆起学习哈希表的时候。所以我就想写一篇关于哈希表的文章。

1. 什么是哈希表

        散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

        给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

——来自百度百科

        我初次查找哈希表的时候看到上面的解释就觉得哈希表很是高大上。因此我就觉得哈希表是一个非常难的数据结构。但是你完全可以简单地把哈希表理解成数组。其所谓的key值就是数组的下标，而哈希函数就是通过key值找到对应的数组下标。

        从上述描述中，我们可以提取出关于哈希表的关键信息：存储表、key值、哈希函数和映射。

        存储表：存储表用来存储信息。这里的信息包括key值和其对应的value。

        key值： 哈希表中表面上的唯一标识，其用来做为哈希函数的参数然后得到存储表中真正的唯一标识快速定位所需信息。

        哈希函数： 其以key值作为参数然后返回一个结果，这个结果就是存储表中真正的唯一标识。

        映射： 每一个key值对应一个value。

2. 一个简单哈希表思想的例子

        我们设定 ‘a’ = 1，'b' = 2, 'c' = 3, ...... , 'z' = 26。然后以下所给的数字转化为字母表示：123,1986。（所给的输入一定是数字且数字范围为1 - 9）

1
2
3
4
5
6
7
string input = Console.ReadLine();
char[] chars = input.ToCharArray();
for (int i = 0; i < chars.Length; i++)
{
    chars[i] = (char)(chars[i] - '1' + 'a');
}
Console.WriteLine(chars);

        你可能有些疑惑这怎么就用到了哈希表的思想呢？首先你要明白哈希表的目的就是为了快速查找值。而之前列出的关键信息都是为了这个目的而服务的。在上面的例子中我们可以找到关键信息的对应。

        存储表即字符的Ascii码，这个是系统自带的表。

        key值：所输入的数字字符。

        哈希函数即是输入的字符与字符1之间的差距。

        映射即一开始的设定

        你会发现就这样的简单例子就用到了哈希表的思想。  我们总是在不经意间就用到了哈希表的思想，但是我们却没有意识到。所以哈希表并不是什么很困难的数据结构。

3.关于哈希冲突

3.1什么是哈希冲突

        我们之前说哈希表会对key值进行一系列操作然后返回一个存储表中唯一标识。但是如果一个哈希函数是y = x % 5。你会发现10 和 5所得到的值会是一样的。也就是说这样的哈希是没办法分清10和5的区别。这就是哈希冲突。

3.2哈希冲突的解决方法

（1）扩大范围

        如果哈希函数是y = x % 10。那么这个函数就可以区分5和10。那么冲突自然就解决了。

（2）如果是单纯的查找某个值是否存在，则可以改变哈希表中值的数据结构让一个key对应多个值。