专业课复习笔记 9

前言

学爽了。

为什么哈希函数的空间复杂度是 O(N)

我们实际使用的电话号码的数目是 N ，理论上至多有 R 个电话号码，桶数组 bucket array 的容量是 M ，满足条件 $$N<M<<R$$，因为动态扩容之类的原因，可以始终保证 N 和 M 是同阶的，那么空间复杂度就是
$$O(N+M)=O(N)$$

hash 散列实例

maybe 取余之后 hash(key) 是不同的，那么皆大欢喜，假设取余之后相同呢，那就发生冲突了，collision .实际上类似于，我说我是六一儿童节这天生日，然后另一个人说我也是六一儿童节生日，然后我们两的生日就冲突了。冲突了就需要处理冲突。或者这里我们可以认为是出现了同义词。明明是不同的 key ，却出现了相同的 hash(key), 然后我们映射的时候也是按照 hash(key) 去映射 value 的。一般的情况不同的 key 对应不同的 value, 当然也不是说不同的 key 不能对应相同的 value, 是说这里不行。一个电话号码不能既是 A 的，又是 B 的。

装填因子 load factor

$$loadfactor:\lambda =\frac{N}{M}$$
怎么选 load factor 呢。非常纠结啊。到底有没有标准答案。

单射 injection

完美散列，perfect hashing .不同的输入一定对应不同的输出，也就是唯一映射。这个我印象很深刻，实际上就是高数教材第一章的内容，我高考完的暑假试图搞清楚一些东西，但是因为学的太仔细，然后也看不懂，然后也没有正反馈，当时花了很大的力气，学了第一章的内容，也没学明白，所以对我个人来说最好是高频率，多轮次，完成比完美更重要，不要在琐碎的细节上面浪费过多的时间，先把主体框架搭建好。

目标

选择冲突小的散列函数，散列就是 hash, 还有一个目标是处理冲突。

除余法

$$key\%M$$

散列表长一般就是 M ，现实中一般不是理想随机。

规律

next token prediction 。下一词元预测，实际上就是局部性。

除余法的缺陷

$$hash(0)\equiv 0$$
相邻关键码的散列地址必相邻。

MAD 法

multiply add divide

$$hash(key)=(a\ast key+b)\%M$$

散列的方法的要求

越是随机，越是没有规律越好。

伪随机数法

$$hash(key)=rand(key)=[rand(0)\ast a^{key}]\%M$$
$$rand(0)=?$$
取决于伪随机数发生器，因具体平台，不同的历史版本而异。

可移植性比较差。

就地随机置乱

$$20!<2^{64}<21!$$

hashcode

冲突难以杜绝，所以要解决冲突。发生冲突的时候要想办法排解冲突。

最后

从今天开始，晚上十点半之后就不学习了，争取晚上十一点就睡觉，早睡从我做起。。。