作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!
HASH
哈希表(hash table)是从一个集合A到另一个集合B的映射(mapping)。映射是一种对应关系,而且集合A的某个元素只能对应集合B中的一个元素。但反过来,集合B中的一个元素可能对应多个集合A中的元素。如果B中的元素只能对应A中的一个元素,这样的映射被称为一一映射。这样的对应关系在现实生活中很常见,比如:
A -> B
人 -> 身份证号
日期 -> 星座
上面两个映射中,人 -> 身份证号是一一映射的关系。在哈希表中,上述对应过程称为hashing。A中元素a对应B中元素b,a被称为键值(key),b被称为a的hash值(hash value)。
韦小宝的hash值
映射在数学上相当于一个函数f(x):A->B。比如 f(x) = 3x + 2。哈希表的核心是一个哈希函数(hash function),这个函数规定了集合A中的元素如何对应到集合B中的元素。比如:
A: 三位整数 hash(x) = x % 10 B: 一位整数
104 4
876 6
192 2
上述对应中,哈希函数表示为hash(x) = x % 10。也就是说,给一个三位数,我们取它的最后一位作为该三位数的hash值。
哈希表在计算机科学中应用广泛。比如:
Ethernet中的FCS:参看小喇叭开始广播 (以太网与WiFi协议)
IP协议中的checksum:参看我尽力 (IP协议详解)
git中的hash值:参看版本管理三国志
上述应用中,我们用一个hash值来代表键值。比如在git中,文件内容为键值,并用SHA算法作为hash function,将文件内容对应为固定长度的字符串(hash值)。如果文件内容发生变化,那么所对应的字符串就会发生变化。git通过比较较短的hash值,就可以知道文件内容是否发生变动。
再比如计算机的登陆密码,一般是一串字符。然而,为了安全起见,计算机不会直接保存该字符串,而是保存该字符串的hash值(使用MD5、SHA或者其他算法作为hash函数)。当用户下次登陆的时候,输入密码字符串。如果该密码字符串的hash值与保存的hash值一致,那么就认为用户输入了正确的密码。这样,就算黑客闯入了数据库中的密码记录,他能看到的也只是密码的hash值。上面所使用的hash函数有很好的单向性:很难从hash值去推测键值。因此,黑客无法获知用户的密码。
(之前有报道多家网站用户密码泄露的时间,就是因为这些网站存储明文密码,而不是hash值,见多家网站卷入CSDN泄密事件 明文密码成争议焦点)
注意,hash只要求从A到B的对应为一个映射,它并没有限定该对应关系为一一映射。因此会有这样的可能:两个不同的键值对应同一个hash值。这种情况叫做hash碰撞(hash collision)。比如网络协议中的checksum就可能出现这种状况,即所要校验的内容与原文并不同,但与原文生成的checksum(hash值)相同。再比如,MD5算法常用来计算密码的hash值。已经有实验表明,MD5算法有可能发生碰撞,也就是不同的明文密码生成相同的hash值,这将给系统带来很大的安全漏洞。(参考hash collision)
HASH与搜索
hash表被广泛的用于搜索。设定集合A为搜索对象,集合B为存储位置,利用hash函数将搜索对象与存储位置对应起来。这样,我们就可以通过一次hash,将对象所在位置找到。一种常见的情形是,将集合B设定在数组下标。由于数组可以根据数组下标进行随机存取(random access,算法复杂度为1),所以搜索操作将取决于hash函数的复杂程度。
比如我们以人名(字符串)为键值,以数组下标为hash值。每个数组元素中存储有一个指针,指向记录 (有人名和电话号码)。
下面是一个简单的hash函数:
#define HASHSIZE 1007
/* By Vamei
* hash function
*/ int hash(char *p) { int value=0; while((*p) != '\0') { value = value + (int) (*p); // convert char to int, and sum p++; } return (value % HASHSIZE); // won's exceed HASHSIZE }
hash value of "Vamei": 498
hash value of "Obama": 480
我们可以建立一个HASHSIZE大小的数组records,