Hash
|---Hash function: ?Division,?Multiplication
|---Collision: ?Chaining,?Open addressing(Linear,Double hasing)
?
?
Symbol-table problem:
Table S holding n records
pointer --> key|satelite data (record)
?
?
?
Hashing:
Hash function h maps keys “randomly”?into slots of table T.
Problem: Collision.
When a record to be inserted maps to an already occupied slot, a collision occurs.
Resolving collisions by chaining.
Idea: link records in same slot into list.
?
?
?
Choosing a hash function:
--Should distribute keys uniformly into slot
--Regularity in key distributions should not affect uniformly.
?
?
除法不會考慮全部的數位，如10010，如果divisor是2的話，只和最后一位有關系。
除法比乘法的計算過程多循環，即除法比乘法慢。
上面更正：
A位于2的w-1次方至w次方之間。
?
?
?
