散列为一种用于以常数平均时间执行插入,删除和查找的技术。一般的实现方法是使通过数据的关键字可以计算出该数据所在散列中的位置,类似于Python中的字典。关于散列需要解决以下问题:
散列函数为关键字->索引的函数,常用的关键字为字符串,则需要一个字符串->整数的映射关系,常见的三种散列函数为:
// 累加
func (n *node) hashSum() int {
hash := 0
for i := range n.key {
hash += int(n.key[i])
}
return hash
}
// 前三个字符和
func (n *node) hashTop3() int {
hash := 0
time := utf8.RuneCountInString(n.key)
if time > 3 {
time = 3
}
for i := 0; i < time; i++ {
hash += int(n.key[i])
}
return hash
}
// 所有字符和取余
func (n *node) hashMod(lenght int) int {
hash := 0
for i := range n.key {
hash += int(n.key[i]) * 32
}
return hash % lenght
}
当不同关键字计算出的散列值相同时,发生冲突,本次使用分离链接法解决:
type nodeData struct {
data int
}
type node struct {
key string
hash int
data nodeData
next *node
}
func (n *node) HashCompute(lenght int) {
n.hash = n.hashMod(lenght)
// fmt.Println("key:", n.key, "hash:", n.hash)
}
func newNode(data nodeData, key string) *node {
temp := &node{key, 0, data, nil}
return temp
}
type hashTable struct {
table [17]node
}
func (h *hashTable) insert(data nodeData, key string) {
temp := newNode(data, key)
temp.HashCompute(len(h.table))
temp.next = h.table[temp.hash].next
h.table[temp.hash].next = temp
}
func (h *hashTable) visit(key string) (nodeData, error) {
temp := newNode(nodeData{}, key)
temp.HashCompute(len(h.table))
//设计失误,仅有节点有计算散列值的方法,因此需要定义一个散列节点用于计算散列值
point := h.table[temp.hash].next
for point != nil {
if point.key == key {
return point.data, nil
}
point = point.next
} //遍历链表,搜索关键字
return temp.data, errors.New("not exsist")
// 失败退出
}
func newHashTable() *hashTable {
temp := &hashTable{}
for i := range temp.table {
temp.table[i] = *newNode(nodeData{}, "")
}
return temp
}
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有