Комментарии 9
Вот тут https://github.com/tidwall/hashmap/ есть реализация на основе открытой адресации. Судя по бенчмаркам, оно иногда даже быстрее, чем стандартная мапа. Возможно, это связано с тем, что при последовательном расположении элементов кеш процессора работает эффективнее.
if insertIdx == nil && isCellEmpty(b.tophash[i]) {
insertIdx = new(int)
*insertIdx = i
}Вот здесь, в bucket.Put(), у вас случаем break не пропущен?
Если кратко - нет)
m.Put("key1", 1) // массив tophash [val1, 0, 0, ...]
m.Put("key2", 2) // [val1, val2, 0, 0, ...]
m.Delete("key1") // [1, val2, 0, 0, ... ]
m.Put("key2", 3) Например, добавляем два элемента и удаляем первый из них. У нас в массиве tophash появится "дыра" со значением 1 == emptyCell. По этому значению мы понимаем что ячейка пустая, но положить сразу туда значение мы не можем, т.к. возможно значение для key2 находится дальше. По этому мы просто запоминаем первую свободную ячейку на случай когда в конце итерации мы не нашли совпадение по переданному ключу.
Всё по полочкам, супер. Спасибо!
Я рекомендую вот эту статью глянуть, т.к. там автор задался той же идеей - реализацией гошной хешмапы через дженерики. И уперся в тот факт, что Go'шный хешер не экспортирован для работы с неизвестными типами. Экспортировать можно через unsafe, мапу, и каст к нужному типу. Возможно имеет смысл попробовать с стандартным хешером который использует AES, вдруг будет быстрее?
Hashmap(map) по версии Golang вместе с реализацией на дженериках