Эффективные хеш-таблицы на Go
В Go нет недостатка хеш-таблиц. Вы всегда можете использовать встроенную map[Key]Val, с ошеломительной скоростью обладающую непревзойденным удобством! А изобилие типов Key, разрешенных к использованию, способно довести до изумления!
Вот только ни указатель, ни слайс не подходят... Невозможно подсунуть свои операции (равенства и хеширования). Но хоть со скоростью все хорошо! (извините, не удержался)
Итого, мне пришлось написать HashMap[K, V any], закрывающую проблемы.
------------------8<------------------
В это трудно поверить, но:
Без резервирования памяти (конфигурация
R0),map[uint64]uint64работает в1.93раза медленнееUintMap! И производит в5.64раза больше мусора!!А с полным резервированием (
R1), в1.72раза медленнее! И аж в16.5раз больше мусора!!!
Вдумайтесь! На коленке написанная хеш-таблица для целых чисел UintMap почти в два раза обгоняет ЖУТКО оптимизированную нативную map[uint64]uint64!! И существенно менее мусорит!!!
Но раз трудно поверить, то давайте проверим:
func MyUintMap() {
const N = umN
//R0| um := lib.NewUintMap(0)
um := lib.NewUintMap(N) //R1|
for i := uint64(0); i < N; i++ {
um.Findsert(i, i+N)
}
lib.Assert(um.Size() == N)
cnt := 0
for i := uint64(0); i < N; i++ {
if *um.Val(um.Find(i)) == i+N {
cnt++
}
if um.Find(i+N) == -1 {
cnt++
}
}
lib.Assert(cnt == N*2)
for i := uint64(0); i < N; i++ {
um.Delete(i)
}
lib.Assert(um.Size() == 0)
}
func GoUintMap() {
const N = umN
//R0| m := make(map[uint64]uint64)
m := make(map[uint64]uint64, N) //R1|
for i := uint64(0); i < N; i++ {
m[i] = i + N
}
lib.Assert(len(m) == N)
cnt := 0
for i := uint64(0); i < N; i++ {
if m[i] == i+N {
cnt++
}
if _, ok := m[i+N]; !ok {
cnt++
}
}
lib.Assert(cnt == N*2)
for i := uint64(0); i < N; i++ {
delete(m, i)
}
lib.Assert(len(m) == 0)
}Здесь всего-то лишь вставка, два поиска и удаление. Запустите go test -bench=UintMap -benchmem и увидите сами. Вот только можно ли ругать Google за неэффективный map[uint64]uint64?
------------------8<------------------
Итоги?
Смело берите
HashMap[K, V any]для слайсов и указателей!Немного оптимизированная
BytesMap-- лучший выбор для[]byte.Интересно оптимизированная
UintMap-- это выбор для целых чисел. Разберитесь, что там "не так", и используйте за основу.
И как всегда, исходный код, подробности и пару неудачных шуток вы можете найти в моей статье https://ders.by/go/hashmap/hashmap.html
