Hash Table

一個hash table包含了兩個部分：
1.hash function
-->分為兩個階段：
a.hash code
由key去產生integer
b.compression function
integer -> [0, N-1]

-->目標：key散得越開越好

2.一個矩陣（or table）來儲存(key, data)

• Hash Codes
  1.快
  2.不要撞在一起
  -->Example

  a.integer cast  
  b.component sum  
  c.polynomial hash code  
  d.**Horner's rule**
  

• Compression Function
  a.Division method
  最常用的function
  h(y) = |y|/N
  -->N基本上為質數
  b.MAD
  h(y) = |ay + b|/N

• Collision Handling
  不同的key對應到相同的index
  1.Separate chaining
  要開新的link list
  2.Open addressing
  可以在原來的array裡做
  若發生collision，則往下找空的放
  a.**linear probing

    一直往下走，直到看到空的**  
  

  b.Double hashing

    用另外一個hash function來處理collision
  

• load factor
  α = n/N