Graph看起來挺難的...得嘗試在十一月中前看完。
有錯請指教。
Def:
- hashing 雜湊
優點 (data不需sort、沒碰撞溢位只要O(1)、保密、data compression)
- hashing fcn
- uniform hashing fcn
- perfect hashing fcn
- hashing address, table
- bucket, slots
- collision, overflow
都沒有，只要O(1)
- identifier density, loading density
Thm:
- hashing用作sorting
利用類似bucket sort，data存入完再merge至各bucket內link list即可
H(X): 取最高位數值
overflow處理方法: chain，data輸入維持小到大排序
Method:
- hashing fcn design(H(X) design)
給定 一組input，求 一組hashing address
- middle square 平方值取中間位數
不取高位數、低位數的原因？
- mod M (division)
%M，好的M值有什麼性質？
- folding addition 折疊相加
- shift addtion
- boundary addtion(偶數反向)
- digits analysis 位數值分析
前提，知道所有identifier
- overflow處理方法，要知道各方法優劣
給定 一組hashing address，
求 hashing table(若已知bucket數, slot數)
求 idntifier比較次數
- linear probing
- quadratic probing 二次方探測
- (H(X) ±i^2) % B
- (H(X) + i^2) % B
where i = 1,...,(b-1)/2 or b/2
- double hashing 雙重雜湊
(H(X) + i*F(X)) % B
= (H(X) + i*(R-(X % R))) % B
where R:prime, i = 1,...
- chain 鏈結 (相同address放相同bucket，以link list串連)
若是uniform hashing fcn，可得bucket內chain上的data數
close addressing mode(其餘為open)
- link list
O(n)
- BST
O(n) ~ O(log n)
- AVL Tree or RB Tree
O(log n)
- rehashing