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 }
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