哈希表极其应用

亦凉 2021-05-12 11:51 551阅读 0赞

一、概念

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

1）哈希表存储的是键值对，其查找的时间复杂度与元素数量多少无关，哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接访问元素的，因此，哈希表查找的时间复杂度为O（1）。  
  
  
2）原理：  
          哈希表的做法其实很简单，就是把key通过一个固定的算法函数即所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。  
    而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位（时间复杂度为O（1））。  
  
  
3）缺点：  
• 数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重，所以程序虽必须要清楚表中将要存储多少数据。  
• 也没有一种简便的方法可以以任何一种顺序〔例如从小到大〕遍历表中数据项。

注：散列表是一个连续存储的区域，但不保证里面数据的连续性。

1、哈希函数  
  
  
哈希查找第一步就是使用哈希函数将键映射成索引。这种映射函数就是哈希函数。如果我们有一个大小为0-M的数组(散列表)，那么我们就需要一个能够将任意键转换为该数组范围内的索引（0~M-1）的哈希函数。哈希函数需要易于计算并且能够均匀分布所有键。  
  
  
实际情况下，我们的关键字(key)并不都是数字，有可能是字符串….所以，我们需要实现自己的哈希函数。  
  
  
2、常见的哈希函数  
1）直接寻址法(开放寻址法)：  
取关键字或者关键字的某个线性函数值作为哈希地址,即H(Key)=Key或者H(Key)=a\*Key+b(a,b为整数)  
  
  
2）除留余数法：  
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址.即H(Key)=Key MOD p,p<=m. 对p的选择很重要，一般取素数或m，若p选得不好，则很容易产生冲突。  
  
  
补充：将字符串作为键的时候，我们也可以将他作为一个大的整数，采用保留除余法。我们可以将组成字符串的每一个字符取值然后进行哈希，比如  
public int GetHashCode(string str)  
\{  
    char\[\] s = str.ToCharArray();  
    int hash = 0;  
    for (int i = 0; i < s.Length; i++)  
    \{  
        hash = s\[i\] + (31 \* hash);   
    \}  
    return hash;  
\}  
  
  
比如要获取”call”的哈希值，字符串c对应的unicode为99，a对应的unicode为97，L对应的unicode为108，所以字符串”call”的哈希值为 3045982 = 99·313 + 97·312 + 108·311 + 108·310 = 108 + 31· (108 + 31 · (97 + 31 · (99)))

二、哈希冲突：通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。（在创建、查找哈希表时都会遇到冲突）常见的解决冲突方法：

1、拉链法：将大小为M的数组的每一个元素指向一个条链表，链表中的每一个节点都存储散列值为该索引的键值对

![Center][]

图中，”JohnSmith”和”Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。

该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。对采用拉链法的哈希实现的查找分为两步，首先是根据散列值找到等一应的链表，然后沿着链表顺序找到相应的键。

2、线性探测法：线性探测法是开放寻址法解决哈希冲突的一种方法，基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。如下图所示：

![Center 1][]

对照前面的拉链法，在该图中，”TedBaker” 是有唯一的哈希值153的，但是由于153被”Sandra Dee”占用了。而原先”Snadra Dee”和”JohnSmith”的哈希值都是152的，但是在对”SandraDee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以存放在153上，然后”TedBaker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。

三、实例：

1、有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

最简单的方法就是遍历数组进行比较。但最合适的算法自然是使用HashTable（哈希表），通过某种算法，可以把一个字符串"压缩" 成一个整数(一个32位整数是无法对应回一个字符串的，所以会有冲突)，构造一个哈希表(Hash Table)来解决问题。哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod) 对应到数组中的一个位置。这样，只要比较这个字符串的哈希值对应的位置有没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)

2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

分析：题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是255Byte，很显然要占据2.375G内存，这个条件就不满足要求了。

题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query 255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

那么，我们的算法就有了：维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(n)的时间复杂度内完成了对该海量数据的处理。

[Center]: /images/20210511/2e71cfb29625476d922c620b3b81a88a.png
[Center 1]: /images/20210511/99f4484a62494b728830840a1c84bb38.png