Go数据结构：哈希表

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”

Go数据结构：哈希表

Go中哈希表数据结构的分析与实现

执行

测验

创建一个具体的哈希表数据结构

更多教程：