纸上谈兵: 哈希表 (hash table)

  • 时间:
  • 浏览:0

作者:Vamei 出处:http://www.cnblogs.com/vamei 欢迎转载,也请保留这段声明。谢谢!

HASH

哈希表(hash table)是从什么都有有集合A到什么都有有集合B的映射(mapping)。映射是三种生活对应关系,如果集合A的某个元素没能对应集合B中的什么都有有元素。但反过来,集合B中的什么都有有元素完后 对应多个集合A中的元素。完后 B中的元素没能对应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 11507

/* 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": 4150

亲戚亲戚亲戚亲戚朋友前会 建立什么都有有HASHSIZE大小的数组records,用于储存记录。HASHSIZE被选着为质数,以便hash值能更加均匀的分布。在搜索"Vamei"的记录时,前会 经过hash,得到hash值498,再直接读取records[498],就前会 读取记录了。

(666666是Obama的电话号码,111111是Vamei的电话号码。纯属杜撰,请勿当真)

hash搜索

完后 不采用hash,而什么都有有在什么都有有数组中搜索搞笑的话,亲戚亲戚亲戚亲戚朋友都要依次访问每个记录,直到找到目标记录,算法复杂性度为n。亲戚亲戚亲戚亲戚朋友前会 考虑一下为或多或少会有什么都有有的差别。数组着实前会 随机读取,但数组下标是随机的,它与元素值没能任何关系,什么都有有亲戚亲戚亲戚亲戚朋友要逐次访问各个元素。通过hash函数,亲戚亲戚亲戚亲戚朋友限定了每个下标位置完后 存储的元素。什么都有有,亲戚亲戚亲戚亲戚朋友利用键值和hash函数,就前会 具备相当的先验知识,来选着适当的下标进行搜索。在没能hash碰撞的前提下,亲戚亲戚亲戚亲戚朋友只都要选着一次,就前会 保证该下标指向的元素是亲戚亲戚亲戚亲戚朋友你前会 的元素。

冲突

hash函数都要防止hash冲突的或多或少的问题图片。比如,后边的hash函数中,"Obama"和"Oaamb"有相同的hash值,占据 冲突。亲戚亲戚亲戚亲戚朋友咋样防止呢?

什么都有有方案是将占据 冲突的记录用链表储存起来,让hash值指向该链表,这叫做open hashing:

open hashing

亲戚亲戚亲戚亲戚朋友在搜索的完后 ,先根据hash值找到链表,再根据key值遍历搜索链表,直到找到记录。亲戚亲戚亲戚亲戚朋友前会 用或多或少数据形态代替链表。

open hashing都要使用指针。亲戚亲戚亲戚亲戚朋友有完后 你前会 防止使用指针,以保持随机存储的优势,什么都有有采用closed hashing的最好的最好的办法来防止冲突。

closed hashing

或多或少情况汇报下,亲戚亲戚亲戚亲戚朋友将记录放满数组。当有冲突突然跳出的完后 ,亲戚亲戚亲戚亲戚朋友将冲突记录放满数组中依然闲置的位置,比如图中Obama被插入后,如果的Oaamb也被hash到4150位置。但完后 4150被占据 ,Oaamb探测到下什么都有有闲置位置(通过将hash值加1),并记录。

closed hashing的关键在咋样探测下什么都有有位置。后边是将hash值加1。但也前会 有其它的最好的最好的办法。概括的说,在第i次的完后 ,亲戚亲戚亲戚亲戚朋友应该探测POSITION(i)=(h(x) + f(i)) % HASHSIZE的位置。后边将hash值加1的最好的最好的办法,就合适 设定f(i) = 1当亲戚亲戚亲戚亲戚朋友在搜索的完后 ,就前会 利用POSITION(i),依次探测记录完后 突然跳出的位置,直到找到记录。

(f(i)的选着会带来不同的结果,这里不再深入)

完后 数组比较满,没能closed hashing都要进行或多或少次探测都前会 找到空位。什么都有有将大大减小插入和搜索的下行传输速率 。或多或少情况汇报下,都要增大HASHSIZE,并将什么都有有的记录放满到新的比较大的数组中。什么都有有的操作称为rehashing

总结

hash表,搜索

hash冲突, open hashing, closed hashing

欢迎继续阅读“纸上谈兵: 算法与数据形态”系列。