Hashmap по версии Golang вместе с реализацией на дженериках

Привет. Сегодня рассмотрим такую интересную структуру данных как hashmap, а именно ее реализацию в Go. Вкратце разберем что такое hashmap, как это выглядит под капотом Go 1.19. Посмотрим отличия реализации с Java и Python. Реализуем hashmap из-под капота с помощью дженериков.

Что такое hashmap

Для тех, кто еще не знаком с hashmap, прикладываю информацию из Википедии:
Hashmap — это структура данных, которая позволяет хранить пары ключ-значение. Ключи в hashmap уникальные. Можно представить как обычный массив, в котором для индекса можем использовать не только целые числа, но и, например, строки.

Сложность:

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

• Хэш-функция(Hash function). Под ней понимают функцию, которая принимает значение (ключ) неопределенного размера и возвращает значение фиксированной длины. В случае c Go она возвращает uint64. Одно из главных свойств — стабильность. Для одного и того же переданного значения она должна возвращать один и тот же результат;

• Бакет(Bucket/Slot). Так называемая структура данных, в которой хранятся ключи и значения в мапе. В некоторых реализациях hashmap в одном бакете хранится одно значение, а в других — несколько. Например, в Go данные внутри бакета хранятся в массиве, и в одном бакете может быть до восьми элементов;

• Коллизия (Collision). Так как хэш-функция не идеальна, передав в нее два разных значения мы можем получить один и тот же результат. В случае с бакетами нам нужно два разных значения положить в один и тот же бакет. Это называется коллизией. Для реализации hashmap необходимо иметь алгоритм их разрешения. Существует несколько таких алгоритмов (стратегий):

  • Closed addressing. Храним элементы с одинаковым хэшем с помощью дополнительных структур данных, таких как: связный список, двоичное дерево, массив и др. Используется в следующих языках: Go, Java, Scala;

  • Open addressing. В бакете хранится только одно значение. При возникновении коллизии выбирается следующий свободный бакет по какой-либо формуле. Такая стратегия используется в Python, Ruby, Rust, C++ и др;

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

• Фактор заполненности мапы (Overload factor). Это число (порог), превысив которое считается, что нужно увеличить количество бакетов (обычно вдвое) для сохранения константной скорости

Как hashmap реализована в Go

Рассмотрим по шагам упрощенный принцип работы hashmap. Для примера будем хранить оценки фильмов в формате название-оценка:

• Передаем ключ "The Matrix" в хэш-функцию. Получаем uint64 — 18002143618149980261;

• Вычисляем маску для наших бакетов. Она равна n-1, где n — количество бакетов. В примере 4 бакета, а маска равна 3;

• Вычисляем номер бакета, в котором сохраним наше значение. Для этого используем битовое «и»: hash & mask == 18002143618149980261 & 3 == 01 & 11(отбросили нули) = 01, что рано 1 в десятичной системе счисления;

• Идем в бакет по индексу 1 и перебором проверяем массив на наличие нашего ключа. Если находим совпадение по ключу, то перезаписываем значение, иначе добавляем в первое свободное место;

Под капотом структуры мапы и бакета выглядят так:
runtime/map.go

// A header for a Go map. type hmap struct { count     int // размер мапы. используется функцией len() flags     uint8 B         uint8  // log_2 количества бакетов. Для 8 бакетов B=3, для 16 B=4 и так далее. noverflow uint16 // примерное число переполненных бакетов hash0     uint32 // seed для хэш-функции, генерируется при создании мапы. нужен для рандомизации хэш-функции  buckets    unsafe.Pointer // ссылка на массив из 2^B бакетов; nil, если count==0 oldbuckets unsafe.Pointer // ссылка на массив предыдущих бакетов. в процессе роста мапы здесь будет массив старых бакетов, откуда потихоньку будут переноситься значения в новые бакеты. nevacuate  uintptr        // количество "эвакуированных" бакетов.  extra *mapextra // опциональные поля }  // A bucket for a Go map. type bmap struct { tophash [bucketCnt]uint8 // массив tophash // После массива tophash идет массив размера bucketCnt ключей и массив размера bucketCnt элементов. }

В структуре бакета явно не описаны поля ключей, значений и ссылка на overflow бакет. Для получения этих значений используется адресная арифметика через unsafe.Pointer.

Интересности реализации:

• В качестве ключа можно использовать любой тип данных для которого определена операция сравнения. Например, можно использовать структуру с тем же условием для всех ее полей;

• При отсутствии элемента возвращается нулевое значение для типа. Вторым параметром можно получить флаг наличия элемента по ключу;

• Нельзя получить адрес элемента. Потому что при росте мапы оно переедет в другой бакет и адрес у него, соответственно, поменяется;

• Мапа не безопасна для конкурентного использования. Для этого можно использовать обертку из sync.Map или мьютекс;

• Порядок итерации не сохраняется. При каждой новой итерации мапы последовательность возвращаемых элементов может отличаться. Под капотом каждый раз выбирается рандомный бакет, с которого начинается итерация. Для сохранения нужного порядка придется сохранять ключи в отдельном массиве и итерироваться по нему;

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

• При коллизиях используется стратегия сlosed addressing. Мы перебираем все ячейки бакета (их 8) и ищем первое свободное место;

• OverloadFactor равен 6.5 (~81% заполненности бакетов). Когда бакеты в среднем заполнены больше чем на 6.5 элементов, тригерится рост мапы, и все элементы перемещаются в новые бакеты, которых создается в два раза больше.

• При росте элементы переносятся в новые бакеты постепенно, а не все сразу;

Некоторые отличия от реализаций в других языках

Python 3.6+. Подробнее можно посмотреть в очень интересном (правда) докладе Raymond Hettinger Modern Python Dictionaries (2017)

• Сохраняется последовательность вставки;

• При коллизиях свободный бакет ищется с помощью стратегии open addressing. Для оптимизации поиска свободного бакета используются следующие формулы: j = ((5*j) + 1) mod 2**i и j = (5*j) + 1 + perturb;

• Данные хранятся отдельно от бакетов. Сами бакеты используются только как указатели (индексы) на данные. Выглядит это примерно так:

  indices =  [None, 1, None, None, None, 0, None, 2]   entries =  [[-9092791511155847987, 'timmy', 'red'],               [-8522787127447073495, 'barry', 'green'],               [-6480567542315338377, 'guido', 'blue']]

• Рядом с данными хранится полный хэш. Это позволяет не пересчитывать его при росте мапы.

• LoadFactor — 2/3 = ~66%

Java. Разбор можно почитать в статье Внутренняя работа HashMap в Java:

• При коллизиях используется стратегия сlosed addressing, но вместо массивов используется связный список. Также когда длина списка больше восьми он превращается в TreeMap. Это дает скорость поиска вместо как в случае со связным списком или массивом;

• Все ключи должны быть объектами. Для этого примитивные типы (boolean, int, char, float и т.д) должны быть сконвертированы в объекты через boxing;

• LoadFactor по умолчанию — 75%. При создании мапы можно указать свое значение параметра.

Также небольшое сравнение с реализациями Java и C++ можно посмотреть у Dave Cheney.

Кодирование

Реализуем базово hashmap из исходников Go 1.19. Не будем учитывать рост мапы, конкурентное обращение и возможность использовать разные типы для ключей.

Начнем с ведер

Определим структуру бакета.

Нам нужно два массива для ключей и значений, и ссылка на бакет для хранения дополнительных значений в случае переполнения текущего. Для оптимизации поиска храним массив первых восьми бит от хэша ключа, которые называются tophash.

const bucketSize = 8 // размер массивов внутри бакета  type bucket[T any] struct { tophash [bucketSize]uint8 // массив первых восьми бит от хэша ключа; некоторые значения используем как флаги, подробности ниже.  keys   [bucketSize]string // массив ключей values [bucketSize]T // массив значений  overflow *bucket[T] // ссылка на бакет в случае переполнения текущего }

Про tophash

В массиве с tophash мы резервируем несколько значений для дальнейшего использования. Ко всем значениям tophash, которые меньше minTopHash будем прибавлять его.

const ( emptyRest  = 0 // эта и все следующие ячейки с бОльшим индексом пустые emptyCell  = 1 // ячейка пустая minTopHash = 3 // минимальное значение tophash означающее что в ячейке есть значение )

По умолчанию, в Go массив заполнен нулевыми значениями, соответственно для tophash массива, который типа uint8, будут нули. При добавлении или получении элемента из бакета в первую очередь ориентируемся на массив tophash, а не массив ключей. Это позволяет оптимизировать поиск внутри бакета.

Добавляем элемент в мапу

Алгоритм добавления элемента:

• В цикле ищем совпадения по tophash и ключу или свободное место. Сохраняем данные и возвращаем соответствующий флаг для подсчета элементов в мапе.

• Если не нашли нужного места, то повторяем упражнения на overflow бакете.

// Добавляем значение в бакет. // Если переданные ключ уже присутствует в бакете, то значение перезапишется. // Если бакет переполнен, то значение сохраняется в бакете overflow. func (b *bucket[T]) Put(key string, topHash uint8, value T) (isAdded bool) { var insertIdx *int  for i := range b.tophash { // сравниваем tophash а не ключ, т.к. это позволяет нам использовать флаги и это работает быстрее if b.tophash[i] != topHash { if b.tophash[i] == emptyRest { insertIdx = new(int) *insertIdx = i break }  if insertIdx == nil && isCellEmpty(b.tophash[i]) { insertIdx = new(int) *insertIdx = i } continue }  // tophash значения не уникальны, по этому при совпадении проверяем дополнительно и сам ключ if b.keys[i] != key { continue }  b.values[i] = value return false }  // если индекс для вставки не определен, то проверяем overflow бакет if insertIdx == nil { if b.overflow == nil { b.overflow = &Bucket[T]{} }  return b.overflow.Put(key, topHash, value) }  // сохраняем ключ, значение и tophash b.keys[*insertIdx] = key b.values[*insertIdx] = value b.tophash[*insertIdx] = topHash  // возвращаем признак успеха. по нему калькулируем количество элементов в мапе. return true }  // проверяем что значение tophash <= чем зарезервированное значение для пустой ячейки func isCellEmpty(val uint8) bool { return val <= emptyCell } 

Получаем элемент

Алгоритм поиска элемента такой же как и в методе Put. Дополнительно возвращаем флаг наличия элемента в бакете.

func (b bucket[T]) Get(key string, topHash uint8) (T, bool) { for i := range b.tophash { if b.tophash[i] != topHash { // константа означает что все следующие ячейки пустые -- выходим из цикла. if b.tophash[i] == emptyRest { break } continue }  if !isCellEmpty(b.tophash[i]) && b.keys[i] == key { return b.values[i], true } }  // проверим бакет overflow if b.overflow != nil { return b.overflow.Get(key, topHash) }  return *new(T), false } 

Удаляем элемент

Вместо фактического удаления просто помечаем ячейку пустой.

// Delete - удаляет элемент по переданному ключу func (b *bucket[T]) Delete(key string, topHash uint8) (deleted bool) { for i := range b.tophash { if b.tophash[i] != topHash { // если встречаем флаг все след. ячейки пустые, то просто выходим из функции if b.tophash[i] == emptyRest { return false } continue }  // дополнительно проверяем совпадение по ключу, т.к. tophash не уникальный if b.keys[i] == key { b.tophash[i] = emptyCell return true } }  // проверяем overflow бакет if b.overflow != nil { return b.overflow.Delete(key, topHash) }  return false } 

Структура мапы

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

// hmap - структура мапы type hmap[T any] struct { len  int // количество реальных значений в мапе b    uint8 // log_2 от количества бакетов seed uint64 // начальный хэш  buckets []Bucket[T] // слайс бакетов }  // интерфейс hashmap, методы которого реализуем type Hashmap[T any] interface { Get(key string) T Get2(key string) (T, bool) Put(key string, value T) Delete(key string) Range(f func(k string, v T) bool) Len() int }

При инициализации генерируем seed и создаем нужное количество бакетов.

const ( // Максимальное среднее количество элементов в бакете которое тригерит рост мапы - 6.5 // Представлен как loadFactorNum/loadFactorDen, для того чтобы производить вычисления через int. loadFactorNum = 13 loadFactorDen = 2      ptrSize = 4 << (^uintptr(0) >> 63) // размер указателя. используется для вычисления tophash )  func New[T any](size int) Hashmap[T] { h := new(hmap[T])  h.seed = generateSeed()  // тот самый log_2 от количества элементов B := uint8(0) // увеличиваем B пока средняя заполненность бакетов > loadFactor  for overLoadFactor(size, B) { B++ } h.b = B  h.buckets = make([]bucket[T], bucketsNum(h.b))  return h }  // функция определяет будут ли бакеты, для size количества элементов, загружены больше чем loadFactor в среднем. // этой же функцией потом будем определять нужно ли начать рост мапы func overLoadFactor(size int, b uint8) bool { return size > bucketSize && uint64(size) > loadFactorNum*(bucketsNum(b)/loadFactorDen) }  // здесь b - log_2 от количества элементов func bucketsNum(b uint8) uint64 { return 1 << b }

Get/Set/Delete

Основную логику мы заложили в модели бакета. Остается только вычислить tophash и номер бакета. Для put/delete учитываем изменение количества хранимых элементов.

// Get - возвращает значение по ключу key // вернется нулевое значение типа <T> если по ключу key не существует значение. func (h hmap[T]) Get(key string) T { tophash, targetBucket := h.locateBucket(key)      v, _ := h.buckets[targetBucket].Get(key, tophash)     return v }  // Get2 - возвращает значение по ключу key и флаг наличия этого значения в мапе // вернет нулевое значение типа <T> и false если по ключу key не существует значения. func (h hmap[T]) Get2(key string) (T, bool) { tophash, targetBucket := h.locateBucket(key)      return h.buckets[targetBucket].Get(key, tophash) }  // Put - добавляет элемент в мапу func (h hmap[T]) Put(key string, value T) { tophash, targetBucket := h.locateBucket(key)  if h.buckets[targetBucket].Put(key, tophash, value) { h.len++ } }  // Delete - удаляем элемент из мапы по переданному ключу func (h hmap[T]) Delete(key string) { tophash, targetBucket := h.locateBucket(key) if h.buckets[targetBucket].Delete(key, tophash){ h.len-- } }

Вычисление номера бакета и tophash:

// locateBucket - возвращает индекс бакета и tophash func (h hmap[T]) locateBucket(key string) (tophash uint8, targetBucket uint64) { hash := hash(key, h.seed) tophash = topHash(hash) mask := bucketMask(h.b)  targetBucket = hash & mask  return tophash, targetBucket }  // возвращает первые 8 бит от значения func topHash(val uint64) uint8 { tophash := uint8(val >> (ptrSize*8 - 8)) if tophash < minTopHash { tophash += minTopHash } return tophash }  // bucketMask возвращает маску бакетов func bucketMask(b uint8) uint64 { return bucketsNum(b) - 1 }  // для хэширования используется алгоритм wyhash func hash(key string, seed uint64) uint64 { return wyhash.Hash([]byte(key), seed) }

Итерация

Итерацию сделаем через callback функцию. Вместо оператора break будем использовать флаг возвращаемый callback функцией. Для рандомизации последовательности значений при итерации будем так же начинать со случайного бакета.

// Range - итерация по всем значениям с вызовом переданной функции func (m hmap[T]) Range(f func(key string, value T) bool) { for i := range m.randRangeSequence() { bucket := &m.buckets[i] for bucket != nil { for j, th := range bucket.tophash { // идет к след. бакету если видим флаг о пустых ячейках после индекса j if th == emptyRest { continue } // если в ячейке есть значение, то передаем в функцию if th >= minTopHash { // прерываем итерацию если получили false if !f(bucket.keys[j], bucket.values[j]) { return } } } // проверяем overflow бакеты bucket = bucket.overflow } } }  // формируем последовательность индексов для начала поиска со случайного бакета. func (m hmap[T]) randRangeSequence() []int { i := rand.Intn(len(m.buckets))  seq := make([]int, 0, len(m.buckets)) for len(seq) != len(m.buckets) { seq = append(seq, i) i++ if i >= len(m.buckets) { i = 0 } }  return seq }

Тесты, бенчмарки

Исходники тестов можно посмотреть на Github. Ради интереса напишем бенчмарки для сравнения с мапой из коробки.
При сравнении методов Put и Get в пределах выделенной памяти разница достигает 20%:

var sizes = []int{128, 1024, 8192} func BenchmarkGet(b *testing.B) { for _, n := range sizes { // выделяем память под n элементов mm := New[int64](n) for i := 0; i < n; i++ { mm.Put(fmt.Sprintf("key__%d", i), int64(i)*2) }  b.Run(fmt.Sprintf("generic-map_%d", n), func(b *testing.B) { var got int64 j := 0 for i := 0; i < b.N; i++ { if j > n { j = 0 } got = mm.Get(fmt.Sprintf("key__%d", j)) j++ } _ = got }) } // такой же код для std мапы  }

go test . -run=^$ -bench . -benchmem goos: darwin goarch: arm64 pkg: github.com/w1kend/go-map BenchmarkGet/generic-map_128-8          12884936                85.63 ns/op            8 B/op          1 allocs/op BenchmarkGet/generic-map_1024-8         13559966                87.57 ns/op           14 B/op          1 allocs/op BenchmarkGet/generic-map_8192-8         11720404               101.1 ns/op            22 B/op          1 allocs/op BenchmarkGet/std-map_128-8              17141264                70.01 ns/op            8 B/op          1 allocs/op BenchmarkGet/std-map_1024-8             16442701                72.42 ns/op           14 B/op          1 allocs/op BenchmarkGet/std-map_8192-8             14521720                81.84 ns/op           22 B/op          1 allocs/op BenchmarkPut/generic-map_128-8          16028941                74.27 ns/op            8 B/op          1 allocs/op BenchmarkPut/generic-map_1024-8         15961150                75.22 ns/op           14 B/op          1 allocs/op BenchmarkPut/generic-map_8192-8         12941882                85.13 ns/op           22 B/op          1 allocs/op BenchmarkPut/std-map_128-8              16949132                70.37 ns/op            8 B/op          1 allocs/op BenchmarkPut/std-map_1024-8             16461930                71.99 ns/op           14 B/op          1 allocs/op BenchmarkPut/std-map_8192-8             14040560                82.28 ns/op           22 B/op          1 allocs/op

Переполнение мапы. Выделяем память на 1000 элементов и заполняем до 10 000, 100 000 и 1 000 000 элементов:

func BenchmarkPutWithOverflow(b *testing.B) { startSize := 1_000 targetSize := []int{10_000, 100_000, 1_000_000}  for _, n := range targetSize { mm := New[int64](startSize) b.Run(fmt.Sprintf("generic-map-with-overflow__%d", n), func(b *testing.B) { j := 0 for i := 0; i < b.N; i++ { if j > n { j = 0 } mm.Put(fmt.Sprintf("key__%d", j), int64(j)) j++ } }) }  for _, n := range targetSize { stdm := make(map[string]int64, startSize) b.Run(fmt.Sprintf("std-map-with-evacuation__%d", n), func(b *testing.B) { j := 0 for i := 0; i < b.N; i++ { if j > n { j = 0 } stdm[fmt.Sprintf("key__%d", j)] = int64(j) j++ } }) } }  

go test . -run=^$ -bench ^BenchmarkPutWithOverflow$ -benchmem goos: darwin goarch: arm64 pkg: github.com/w1kend/go-map BenchmarkPutWithOverflow/generic-map-with-overflow__10000-8             11472094               104.9 ns/op            23 B/op          1 allocs/op BenchmarkPutWithOverflow/generic-map-with-overflow__100000-8             3440781               344.7 ns/op            23 B/op          1 allocs/op BenchmarkPutWithOverflow/generic-map-with-overflow__1000000-8            1000000              8376 ns/op              57 B/op          3 allocs/op BenchmarkPutWithOverflow/std-map-with-evacuation__10000-8               14312827                83.43 ns/op           23 B/op          1 allocs/op BenchmarkPutWithOverflow/std-map-with-evacuation__100000-8              12691999                90.62 ns/op           23 B/op          1 allocs/op BenchmarkPutWithOverflow/std-map-with-evacuation__1000000-8              7283215               168.7 ns/op            23 B/op          1 allocs/op 

Пока что такой бенчмарк не особо информативный, так как, очевидно, что результаты будут хуже. Интересно на сколько:

---

На этом все, спасибо за внимание. Ставьте лайки, подписывайтесь на гитхаб.
В следующей части:

• Научим мапу расти;

• Замерим производительность при росте;

• Добавим дженерик ключи;

• Подумаем про конкурентное обращение.

И, наверное, стоит добавить что смысл данной статьи именно показать как hashmap реализована в Go под капотом, и показать более читаемый пример реализации на самом Go.

Ссылки

Исходники
Картинки гоферов
Гоферы от Ashley McNamara

Go:
GopherCon 2016: Keith Randall — Inside the Map Implementation
How the Go runtime implements maps efficiently (without generics)

Python:
Raymond Hettinger Modern Python Dictionaries A confluence of a dozen great ideas PyCon 2017 Raymond Hettinger. More compact dictionaries with faster iteration

Java:
Внутренняя работа HashMap в Java
The Java HashMap Under the Hood

Лекция cs166 stanford про Liner probing
An Analysis of Hash Map Implementations in Popular Languages