14-1 哈希表基礎(chǔ)
知識點:
1 將 a-z 字幕的 ascii 碼出現(xiàn)次數(shù)映射到 0-25 的數(shù)組中 , 哈希函數(shù) f(char)=char-'a' O(1) , 鍵轉(zhuǎn)換為索引
2 26 個字幕和 1-30 學(xué)號這樣的哈希函數(shù)很容易能找到一一對應(yīng)的索引 , 但是身份證,字符串,浮點數(shù),日期卻不能 , 可能是多對一 , 因而產(chǎn)生哈希沖突
3 哈希表的設(shè)計思想: 空間換時間 , 假如1101819851216666 的身份證 , 可以開辟無限大的 99999999999999 的數(shù)組,則可以用 O(1)的時間執(zhí)行任意操作 , 假如只有 1 的空間, 則只能類似鏈表(線性表) , O(n)的時間操作
func firstUniqChar(s string) int {
/*
make a arr , map 0-25 as a-z
*/
arr:=[26]int{}
for _,v:=range s {
arr[v-'a']++
}
for k,v:=range s {
if arr[v-'a']==1 {
return k
}
}
return -1
}
14-2 哈希函數(shù)設(shè)計
知識點
1 哈希函數(shù) 得到的索引 分布越均勻越好
所有類型都轉(zhuǎn)換為整形的哈希函數(shù)設(shè)計:
2小范圍正整數(shù)直接用 , 負(fù)整數(shù)做偏移 -100~100 -> 0~200
3大整數(shù)的哈希函數(shù):取模 , 身份證號取后四位 = mod 10000 12343253255312056666 -> 6666 ,
4 mod1000000->056666 , 1205 是生日 , 05 部分取值為01~31 , 而哈?？臻g為 00~99 , 造成了分布不均勻
5 每個領(lǐng)域都有不同的哈希函數(shù)設(shè)計 , 很難找到通用的設(shè)計
6 對身份證號取模沒有利用所有信息( 信息摘要的概念? ) , 因此更容易產(chǎn)生沖突 , 信息越多越能接近唯一性 , 如用年月日區(qū)分 , 對比用省市區(qū)+年月日 , 更容易產(chǎn)生重復(fù)
7 模一個素數(shù) , 更有效利用一個數(shù)字的所有信息 , 數(shù)論
8 32浮點型在計算機(jī)中的表示 , 32 或 64 位的二進(jìn)制數(shù) , 32 位的情況,單精度 從左邊起 , 第一位是符號位 , 2-9 共 8 位是 exponent , 指數(shù)位 , 后面 23 位是 fraction 小數(shù)位
9 64 位浮點型的表示 , 第一符號位 , 2-12 , 11 位指數(shù)位 , 后面是 52 位的小數(shù)位
10 浮點型直接當(dāng)做整形 , 然后同上作哈希
11 字符串也轉(zhuǎn)成整型
12 166 也可以看成字符串 110^2 + 610^1 + 610^0
13 英文字母可以看成 26 進(jìn)制 , code=c26^4 + o*26^3 ...........
14 字符串特別長的時候可能計算很慢 , 可以做變形減少計算次數(shù)
15 字符串特別長并且使用的進(jìn)制特別大的時候可能產(chǎn)生溢出 , 可以把取模移到每一個里面
16 字符串哈希函數(shù)解決方案
17 復(fù)合類型 , 如類 , 將類中的屬性 , 如 Date { year,month,day} , 取出來同上面的字符串一樣取哈希
18 并不一定需要轉(zhuǎn)成整型處理 , 還有其他方法
19 哈希函數(shù)設(shè)計原則 , 一致性 a 的哈希值永遠(yuǎn)是同一個 , 高效性, 計算速度快 , 均勻 , 分布均勻
14-3 鏈地址法
知識點
1 取絕對值 和0x7ffffffff 進(jìn)行與操作 , 7 個 f = 7*4=28個 1 , 7 表示為 0111 ,
0111 ....11111 , 符號位取 0 為正數(shù)
2 元素為查找表 , 如鏈表 , 平衡樹 (PHP 的為鏈表,頭插法 , Java 里有一個HashMap是紅黑樹的實現(xiàn))
3 如何用 map 實現(xiàn) set ? 如何復(fù)用 hashmap 實現(xiàn) hashset , 用 map 的 key 存儲 set 的 value
4 HashSet HashMap 的區(qū)別?
5 數(shù)據(jù)量小鏈表比較快 , 大則紅黑樹比較快
