开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于0.5)的散列表。
开放地址法中索引的计算方法为$$h_{i}(x) = (Hash(X) + F(i)) % TableSize$$,其中:
F(i)一般有:
// 节点数据
type tableData struct {
data int
}
// 节点
type tableNode struct {
flag bool //是否已经插入数据,用于冲突检测
key string //关键字
data tableData //节点数据
}
func newTableNode(key string, data tableData) *tableNode {
return &tableNode{false, key, data}
}
type hashTable struct {
table [17]tableNode
length int
}
func (h *hashTable) hashCompute(key string) int {
hash := 0
for i := range key {
hash = hash + int(key[i])*32
}
return hash % h.length
}
func (h *hashTable) insert(key string, data tableData) error {
hash, i := h.hashCompute(key), 0
// 若发生冲突,则搜索下一个位置
for i = 0; h.table[(i+hash)%h.length].flag != false && h.table[(i+hash)%h.length].key != key; i++ {
if i == h.length {
// 若找不到,则表满,返回错误
return errors.New("table full")
}
}
hash = (i + hash) % h.length
// 插入数据
h.table[hash].data = data
h.table[hash].flag = true
h.table[hash].key = key
return nil
}
func (h *hashTable) visit(key string) (tableData, error) {
hash := h.hashCompute(key)
for index := 0; h.table[(index+hash)%h.length].flag == true; index++ {
if h.table[(index+hash)%h.length].key == key {
return h.table[(index+hash)%h.length].data, nil
}
}
return tableData{}, errors.New("not find")
}
func newHashTable() *hashTable {
data := &hashTable{}
data.length = 17
for i := range data.table {
data.table[i] = *newTableNode("", tableData{})
}
return data
}