Пишем хештейбл с дженериками

Перевод статьи “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 функцией хеширования), мы можем создать универсальную функцию хеширования для использования в нашем собственном коде!