前言
學爽了。
為什么哈希函數的空間復雜度是 O(N)
我們實際使用的電話號碼的數目是 N ，理論上至多有 R 個電話號碼，桶數組 bucket array 的容量是 M ，滿足條件 N < M < < R N<M<<R N<M<<R，因為動態擴容之類的原因，可以始終保證 N 和 M 是同階的，那么空間復雜度就是
O ( N + M ) = O ( N ) O(N+M)=O(N) O(N+M)=O(N)
hash 散列實例
maybe 取余之后 hash(key) 是不同的，那么皆大歡喜，假設取余之后相同呢，那就發生沖突了，collision .實際上類似于，我說我是六一兒童節這天生日，然后另一個人說我也是六一兒童節生日，然后我們兩的生日就沖突了。沖突了就需要處理沖突。或者這里我們可以認為是出現了同義詞。明明是不同的 key ，卻出現了相同的 hash(key), 然后我們映射的時候也是按照 hash(key) 去映射 value 的。一般的情況不同的 key 對應不同的 value, 當然也不是說不同的 key 不能對應相同的 value, 是說這里不行。一個電話號碼不能既是 A 的，又是 B 的。
裝填因子 load factor
l o a d f a c t o r : λ = N M load\ factor:\lambda=\frac N M load?factor:λ=MN?
怎么選 load factor 呢。非常糾結啊。到底有沒有標準答案。
單射 injection
完美散列，perfect hashing .不同的輸入一定對應不同的輸出，也就是唯一映射。這個我印象很深刻，實際上就是高數教材第一章的內容，我高考完的暑假試圖搞清楚一些東西，但是因為學的太仔細，然后也看不懂，然后也沒有正反饋，當時花了很大的力氣，學了第一章的內容，也沒學明白，所以對我個人來說最好是高頻率，多輪次，完成比完美更重要，不要在瑣碎的細節上面浪費過多的時間，先把主體框架搭建好。
目標
選擇沖突小的散列函數，散列就是 hash, 還有一個目標是處理沖突。
除余法
k e y % M key \% M key%M
散列表長一般就是 M ，現實中一般不是理想隨機。
規律
next token prediction 。下一詞元預測，實際上就是局部性。
除余法的缺陷
h a s h ( 0 ) ≡ 0 hash(0)\equiv0 hash(0)≡0
相鄰關鍵碼的散列地址必相鄰。
MAD 法
multiply add divide
h a s h ( k e y ) = ( a ? k e y + b ) % M hash(key)=(a*key+b)\%M hash(key)=(a?key+b)%M
散列的方法的要求
越是隨機，越是沒有規律越好。
偽隨機數法
h a s h ( k e y ) = r a n d ( k e y ) = [ r a n d ( 0 ) ? a k e y ] % M hash(key)=rand(key)=[rand(0)*a^{key}]\%M hash(key)=rand(key)=[rand(0)?akey]%M
r a n d ( 0 ) = ? rand(0)=? rand(0)=?
取決于偽隨機數發生器，因具體平臺，不同的歷史版本而異。
可移植性比較差。
就地隨機置亂
20 ! < 2 64 < 21 ! 20!<2^{64}<21! 20!<264<21!
hashcode
沖突難以杜絕，所以要解決沖突。發生沖突的時候要想辦法排解沖突。
最后
從今天開始，晚上十點半之后就不學習了，爭取晚上十一點就睡覺，早睡從我做起。。。
)
)
