Go數據結構:字典

Go中Dictionary數據結構的分析與實現

詞典商店[key, value]對。 Go通過內置的字典提供了非常方便的字典實現map類型。

在本文中,我將豐富map內置類型,並通過一些方便的操作來獲取其中的信息並更改其內容。

我將創建一個ItemDictionary泛型類型,並發安全,可以為任何類型生成字典。通過運行genny該代碼將創建一個特定於類型的Dictionary實現,並封裝實際的map包含數據。

目標

該字典是使用以下方法創建的dict := ValueDictionary{}並提供以下導出方法集:

  • Set()
  • Delete()
  • Has()
  • Get()
  • Clear()
  • Size()
  • Keys()
  • Values()

執行

// Package dictionary creates a ValueDictionary data structure for the Item type
package dictionary

import ( “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

// ValueDictionary the set of Items type ValueDictionary struct { items map[Key]Value lock sync.RWMutex }

// Set adds a new item to the dictionary func (d *ValueDictionary) Set(k Key, v Value) { d.lock.Lock() defer d.lock.Unlock() if d.items == nil { d.items = make(map[Key]Value) } d.items[k] = v }

// Delete removes a value from the dictionary, given its key func (d *ValueDictionary) Delete(k Key) bool { d.lock.Lock() defer d.lock.Unlock() _, ok := d.items[k] if ok { delete(d.items, k) } return ok }

// Has returns true if the key exists in the dictionary func (d *ValueDictionary) Has(k Key) bool { d.lock.RLock() defer d.lock.RUnlock() _, ok := d.items[k] return ok }

// Get returns the value associated with the key func (d *ValueDictionary) Get(k Key) Value { d.lock.RLock() defer d.lock.RUnlock() return d.items[k] }

// Clear removes all the items from the dictionary func (d *ValueDictionary) Clear() { d.lock.Lock() defer d.lock.Unlock() d.items = make(map[Key]Value) }

// Size returns the amount of elements in the dictionary func (d *ValueDictionary) Size() int { d.lock.RLock() defer d.lock.RUnlock() return len(d.items) }

// Keys returns a slice of all the keys present func (d *ValueDictionary) Keys() []Key { d.lock.RLock() defer d.lock.RUnlock() keys := []Key{} for i := range d.items { keys = append(keys, i) } return keys }

// Values returns a slice of all the values present func (d *ValueDictionary) Values() []Value { d.lock.RLock() defer d.lock.RUnlock() values := []Value{} for i := range d.items { values = append(values, d.items[i]) } return values }

測驗

這些測試描述了上述實現的用法。請注意,我們從不與基礎互動map類型,如果只有Go尚未為我們提供地圖類型,則也可以通過其他方式實現。

package dictionary

import ( “fmt” “testing” )

func populateDictionary(count int, start int) *ValueDictionary { dict := ValueDictionary{} for i := start; i < (start + count); i++ { dict.Set(fmt.Sprintf(“key%d”, i), fmt.Sprintf(“value%d”, i)) } return &dict }

func TestSet(t *testing.T) { dict := populateDictionary(3, 0) if size := dict.Size(); size != 3 { t.Errorf(“wrong count, expected 3 and got %d”, size) } dict.Set(“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.Set(“key4”, “value4”) //should add it if size := dict.Size(); size != 4 { t.Errorf(“wrong count, expected 4 and got %d”, size) } }

func TestDelete(t *testing.T) { dict := populateDictionary(3, 0) dict.Delete(“key2”) if size := dict.Size(); size != 2 { t.Errorf(“wrong count, expected 2 and got %d”, size) } }

func TestClear(t *testing.T) { dict := populateDictionary(3, 0) dict.Clear() if size := dict.Size(); size != 0 { t.Errorf(“wrong count, expected 0 and got %d”, size) } }

func TestHas(t *testing.T) { dict := populateDictionary(3, 0) has := dict.Has(“key2”) if !has { t.Errorf(“expected key2 to be there”) } dict.Delete(“key2”) has = dict.Has(“key2”) if has { t.Errorf(“expected key2 to be removed”) } dict.Delete(“key1”) has = dict.Has(“key1”) if has { t.Errorf(“expected key1 to be removed”) } }

func TestKeys(t *testing.T) { dict := populateDictionary(3, 0) items := dict.Keys() if len(items) != 3 { t.Errorf(“wrong count, expected 3 and got %d”, len(items)) } dict = populateDictionary(520, 0) items = dict.Keys() if len(items) != 520 { t.Errorf(“wrong count, expected 520 and got %d”, len(items)) } }

func TestValues(t *testing.T) { dict := populateDictionary(3, 0) items := dict.Values() if len(items) != 3 { t.Errorf(“wrong count, expected 3 and got %d”, len(items)) } dict = populateDictionary(520, 0) items = dict.Values() if len(items) != 520 { t.Errorf(“wrong count, expected 520 and got %d”, len(items)) } }

func TestSize(t *testing.T) { dict := populateDictionary(3, 0) items := dict.Values() if len(items) != dict.Size() { t.Errorf(“wrong count, expected %d and got %d”, dict.Size(), len(items)) } dict = populateDictionary(0, 0) items = dict.Values() if len(items) != dict.Size() { t.Errorf(“wrong count, expected %d and got %d”, dict.Size(), len(items)) } dict = populateDictionary(10000, 0) items = dict.Values() if len(items) != dict.Size() { t.Errorf(“wrong count, expected %d and got %d”, dict.Size(), len(items)) } }

創建具體的字典數據結構

您可以使用以下通用實現來生成特定於類型的字典,方法是:

//generate a `IntDictionary` dictionary of `string` keys associated to `int` values
genny -in dictionary.go -out dictionary-string-int.go gen "Key=string Value=int"

//generate a </span>StringDictionary<span style="color:#e6db74"> dictionary of </span>string<span style="color:#e6db74"> keys associated to </span>string<span style="color:#e6db74"> values genny -in dictionary.go -out dictionary-string-string.go gen “Key=string Value=string”


更多教程: