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