Структуры данных Go: хеш-таблица

Анализ и реализация структуры данных Hash Table в Go

Хеш-таблица - это хеш-реализация структуры данных хеш-таблицы. Вместо использования настраиваемого ключа для хранения значения на карте структура данных выполняет функцию хеширования для ключа, чтобы вернуть точный индекс элемента в массиве.

Выполнение

Внутри хеш-таблица будет представленаmapтипа, и я выставлю

  • Put()
  • Remove()
  • Get()
  • Size()

методы.

Я создамValueHashtableуниверсальный тип, безопасный для параллелизма, который может создавать хеш-таблицы, содержащие любой тип. Ключи могут быть любого типа, если они реализуютStringerинтерфейс. Запускаяgo generateкод создаст зависящую от типа реализацию Hash Table, инкапсулирующую фактическую зависящую от значения структуру данных, содержащую данные.

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

Тесты

Тесты описывают использование вышеупомянутой реализации. Обратите внимание, что мы никогда не взаимодействуем с базовымmaptype, который также можно было бы реализовать по-другому, если бы только 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: