Truy cập cấu trúc dữ liệu: Từ điển

Phân tích và triển khai cấu trúc dữ liệu Từ điển trong Go

Một cửa hàng từ điển[key, value]cặp. Go cung cấp một cách triển khai từ điển rất thuận tiện nhờ tích hợp sẵn của nómapkiểu.

Trong bài viết này, tôi sẽ làm phong phú thêmmaploại cài sẵn với một số thao tác thuận tiện để lấy thông tin ra khỏi nó và thay đổi nội dung của nó.

Tôi sẽ tạo mộtItemDictionaryloại chung, an toàn đồng thời, có thể tạo từ điển cho bất kỳ loại nào. Bằng cách chạygennymã sẽ tạo ra một triển khai Từ điển theo kiểu cụ thể, đóng gói thực tếmapchứa dữ liệu.

Mục tiêu

Từ điển được tạo bằng cách sử dụngdict := ValueDictionary{}và cung cấp tập hợp các phương pháp đã xuất này:

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

Thực hiện

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

Kiểm tra

Các bài kiểm tra mô tả việc sử dụng triển khai trên. Lưu ý rằng chúng tôi không bao giờ tương tác vớimaploại, cũng có thể được triển khai theo cách khác nếu chỉ Go chưa cung cấp cho chúng tôi loại bản đồ.

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

Tạo cấu trúc dữ liệu từ điển cụ thể

Bạn có thể sử dụng cách viết chung chung này để tạo các từ điển dành riêng cho từng loại, bằng cách sử dụng

//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”


Các hướng dẫn về go khác: