开放地址法

开放地址法是另一种（相对于分离链接法）解决散列冲突的方法。适用于装填因子（散列表中元素个数和散列表长度比）较小（小于0.5）的散列表。

开放地址法中索引的计算方法为，其中：

  • Hash(x)为索引的计算方法
  • F(i)为冲突的解决函数，有F(0) = 0，i为已经尝试计算索引的次数

F(i)一般有：

  • 线性探测法：，即每次冲突则向下寻找1个位置，直到找到不冲突的位置，容易产生“一次聚集”的现象（数据集中在某一个地址区域）
  • 平方探测法：，每次冲突按平方寻找下一个位置，直到找到不冲突的位置
  • 双散列：，即发生冲突后使用第二个散列函数计算下一个位置

代码实现

数据结构

结构体

1
2
3
4
5
6
7
8
9
10
11
// 节点数据
type tableData struct {
	data int
}

// 节点
type tableNode struct {
	flag bool		//是否已经插入数据，用于冲突检测
	key  string		//关键字
	data tableData	//节点数据
}

构造函数

1
2
3
func newTableNode(key string, data tableData) *tableNode {
	return &tableNode{false, key, data}
}

散列表

结构体

1
2
3
4
type hashTable struct {
	table  [17]tableNode
	length int
}

方法

计算散列值

1
2
3
4
5
6
7
func (h *hashTable) hashCompute(key string) int {
	hash := 0
	for i := range key {
		hash = hash + int(key[i])*32
	}
	return hash % h.length
}

插入方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
}

访问方法

1
2
3
4
5
6
7
8
9
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")
}

构造函数

1
2
3
4
5
6
7
8
func newHashTable() *hashTable {
	data := &hashTable{}
	data.length = 17
	for i := range data.table {
		data.table[i] = *newTableNode("", tableData{})
	}
	return data
}