Hashmap according to Golang along with implementation on generics

Hello. Today we will consider such an interesting data structure as hashmap, namely its implementation in Go. Let’s briefly analyze what a hashmap is, how it looks under the hood of Go 1.19. Let’s see the implementation differences with Java and Python. We implement hashmap from under the hood using generics.

What is hashmap

For those who are not yet familiar with hashmap, I am attaching information from Wikipedia:
Hashmap is a data structure that allows you to store key-value pairs. The keys in the hashmap are unique. It can be represented as a regular array, in which we can use not only integers for the index, but also, for example, strings.

Complexity:

Operation	Medium	Worst
Insert
Search
Removal
Memory

When deepening into the implementation of such a data structure, the following words can be found: hash function, collisions, buckets, fullness factor. Let’s figure out what they mean:

• Hash function. It is understood as a function that takes a value (key) of an indefinite size and returns a value of a fixed length. In the case of c Go, it returns uint64. One of the main properties is stability. For the same passed value, it must return the same result;

• Bucket(Bucket/Slot). The so-called data structure that stores keys and values ​​in a map. Some hashmap implementations store one value per bucket, while others store multiple values. For example, in Go, the data inside a bucket is stored in an array, and there can be up to eight elements in one bucket;

• Collision. Since the hash function is not perfect, by passing two different values ​​​​to it, we can get the same result. In the case of buckets, we need to put two different values ​​in the same bucket. This is called a collision. To implement a hashmap, you need to have an algorithm for resolving them. There are several such algorithms (strategies):

  • closed addressing. We store elements with the same hash using additional data structures, such as: linked list, binary tree, array, etc. Used in the following languages: Go, Java, Scala;

  • open addressing. Only one value is stored in a bucket. When a collision occurs, the next free bucket is selected according to some formula. This strategy is used in Python, Ruby, Rust, C++, and others;

  • perfect hashing. A hash function is chosen such that there will be no collisions. Selected for a static, pre-known set of keys.

• Overload factor. This is the number (threshold) above which it is considered necessary to increase the number of buckets (usually twice) to maintain a constant speed

How hashmap is implemented in Go

Let’s take a step-by-step simplified how hashmap works. For example, we will store movie ratings in the title-rating format:

• Passing the key "The Matrix" into a hash function. We get uint64 – 18002143618149980261;

• We calculate the mask for our buckets. She is equal n-1, where n is the number of buckets. In the example, there are 4 buckets, and the mask is 3;

• We calculate the number of the bucket in which we will store our value. To do this, we use the bit “and”: hash & mask == 18002143618149980261 & 3 == 01 & 11(discarded zeros) = 01which is early 1 in decimal;

• We go to the bucket at index 1 and brute force check the array for the presence of our key. If we find a match by key, then we overwrite the value, otherwise we add it to the first free space;

Under the hood, the map and bucket structures look like this:
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 элементов.
}

The bucket structure does not explicitly describe the fields of keys, values ​​and a link to the overflow bucket. To obtain these values, address arithmetic is used through unsafe.Pointer.

Implementation highlights:

• Any data type for which a comparison operation is defined can be used as a key. For example, you can use a structure with the same condition for all of its fields;

• If there is no element, null is returned for the type. The second parameter can be used to get the element presence flag by key;

• Cannot get element address. Because with the growth of the map, it will move to another bucket and its address will change accordingly;

• Mapa is not safe for competitive use. To do this, you can use the wrapper from sync.Map or a mutex;

• The iteration order is not preserved. With each new iteration of the map, the sequence of returned elements may differ. Under the hood, a random bucket is selected each time, from which the iteration begins. To preserve the desired order, you will have to store the keys in a separate array and iterate over it;

• Each time a map is created, a seed is generated to randomize the hash function. This is done for security, since knowing the hash function, you can pick up such keys that all values ​​will fall into one bucket and we will get a linear search speed;

• Collisions use the strategy closed addressing. We go through all the cells of the bucket (there are 8 of them) and look for the first free place;

• Overload Factor equals 6.5 (~81% full buckets). When buckets are more than 6.5 items full on average, map growth is triggered and all items are moved to new buckets, which are created twice as many.

• When growing, elements are transferred to new buckets gradually, and not all at once;

Some differences from implementations in other languages

Python 3.6+. More details can be found in a very interesting (true) report. Raymond Hettinger Modern Python Dictionaries (2017)

• The insertion sequence is preserved;

• In the event of collisions, a free bucket is searched using the open addressing strategy. To optimize the search for a free bucket are used the following formulas: j = ((5*j) + 1) mod 2**i and j = (5*j) + 1 + perturb;

• Data is stored separately from buckets. Buckets themselves are used only as pointers (indexes) to data. It looks something like this:

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

Java. You can read the analysis in the article The inner workings of HashMap in Java:

• Collisions use the strategy closed addressing, but a linked list is used instead of arrays. Also, when the list length is more than eight, it turns into a TreeMap. This gives the search speed instead of as in the case of a linked list or an array;

• All keys must be objects. To do this, primitive types (boolean, int, char, float, etc.) must be converted to objects via boxing;

• LoadFactor the default is 75%. When creating a map, you can specify your own parameter value.

Also, a small comparison with Java and C++ implementations can be found at Dave Cheney.

Coding

Implementing a basic hashmap from the Go 1.19 sources. We will not take into account the growth of the map, competitive circulation and the ability to use different types for keys.

Let’s start with buckets

Let’s define the bucket structure.

We need two arrays for keys and values, and a link to a bucket to store additional values ​​in case the current one overflows. To optimize the search, we store an array of the first eight bits of the hash of the key, which are called tophash.

const bucketSize = 8 // размер массивов внутри бакета

type bucket[T any] struct {
	tophash [bucketSize]uint8 // массив первых восьми бит от хэша ключа; некоторые значения используем как флаги, подробности ниже.

	keys   [bucketSize]string // массив ключей
	values [bucketSize]T // массив значений

	overflow *bucket[T] // ссылка на бакет в случае переполнения текущего
}

About tophash

In the tophash array, we reserve a few values ​​for later use. To all tophash values ​​less than minTopHash we will add it.

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

By default, in Go the array is filled with null values, respectively for the tophash array, which is like uint8, will be zeros. When adding or getting an element from a bucket, we first of all focus on the tophash array, and not the keys array. This allows you to optimize the search within the bucket.

Adding an element to the map

Algorithm for adding an element:

• In the loop, we look for matches by tophash and the key or free space. We save the data and return the appropriate flag to count the elements in the map.

• If you didn’t find the right place, then repeat the exercises on the overflow bucket.

// Добавляем значение в бакет.
// Если переданные ключ уже присутствует в бакете, то значение перезапишется.
// Если бакет переполнен, то значение сохраняется в бакете 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
}

Get the element

The element search algorithm is the same as in the method Put. Additionally, we return the flag of the presence of an element in the bucket.

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
}

Removing an element

Instead of actually deleting, we simply mark the cell empty.

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

Map structure

We store the size of the map, the number of buckets, the seed for the hash function, and the slice of the buckets themselves.

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

During initialization, we generate a seed and create the required number of buckets.

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

We put the main logic in the bucket model. It remains only to calculate tophash and the bucket number. For put/delete, we take into account the change in the number of stored elements.

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

Calculating the bucket number and 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)
}

Iteration

We will iterate through the callback function. Instead of an operator break we will use the flag returned by the callback function. To randomize the sequence of values ​​during iteration, we will also start with a random bucket.

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

Tests, benchmarks

Test sources can be found at Github. For the sake of interest, we will write benchmarks for comparison with the map out of the box.
When comparing methods Put and Get within the allocated memory, the difference reaches 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

Map overflow. We allocate memory for 1000 elements and fill up to 10,000, 100,000 and 1,000,000 elements:

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

So far, such a benchmark is not particularly informative, since, obviously, the results will be worse. I wonder how much