hash表算法

ゝ一纸荒年。 2022-08-06 01:06 121阅读 0赞

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。把Key通过一个固定的算法函数既所谓的哈希函数转换成一个固定长度的字符串，然后就将该字符串转化为一个整数，用整数对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。

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

解答：

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

Hash，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。，hash就是找到一种数据内容和数据存放地址之间的映射关系。

哈希表的拉链法实现方法：建一个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

元素特征转变为数组下标的方法就是散列法。

1.除数散列法

index = value % n

2.平方散列法

index = (value \* value) >> 28

3.斐波那契散列法

index = (value \* k) >> m

找出一个理想的乘数k，而不是拿value本身当作乘数。

对于16位整数而言，这个乘数是40503  
对于32位整数而言，这个乘数是2654435769  
对于64位整数而言，这个乘数是11400714819323198485

最快的hash表算法

通过hash算法将一个长的字符串压缩成一个较短的字符串，并且发生碰撞的概率非常小，可以用较短的字符串“代替”原来较长的字符串进行运算。（单向hash函数）

times 33算法

times33的算法很简单，就是不断的乘33。nHash = nHash\*33 + \*key++;

经典times33算法如下：  
inline UINT CMyMap::HashKey(LPCTSTR key) const  
\{  
    UINT nHash = 0;  
    while (\*key)  
        nHash = (nHash<<5) + nHash + \*key++;  
    return nHash;  
\}

blizzard哈希算法

该算法可以认为是在times 33算法的改进。首先blizzard的这个hash算法的计算工作量也要比经典的times33算法大很多。但是blizzard算法让同一个字符串，可以根据dwHashType 的不同而计算出不同的独立的hash值。如果对于两个不同的字符串经过同一个hash函数得到的hash值有可能相同的话，但是用三个不同的hash函数得到的hash值依然相同的概率可以被证明为很低很低。

另外blizzard哈希算法的hash表的结构和不同的hash表的结构不同。blizzard算法本质上还是把数据放在hash bucket里面，也同样是在每个hash bucket里面有一个list队列。只不过一般的hash表，在找到hash bucket之后，就逐个的直接比较element；而blizzard的这个hash表，则是用“额外的两个hash值的比较”来代替element的直接比较。其中的一个用于确定位置，另外两个用于校验。

（blizzard算法使用三个hash值比较来替代字符串比较，不是为了降低时间复杂度，而是为了降低大规模字符串hash表的存储，所以这个算法不能说是“最快的”。）

所谓"One-way hash"其实就是不可逆hash，主要是用来加密用的，和速度快不快没什么关系。实际上"One-way hash"为了达到不可逆的目的，通常总是要更慢一些。

inline UINT CMyMap::HashKey(LPCTSTR key) const  
\{  
    int dwHashType = 1;  
    unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;  
    int ch;  
    while(\*key != 0)  
    \{  
        ch = toupper(\*key++);  
         
        //seed1 = cryptTable\[(dwHashType << 8) + ch\] ^ (seed1 + seed2);  
        seed1 = ((dwHashType << 8) + ch) ^ (seed1 + seed2);  
        seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;  
    \}  
    return seed1;  
\}

murmur哈希算法