Что такое 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;
- Данные хранятся отдельно от бакетов. Сами бакеты используются только как указатели (индексы) на данные. Выглядит это примерно так:
entries = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]
- Рядом с данными хранится полный хэш. Это позволяет не пересчитывать его при росте мапы.
- LoadFactor - 2/3 = ~66%
- При коллизиях используется стратегия сlosed addressing, но вместо массивов используется связный список. Также когда длина списка больше восьми он превращается в TreeMap. Это дает скорость поиска
вместо
как в случае со связным списком или массивом;
- Все ключи должны быть объектами. Для этого примитивные типы (boolean, int, char, float и т.д) должны быть сконвертированы в объекты через boxing;
- LoadFactor по умолчанию - 75%. При создании мапы можно указать свое значение параметра.
Кодирование
Реализуем базово 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 != topHash {
if b.tophash == emptyRest {
insertIdx = new(int)
*insertIdx = i
break
}
if insertIdx == nil && isCellEmpty(b.tophash) {
insertIdx = new(int)
*insertIdx = i
}
continue
}
// tophash значения не уникальны, по этому при совпадении проверяем дополнительно и сам ключ
if b.keys != key {
continue
}
b.values = value
return false
}
// проверяем overflow бакет.
if insertIdx == nil || b.overflow != 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 != topHash {
// константа означает что все следующие ячейки пустые -- выходим из цикла.
if b.tophash == emptyRest {
break
}
continue
}
if !isCellEmpty(b.tophash) && b.keys == key {
return b.values, 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 != topHash {
// если встречаем флаг все след. ячейки пустые, то просто выходим из функции
if b.tophash == emptyRest {
return false
}
continue
}
// дополнительно проверяем совпадение по ключу, т.к. tophash не уникальный
if b.keys == key {
b.tophash = 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
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]
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
Пока что такой бенчмарк не особо информативный, так как, очевидно, что результаты будут хуже. Интересно на сколько:
Увеличение элементов с 1000 до | Std map | Generic map | Разница |
10 000 | 83.43 ns/op | 104.9 ns/op | 1.25 |
100 000 | 90.62 ns/op | 344.7 ns/op | 3.8 |
1 000 000 | 168.7 ns/op | 8376 ns/op | 49.65 |
Hashmap(map) по версии Golang вместе с реализацией на дженериках
Привет. Сегодня рассмотрим такую интересную структуру данных как hashmap, а именно ее реализацию в Go. Вкратце разберем что такое hashmap, как это выглядит под капотом Go 1.19. Посмотрим отличия...
habr.com