Пишем хештейбл с дженериками
Перевод статьи “Go generics draft design: building a hashtable”.
В 2018 я реализовал игрушечную хеш таблицу для демонстрации работы хаш таблицы по капотом. В этой реализации ключами и значения были строки.
Через два года, в июне этого года, на официальном сайте появилась статья “The Next Step for Generics”, в которой рассказали про черновик дизайна дженериков, основанных на расширении существующих интерфейсов и новой концепции - контрактов. Я очень рекомендую изучить черновик нового дизайна. У меня нет экспертизы в этой теме и я могу говорить только исходя из собственного опыта.
В этой статье я расскажу о портировании свой хещ таблицы на дженерики. Если вы опытный пользователь и уже все умеете - можете пропустить введение и сразу перейти к коду хеш таблицы.
Хеш таблица без дженериков
Мой код мог работать только со ключами строками и значениями строками.
Тип Table
- основа всего пакета. Пара ключ/значение сохраняется в слайсе. Таблица разделена на бакеты. Количество бакетов определяется значением m
:
- Если задать
m
слишком маленьким, то бакетов будет не много. Но тогда будет очень много коллизий и поиск значений замедлится. - При большом
m
будет много бакетов, поиск по каждому ключу будет быстрым.
Тип kv
- небольшой хелпер для хранения строковых пар ключ/значение.
1// Package hashtable implements a basic hashtable for string key/value pairs.
2package hashtable
3
4// A Table is a basic hashtable.
5type Table struct {
6 m int
7 table [][]kv
8}
9
10// A kv stores key/value data in a Table.
11type kv struct {
12 Key, Value string
13}
14
15// New creates a Table with m internal buckets.
16func New(m int) *Table {
17 return &Table{
18 m: m,
19 table: make([][]kv, m),
20 }
21}
Хеш таблица поддерживает две операции:
Get
- возвращает значение, если ключ есть в таблице и булевое значение(true
- если ключ существует)Insert
- вставляет пару ключ/значение в хеш таблицу, перезаписывает значение, если оно там уже есть.
Оба этих метода используют функцию хеширования, которая принимает строку и возвращает целое число, которое определяет в какой бакет попадет значение.
1// hash picks a hashtable index to use to store a string with key s.
2func (t *Table) hash(s string) int {
3 h := fnv.New32()
4 h.Write([]byte(s))
5 return int(h.Sum32()) % t.m
6}
Я выбрал hash/fnv32
как простую не криптографическую хеш функцию, которая возвращает целое число. После вычисления хеша, получаем индекс бакета с помощью деления по модулю hash % t.m
Начнем с кода Go
:
1// Get determines if key is present in the hashtable, returning its value and
2// whether or not the key was found.
3func (t *Table) Get(key string) (string, bool) {
4 // Hash key to determine which bucket this key's value belongs in.
5 i := t.hash(key)
6
7 for j, kv := range t.table[i] {
8 if key == kv.Key {
9 // Found a match, return it!
10 return t.table[i][j].Value, true
11 }
12 }
13
14 // No match.
15 return "", false
16}
Первым делом вычисляем хеш ключа, переданного в параметре. Определяем бакет, который будет использоваться для сохранения ключа. Как только определяемся с бакетом - итерируемся по всем значениями в бакете и проверяем соответствие с нашим ключем.
Если ключ совпадает с одним из ключей в бакете, то возвращается значение и true
Если совпадение не найдено, то возвращается пустая строка и false
Теперь разберемся с Insert
:
1// Insert inserts a new key/value pair into the Table.
2func (t *Table) Insert(key, value string) {
3 i := t.hash(key)
4
5 for j, kv := range t.table[i] {
6 if key == kv.Key {
7 // Overwrite previous value for the same key.
8 t.table[i][j].Value = value
9 return
10 }
11 }
12
13 // Add a new value to the table.
14 t.table[i] = append(t.table[i], kv{
15 Key: key,
16 Value: value,
17 })
18}
Метод Insert
также использует ключ, чтобы определить какой бакет использовать и куда вставлять новую пару ключ/значение.
Перебирая пары ключ/значения в бакете, может оказаться, что ключ уже есть. В этом случае перезаписывается значение.
Если ключа нет, то новая пара добавляется в слайс.
На этом все. Это очень базовая хеш таблица которая работает со строками.
1// 8 buckets ought to be plenty.
2t := hashtable.New(8)
3t.Insert("foo", "bar")
4t.Insert("baz", "qux")
5
6v, ok := t.Get("foo")
7fmt.Printf("t.Get(%q) = (%q, %t)", "foo", v, ok)
8// t.Get("foo") = ("bar", true)
Теперь попробуем использовать дженерики для хеш таблицы
Хеш таблица на дженериках
Наша цель - переделать существующий код для работы с произвольными парами ключ значение. У нас одно ограничение: ключи в таблице должны соответствовать предопределенному ограничению comparable
, чтобы у нас была возможность проверить равенство.
1// Package hashtable implements a basic hashtable for generic key/value pairs.
2package hashtable
3
4// A Table is a basic generic hashtable.
5type Table(type K comparable, V interface{}) struct {
6 // hash is a function which can hash a key of type K with t.m.
7 hash func(key K, m int) int
8
9 m int
10 table [][]kv
11}
12
13// A kv stores generic key/value data in a Table.
14type kv(type K comparable, V interface{}) struct {
15 Key K
16 Value V
17}
18
19// New creates a table with m internal buckets which uses the specified hash
20// function for an input type K.
21func New(type K comparable, V interface{}) (m int, hash func(K, int) int) *Table(K, V) {
22 return &Table(K, V){
23 hash: hash,
24 m: m,
25 // Note the parentheses around "kv(K, V)"; these are required!
26 table: make([][](kv(K, V)), m),
27 }
28}
Для универсальных типов нужно использовать списки параметров типа. Каждый из этих типов и функций верхнего уровня должен иметь список параметров типа для K
и V
. Типы, которые будут использоваться для K
, должны соответствовать comparable
. Для V
может использоваться любой тип.
Я узнал несколько нюансов, пока писал этот код:
- Функция хеширования
func(K, int) int
теперь отдельный параметр конструктораNew
. Необходимо знать как хешировать разные типы. Я мог бы завести простой интерфейсHash() int
, но нужно чтобы код работал со стандартными типамиstring
иint
. - Я завис на создании пустого параметризированного слайса с помощью
make()
для поляTable.table
. Изначально я пытался сделать это такmake([][]kv(K, V))
. Оказалось, все не так просто.
Время для реализации Get
:
1// Get determines if key is present in the hashtable, returning its value and
2// whether or not the key was found.
3func (t *Table(K, V)) Get(key K) (V, bool) {
4 // Hash key to determine which bucket this key's value belongs in.
5 // Pass t.m so t.hash can perform the necessary operation "hash % t.m".
6 i := t.hash(key, t.m)
7
8 for j, kv := range t.table[i] {
9 if key == kv.Key {
10 // Found a match, return it!
11 return t.table[i][j].Value, true
12 }
13 }
14
15 // No match. The easiest way to return the zero-value for a generic type
16 // is to declare a temporary variable as follows.
17 var zero V
18 return zero, false
19}
Для метод обобщенного типа нужно указывать параметр типа в ресейвере. В нашем примере, метод Get
может принимать любой тип K
возвращает тип V
и bool
для индикации есть ли значение.
За исключением изменений в приемнике и нескольких обобщенных K
и V
, метод выглядит как обычный Go код, что радует.
Еще одна хитрость - обработка нулевых значений для обобщенных типов. По ссылке рекомендуется делать как в примере var zero V
. Возможно, в будущем этот момент станет проще. Я бы хотел что-то такое return _, false
, что будет работать и для обычного кода и для обобщенного.
Перейдем к методу Insert
1// Insert inserts a new key/value pair into the Table.
2func (t *Table(K, V)) Insert(key K, value V) {
3 i := t.hash(key, t.m)
4
5 for j, kv := range t.table[i] {
6 if key == kv.Key {
7 // Overwrite previous value for the same key.
8 t.table[i][j].Value = value
9 return
10 }
11 }
12
13 // Add a new value to the table.
14 t.table[i] = append(t.table[i], kv(K, V){
15 Key: key,
16 Value: value,
17 })
18}
Тут понадобилось совсем немного кода для обобщения этого метода.
- Ресейвер метода теперь
*Table(K, V)
вместо*Table
- Метод принимает
(key K, value V)
вместо(key, value string)
- Структура
kv{}
теперь определяется какkv(K, V){}
И на этом с переделкой все! Теперь у нас есть обобщенный тип хештаблицы, который может принимать любые ключи, которые соответствуют comparable
ограничениям.
Использование хештаблицы на дженериках
Для тестирования этого кода, я собираюсь две параллельные хештаблицы, которые взаимодействуют как индекс и обратный индекс между строковыми и числовыми типами.
1t1 := hashtable.New(string, int)(8, func(key string, m int) int {
2 h := fnv.New32()
3 h.Write([]byte(key))
4 return int(h.Sum32()) % m
5})
6
7t2 := hashtable.New(int, string)(8, func(key int, m int) int {
8 // Good enough!
9 return key % m
10})
В момент вызова конструктора New
определяем параметры типа для K
и V
. Для примера, t1
это Table(string, int)
, где K = string
and V = int
. t2
это реверс Table(int, string)
. Оба типа int
и string
соответствуют ограничению comparable
.
Чтобы хешировать наши обобщенные данные, необходимо реализовать функцию хеширования, которая работает с K
и t.m
и генерирует значения типа int
. Для t1
мы переиспользуем hash/fnv
из оригинального примера. Для t2
достаточно операции получения по модулю.
Я понимаю, что в большинстве случаев компилятор Go должен иметь возможность определять правильные типы для универсальных типов(K
и V
) при вызовах вида hashtable.New
, но я продолжу писать их явно, чтобы привыкнуть к такому дизайну.
Теперь у нас есть две таблицы - индекс и обратный индекс. Давайте их заполним:
1strs := []string{"foo", "bar", "baz"}
2for i, s := range strs {
3 t1.Insert(s, i)
4 t2.Insert(i, s)
5}
Каждая пара ключ/значение в таблице t1
имеет свое отражение значение/ключ в таблице t2
. Можем проитерироваться по строкам и их индексам для демонстрации нашего кода в действии.
1for i, s := range append(strs, "nope!") {
2 v1, ok1 := t1.Get(s)
3 log.Printf("t1.Get(%v) = (%v, %v)", s, v1, ok1)
4
5 v2, ok2 := t2.Get(i)
6 log.Printf("t2.Get(%v) = (%v, %v)\n\n", i, v2, ok2)
7}
Вывод демо программы:
t1.Get(foo) = (0, true)
t2.Get(0) = (foo, true)
t1.Get(bar) = (1, true)
t2.Get(1) = (bar, true)
t1.Get(baz) = (2, true)
t2.Get(2) = (baz, true)
t1.Get(nope!) = (0, false)
t2.Get(3) = (, false)
Готово, мы реализовали обобщенную хештаблицу.
Я хочу провести побольше экспериментов, чтобы лучше разбираться в новом функционале дженериков. Если вы хотите побольше узнать побольше - загляните в блог Go и новый черновик по дженерикам.
Если у вас есть вопросы или комментарии, можете найти меня в Twitter или Slack(@mdlayher). Иногда я делаю стримы по Go на Twitch.
Бонус: “дженерик” хеш функция
После реализации этой хештаблицы, у меня была интересная инструкция в канале #performance в Gophers Slack как во время выполнения получить доступ к “универсальной” функции хеширования, которая используется встроенными таблицами в Go.
@zeebo в Gophers Slack предложил это забавное, ужасающее, и блестящее решение:
1unc hash(type A comparable)(a A) uintptr {
2 var m interface{} = make(map[A]struct{})
3 hf := (*mh)(*(*unsafe.Pointer)(unsafe.Pointer(&m))).hf
4 return hf(unsafe.Pointer(&a), 0)
5}
6
7func main() {
8 fmt.Println(hash(0))
9 fmt.Println(hash(false))
10 fmt.Println(hash("why hello there"))
11}
12
13///////////////////////////
14/// stolen from runtime ///
15///////////////////////////
16
17// mh is an inlined combination of runtime._type and runtime.maptype.
18type mh struct {
19 _ uintptr
20 _ uintptr
21 _ uint32
22 _ uint8
23 _ uint8
24 _ uint8
25 _ uint8
26 _ func(unsafe.Pointer, unsafe.Pointer) bool
27 _ *byte
28 _ int32
29 _ int32
30 _ unsafe.Pointer
31 _ unsafe.Pointer
32 _ unsafe.Pointer
33 hf func(unsafe.Pointer, uintptr) uintptr
34}
Этот код использует факт, что интерфейс в Go, на самом деле, является кортежем из типа данных времени выполнения и указателем на тип. Получив доступ к этому указателю и используя unsafe
и приведения его к представлению мапы во время выполнения (которая имеет поле c функцией хеширования), мы можем создать универсальную функцию хеширования для использования в нашем собственном коде!