
Реализация хеш таблицы на golang.
Достаточно частый вопрос на собеседования, как реализовать hash таблицу. Вопрос также может звучать следующим образом: "Что делать если в языке нет данной структуры данных, как реализовать?" и т.д. Ну и кроме того, всегда интересно разобраться, как же оно работает под капотом. И так, начнем с теории.
Теория
Хеш функция - функция, принимающая на вход данные произвольной длины, и отдающая данные фиксированной длины. В идеале также выходные значения должны быть близки к уникальному. Случай, когда выходное значение функции с разными входными аргументами выдает одинаковый результат называется коллизией.
В общем случае для реализации хештаблицы нам необходмо создать структуру данных, содержащую бакеты (список из элементов ключ-значение, для того чтобы разрешать коллизии). Индекс текущего элемента высчитывается в хеш функции (мы будем использовать простой xor, однако, в реальных системах эта функция реализуется сложнее)
Реализация
Определим структуру нашего хешмапа, будем хранить его размерность, а также список бакетов, каждый бакет в свою очередь будет слайсом, содержащим слайсы с структурой [ключ, значение].
type HashMap struct {
buckets [][][]string
size int
}
Реализуем функцию, находящую по ключу индекс, реализовывать будем через xor. Результат разделим на размер массива и возьмем целую часть.
func (h *HashMap) XORHash(src []byte) int {
index := 0
for _, c := range src {
index = index ^ int(c)
}
return index / h.size
}
Реализуем метод добавления, для этого расчитаем хеш сумму, затем, полученное ключ/значение, добавим в бакет по найденному индексу.
func (h *HashMap) Set(key string, value string) string {
index := h.XORHash([]byte(key))
insertedKeyVal := []string{key, value}
h.buckets[index] = append(h.buckets[index], insertedKeyVal)
return key
}
Для метода получения будем возвращать найденное значение, а также флаг, указывающий на то, было ли что-нибудь найденно. Для этого, получим индекс через XORHash функцию, реализованную ранее, и проитерируемся по бакету, содержащиму список из пар ключ/значение, при нахождении совпадения ключей, вернем результат с флагом 'найденно', в противном случае, установим флаг в false.
func (h *HashMap) Get(key string) (string, bool) {
index := h.XORHash([]byte(key))
if len(h.buckets[index]) == 0 {
return "", false
}
for _, kv := range h.buckets[index] {
if kv[0] == key {
return kv[1], true
}
}
return "", false
}
Метод удаления очень похож на метод получения, отличается лишь операция, делаем удаление элемента по индексу из бакета
func (h *HashMap) Del(key string) bool {
index := h.XORHash([]byte(key))
if len(h.buckets[index]) == 0 {
return false
}
for i, kv := range h.buckets[index] {
if kv[0] == key {
h.buckets[index] = append(h.buckets[index][:i], h.buckets[index][i+1:]...)
return true
}
}
return false
}
Результат, как и всегда, можно пощупать тут