Golang 数据结构:哈希表

wuYinBlog · · 5149 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Golang 中链表的实现及常用操作,数据结构系列原文:flaviocopes.com,翻译已获作者授权。

概述

哈希表是和 map 类型的键值对存储方式不同(PHP 中的关联数组),它的哈希函数能根据 key 值计算出 key 在数组中的切确位置(索引)。

区别哈希表与 Golang 的 map、PHP 中的关联数组:

实现

常用操作

使用内置的 map 类型来实现哈希表,并实现以下常用操作:

1
2
3
4
Put()
Remove()
Get()
Size()

类似的,创建通用类型 ValueHashTable 来作为哈希表的结构类型,其中键值需实现 Stringer 接口。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
package hashtable

import (
"github.com/cheekybits/genny/generic"
"sync"
"fmt"
)

type Key generic.Type
type Value generic.Type

type ValueHashTable struct {
items map[int]Value
lock sync.RWMutex
}

// 使用霍纳规则在 O(n) 复杂度内生成 key 的哈希值
func hash(k Key) int {
key := fmt.Sprintf("%s", k)
hash := 0
for i := 0; i < len(key); i++ {
hash = 31*hash + int(key[i])
}
return hash
}

// 新增键值
func (ht *ValueHashTable) Put(k Key, v Value) {
ht.lock.Lock()
defer ht.lock.Unlock()
h := hash(k)
if ht.items == nil {
ht.items = make(map[int]Value)
}
ht.items[h] = v
}

// 删除键
func (ht *ValueHashTable) Remove(k Key) {
ht.lock.Lock()
defer ht.lock.Unlock()
h := hash(k)
delete(ht.items, h)
}

// 获取键的哈希值
func (ht *ValueHashTable) Get(k Key) Value {
ht.lock.RLock()
defer ht.lock.RUnlock()
h := hash(k)
return ht.items[h]
}

// 获取哈希表的大小
func (ht *ValueHashTable) Size() int {
ht.lock.RLock()
defer ht.lock.RUnlock()
return len(ht.items)
}

测试用例:hashtable_test.go


有疑问加站长微信联系(非本文作者)

本文来自:wuYinBlog

感谢作者:wuYinBlog

查看原文:Golang 数据结构:哈希表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

5149 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传