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”


更多教程: