Go中哈希表数据结构的分析与实现
哈希表是哈希表数据结构的哈希实现。数据结构不使用自定义键将值存储在映射中,而是对键执行哈希函数以返回数组中项的确切索引。
执行
在内部,哈希表将用map
类型,我将揭露
Put()
Remove()
Get()
Size()
方法。
我将创建一个ValueHashtable
泛型类型,并发安全,可以生成包含任何类型的哈希表。密钥可以是任何类型,只要它实现Stringer
界面。通过运行go generate
该代码将创建特定于类型的哈希表实现,封装包含数据的实际特定于值的数据结构。
// Package hashtable creates a ValueHashtable data structure for the Item type
package hashtable
import (
“fmt”
“sync”
<span style="color:#e6db74">"github.com/cheekybits/genny/generic"</span>
)
// Key the key of the dictionary
type Key generic.Type
// Value the content of the dictionary
type Value generic.Type
// ValueHashtable the set of Items
type ValueHashtable struct {
items map[int]Value
lock sync.RWMutex
}
// the hash() private function uses the famous Horner’s method
// to generate a hash of a string with O(n) complexity
func hash(k Key) int {
key := fmt.Sprintf("%s", k)
h := 0
for i := 0; i < len(key); i++ {
h = 31*h + int(key[i])
}
return h
}
// Put item with value v and key k into the hashtable
func (ht *ValueHashtable) Put(k Key, v Value) {
ht.lock.Lock()
defer ht.lock.Unlock()
i := hash(k)
if ht.items == nil {
ht.items = make(map[int]Value)
}
ht.items[i] = v
}
// Remove item with key k from hashtable
func (ht *ValueHashtable) Remove(k Key) {
ht.lock.Lock()
defer ht.lock.Unlock()
i := hash(k)
delete(ht.items, i)
}
// Get item with key k from the hashtable
func (ht *ValueHashtable) Get(k Key) Value {
ht.lock.RLock()
defer ht.lock.RUnlock()
i := hash(k)
return ht.items[i]
}
// Size returns the number of the hashtable elements
func (ht *ValueHashtable) Size() int {
ht.lock.RLock()
defer ht.lock.RUnlock()
return len(ht.items)
}
测验
这些测试描述了上述实现的用法。请注意,我们从不与基础互动map
类型,如果只有Go尚未为我们提供地图类型,则也可以通过其他方式实现。
package hashtable
import (
“fmt”
“testing”
)
func populateHashtable(count int, start int) *ValueHashtable {
dict := ValueHashtable{}
for i := start; i < (start + count); i++ {
dict.Put(fmt.Sprintf(“key%d”, i), fmt.Sprintf(“value%d”, i))
}
return &dict
}
func TestPut(t *testing.T) {
dict := populateHashtable(3, 0)
if size := dict.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
dict.Put(“key1”, “value1”) //should not add a new one, just change the existing one
if size := dict.Size(); size != 3 {
t.Errorf(“wrong count, expected 3 and got %d”, size)
}
dict.Put(“key4”, “value4”) //should add it
if size := dict.Size(); size != 4 {
t.Errorf(“wrong count, expected 4 and got %d”, size)
}
}
func TestRemove(t *testing.T) {
dict := populateHashtable(3, 0)
dict.Remove(“key2”)
if size := dict.Size(); size != 2 {
t.Errorf(“wrong count, expected 2 and got %d”, size)
}
}
创建一个具体的哈希表数据结构
您可以使用以下通用实现来生成特定于类型的哈希表,方法是:
//generate a `IntHashtable` hash table of `int` values
genny -in hashtable.go -out hashtable-int.go gen "Value=int"
//generate a </span>StringHashtable<span style="color:#e6db74">
hash table of </span>string<span style="color:#e6db74">
values
genny -in hashtable.go -out hashtable-string.go gen “Value=string”
更多教程:
- 使用NGINX反向代理服务Go服务
- 在Go中复制结构
- Go Web服务器的基础
- 在Go中对地图类型进行排序
- 简而言之去指针
- 转到标签说明
- 开始日期和时间格式
- 使用Go进行JSON处理
- 可变参数函数
- 去弦备忘单
- 转到空界面说明
- 使用VS Code和Delve调试Go
- 命名为Go返回参数
- 在Go中生成随机数和字符串
- Go项目的文件系统结构
- Go中的二进制搜索算法
- 在Go中使用命令行标志
- GOPATH解释
- 使用Go构建一个命令行应用程序:lolcat
- 使用Go构建CLI命令:Cowsay
- 在Go中使用壳管
- Go CLI教程:财富克隆
- 使用Go列出文件夹中的文件
- 使用Go从GitHub获取存储库列表
- 去,将一小段字符串附加到文件中
- 去,将字符串转换为字节片
- 使用Go可视化您本地的Git贡献
- Go CPU和内存分析入门
- 解决Go程序中的“不支持索引”错误
- 测量Go程序中的执行时间
- 使用Go构建Web爬网程序以检测重复的标题
- 最佳实践:指针还是价值接收者?
- 最佳实践:您应该使用方法还是函数?
- Go数据结构:集
- 前往地图备忘单
- 在Go中生成泛型类型的实现
- Go数据结构:字典
- Go数据结构:哈希表
- 在“通过通道”中实现事件侦听器
- Go数据结构:堆栈
- Go数据结构:队列
- Go数据结构:二进制搜索树
- Go数据结构:图形
- Go数据结构:链表
- Go数据结构的完整指南
- 比较Go值
- Go是面向对象的吗?
- 在Go中使用SQL数据库
- 在Go中使用环境变量
- 上篇教程:PostgreSQL支持的REST API
- 在Go Web服务器上启用CORS
- 在Docker容器中部署Go应用程序
- 为什么Go是作为PHP开发人员学习的功能强大的语言
- 去,删除io.Reader.ReadString换行符
- 开始,如何观看更改并重建程序
- 去算一下自约会以来的月份
- 在Go中访问HTTP POST参数