本文简介

哈希函数和哈希表的实现

什么是哈希函数

• 哈希函数out = f(in)的特征
  • $f(in) -> \infty$
    • 它的输入域是无穷的，可以接受任意长度的字符串
    • 它的输出与域是有限的，$out -> S$，
      • MD5的返回值是 $[0, 2^{64}-1]$，长度为16的字符串，$16^{16} = 2^{64}$
      • 而SHa1是 $[0, 2^{128} - 1]$，长度为32的字符串
  • $Same(in) -> Same(out)$
    • 相同的输入一定返回相同输出值
    • 哈希函数没有任何随机的成分
  • $dif(in) -> Same(out)$
    • 哈希碰撞
    • 几率低：0.1s生成一个字符串，一辈子都碰撞不到
  • hash函数的均匀性和离散性
    • 1k个 $f(in)$ 在S域中映射出1k个点 $S_k$，
    • 可以把1k个输入均匀的离散到S域中
      • 离散性：即使输入$in$变化不大，out也会特别不一样,映射后的$out$不会有规律
      • 均匀性：固定面积的图像在S中框住的点是差不多的
    • 说明哈希函数的映射是没有规律的
      • 否则做不到均匀离散
      • 有规律势必在某个区域集中输出
• 哈希推论
  • $(in_1, in_2, …)$ –f–> $(out_1, out_2, …)$ –$%m$–> $(m_1, m_2, …)$
  • $(out_1, out_2,…)$保证在$S$域上均匀分布，则 $(m_1, m_2, …)$ 也能保证在[0, m-1]上均匀分布

假设文件中都是无符号整数，范围$[0, 2^{32}-1]$，有40亿个。只有1G内存，返回出现次数最多的数

经典方法可用hash表统计词频。但因为一个哈希表项key(int):value(int)是4+4=8字节，hash表内部还有索引空间，40亿个数最差情况(都不同)要40x8亿Byte=320亿B是32G空间

可以：$(a_1, a_2, a_{40y})$ –f–> $(b_1, b_2, b_{40y})$ –%100–> $(m_1, m_2, …, m_{40y})$，$a_n$ 根据$m_n$ 的值分配到不同的文件中，因为hash函数的性质，所以各文件中含不同数的数量基本上是差不多的，相同的数一定会发到同一个文件中，不同的数也会因为哈西函数的性质被均匀分布到100个文件中。 再对每个文件用哈西表来统计词频，这样每个文件用到的内存是32G/100 = 0.32G，每个文件都有一个词频最大的。

用hash函数在种类上均分，再用内存在每个种类中统计

hash表的实现

给一个17个元素的数组，给一个字符串”abc”， 字符串通过哈西函数得到一个输出$out_1$，再$out_1 %17 = 13%，把”abc”挂到a[13]上。

对于”bcd”： $f(“bcd”) -> out_2, out_2 % 17 = 14$，则”bcd”挂到a[14]

hash函数的性质可以保证数组中每一个元素所挂的字符串的个数是均匀的.

要查找的时候也可以通过哈西表计算出字符串所在的元素的下标,在去遍历。

同时统计每一个元素所挂的字符串的个数，当超过一个值的时候就要触发扩容操作。可就知道其他链的长度也是这个数了。 之后再把原来链表上的字符串再重新计算一遍，挂到34的数组中

• 扩容的代价
  • $hash(“abc”)$是$O(1)$的，注意是大常数
  • 遍历链表的代价是$O(k)$，如果链不长，可以认为是$O(1)$
  • 对于N个字符串，经历了$log{N}$次扩容
  • 每次扩容的代码是$O(N)$
  • 总的代价是$O(N \times log{N})$
  • 单次代价是$\frac{O(N \times log{N})}{N} = O(log{N})$，数组比较大，挂的链表长度比较小时，可以认为单次查找的代价是$O(1)$

题

设计RandomPool结构

• 设计一种结构，在该结构中有如下三个功能
  • insert(key)：将某个key加入到该结构中，做到不重复加入
  • delete(key)：将原本在结构中的某个key移除
  • getRandom()：等概率随机返回结构中的任何一个key
• 要求
  • insert、delete和getRandom方法的时间复杂度都是O(1)

通过两个hash表和size来实现这个功能：

map1(str->index), map2(index->str), size

map1.str	map1.index	-	map2.index	map2.str	size
“A”	0		0	“A”	1
“B”	1		1	“B”	2
“C”	2		2	“C”	3
…	…		…	…
“Z”	25		25	“Z”	26

每增加一个字符串，size++

返回随机key，可以用random(size)

delete(key)删除随机key，

• 用最后一个替代，比如删除map1中的”C”
  • map1(“C”) -> 2，用map1的index区域上的最后一条填它
  • map2(2) -> “C”, 用map2的index区域上的最后一条填它
  • size–
• 保证index区域上没有洞，是连续的

map1.str	map1.index	-	map2.index	map2.str	size
“A”	0		0	“A”	1
“B”	1		1	“B”	2
“C”->”Z”	2		2	“C”->”Z”	3
…	…		…	…
“Z”->del	25->del		25->del	“Z”->del	26–