## 直接寻址表

class DirectAddressTable

def initialize
@table = []
end

def search(k)
@table[k]
end

def insert(x)
@table[x.key] = x
end

def delete(x)
@table[x.key] = nil
end

end


## 散列表

$$h:U\rightarrow \big\{0,1,...,m-1 \big\}$$

### 链接法

class ChainedHashTable

def initialize
@table = []
end

def insert(x)
if @table[x.key.hash]
@table[x.key.hash] << x
else
@table[x.key.hash] = [x]
end
end

def search(k)
@table[k.hash].each do |key|
if key == k
return k
end
end
end

def delete(x)
@table[x.key.hash].delete(x)
end

end


### 开放寻址法

$$h: U \times \big\{ 0,1,...,,-1 \big\} \rightarrow \big\{ 0,1,...,,-1 \big\}$$

$$\big \langle h(k,0),h(k,1),...,h(k,m-1) \big \rangle$$

class OpenAddressHashTable

def initialize(max)
@max = max
@table = []
end

def insert(k)
i = 0

until i == m
j = k.hash(i)
if @table[j] == nil
@table[j] = k
return j
else
i = i + 1
end
end

raise "Hash table overflow!"
end

def search(k)
i = 0

until @table[j] == nil || i == m
j = k.hash(i)
if @table[j] == nil
return j
end
i = i + 1
end

nil
end

end


## 散列函数

### 除法散列法

$$h(k)=k \mod m$$

### 乘法散列法

$$h(k) = \left \lceil{m(kA \mod 1)}\right \rceil$$

Knuth 认为

$$A \approx (\sqrt{5}-1)/2 = 0.618 033 988 7...$$