Всем доброго времени суток. Для начинающего программиста (коим я и являюсь) реализация базовых структур данных, по типу бинарных деревьев и связных списков, довольно легка. Чего не скажешь о хэш картах. В этой статье мы и разберём пример её реализации.
Об устройстве хэш карты
В данном примере мы будем рассматривать хэш-карту на базе функции хеширования Пирсона. Данная функция имеет на выходе число типа uint8
, как следствие мы можем использовать 256 ячеек памяти для хранения результата на базе ключа. Однако есть такой недостаток хэш-функций как коллизии. Тут в дело вступают связные списки. Условимся, что наша структура хэш-карты будет иметь в себе массив длинною 256, а каждый из элементов будет являться связным списком.
Разберёмся на примере
Начнём с хэш-функции.
Краткими словами эта функция получающая на вход любое количество байт и возвращающая при этом 1 байт. Её реализация базируется на наборе инструкций (в данном случае сдвиг элемента на номер символа в таблицы ASCII), а так же на 256-байтной таблицы поиска, содержащей перестановку значений от 0 до 255.
var table[256]int = func()[256]int {
var data [256]int
rand.Seed(time.Now().Unix())
for index, _ := range(data) { data[index] = index }
for index, _ := range(data) {
rv := rand.Intn(256)
data[index], data[rv] = data[rv], data[index]
}
return data
}()
В начале мы создаём массив из 256 элементов, каждый из которых имеет значение, равное своему индексу, а затем перемешиваем эти элементы в рандомном порядке.
func hash8(message string) int {
// using global table
var hash int = len(message)%256
for _, value := range(message) {
hash = table[(hash + int(value))%256]
}
return hash
}
А вот и реализация алгоритма :)
Рассмотрим её поподробнее. Получая на вход строку, мы декларируем переменную hash
равную (длина строки) mod 256
, она же и будет служить результатом хэш-функции. Далее итерируя по строке мы присваиваем hash
значение равное значение элемента таблицы поиска по индексу (hash + номер в ASCII) mod 256
.
Разобравшись с хэш-функцией рассмотрим реализацию самой хэш-карты.
type Node struct {
key string
value string
next *Node
}
type List struct {
head *Node
}
type Map struct {
map_list [256]*List
len int64
}
Как и писалось выше хэш-карта базируется на массиве длинною 256 элементов. Каждый элемент это начало/голова связного списка List
, состоящего из узлов Node
, которые в свою очередь имеют переменные ключ key
и значение value
. Помимо того Map
имеет переменную len
, которая нужна для подсчёта длины карты.
Теперь перейдём к методам. Для начала надо реализовать метода работы связного списка:
1. Вставка элемента
2. Удаление элемента
3. Вывод элементов (в частность ключей)
Спойлер
Ниже мы не будем детально рассматривать реализацию методов связного списка...
Об это как-нибудь будет пост.
func (l *List) add(key, val string, m *Map) {
new_data := &Node{value: val, key: key}
if l.head == nil {
l.head = new_data
m.len++
} else {
current := l.head
for current.next != nil {
if key == current.key {
current.value = val
return
}
current = current.next
}
if key == current.key {
current.value = val
return
}
current.next = new_data
m.len++
}
}
Для вставки элемента мы проходим по связному списку, при нахождении такого же ключа, как и входного, изменяем значение, в ином случае добавляем в конец новый элемент и увеличиваем счётчик длины на 1.
func (l *List) delete(key string, m *Map) {
current := l.head
if current.key == key {
l.head = l.head.next
m.len--
return
}
for current.next != nil {
if current.next.key == key {
current.next = current.next.next
m.len--
return
}
current = current.next
}
panic("Key is missing!!")
}
Для удаления элемента там необходимо пройтись по списку и найти нужный ключ и удалить этот элемент (заменив его на следующий), попутно уменьшив счётчик длины. В случае отсутствия ключа возвращаем ошибку.
func (l *List) print() []string {
var result []string
current := l.head
if current != nil {
result = append(result, current.key)
}
for current.next != nil {
result = append(result, current.next.key)
current = current.next
}
return result
}
Для получения ключей списка мы проходим по нему и собираем все ключи в массив result
, а затем возвращаем его.
Следующим шагом необходимо реализовать методы самой структуры Map
:
1. Вставка
2. Удаление
3. Получение значения по ключу
4. Получение всех ключей
func (m *Map) insert(key, val string) {
if m.map_list[hash8(key)] == nil {
m.map_list[hash8(key)] = &List{}
}
m.map_list[hash8(key)].add(key, val, m)
}
Для вставки элемента мы проверяем наличие данных в массиве по индексу результата хэш-функции, в случае, если его нет создаём экземпляр структуры List
. Иначе у нас возникает коллизия. Для этого обращаемся к элементу (который является экземпляром структуры List
) и вызываем у него ранее описанный метод add
.
func (m *Map) delete(key string) {
elem := m.map_list[hash8(key)]
if elem == nil { panic("Map is nil!!") }
if elem.head.key == key && elem.head.next == nil {
m.map_list[hash8(key)] = nil
m.len--
fmt.Println("+")
} else if elem.head.next != nil {
elem.delete(key, m)
} else {
panic("Key is missing!!")
}
}
Для реализации удаления элемента проверяем наличие элемента в массиве по индексу результата хэш-функции:
Если элемент пустой, то возвращаем ошибку.
Если есть элемент, но следующего за ним нет, то присваиваем элементу массива
nil
.Если есть элемент и последующий за ним, то вызываем метод
delete
у элемента массива (который имеет тип*List)
.В ином случае возвращаем ошибку о том, что ключ отсутствует.
func (m *Map) get_value(key string) string {
if m.map_list[hash8(key)] == nil { panic("Map is nil!!") }
current := m.map_list[hash8(key)].head
if current != nil && current.key == key { return current.value }
for current.next != nil {
if current.next.key == key { return current.next.value }
current = current.next
}
panic("Key is missing!!")
}
Чтобы получить значение по ключу, необходимо получить связный список из массива на основе результата хэш-функции. Далее пройтись по связному списку, сравнивая входной и текущий ключ.
func (m *Map) keys() []string {
var answer [] string
for _, data := range(m.map_list) {
if data != nil { answer = append(answer, data.print()...)}
}
return answer
}
Для выгрузки всех ключей мы проходим по всему массиву. Если в элементе есть данные, то дополняем слайс answer
результативным слайсом функции print
у структуры List
.
Итоги
Мы разобрались, как реализовать простую хэш-карту на основе 8-битной хэш-функции Пирсона с помощью языка Go. Рассмотрели краевые случаи всех описанных методов, а так же возникновение коллизии. Сложность данной структуры (как на чтение, так и на запись) я бы оценил в наилучшем случает, как O(1), в наихудшем же случае она доходит до O(n), при возникновении коллизии и формировании связного списка длинною > 1.