Сергей Деревяго

Эффективные хеш-таблицы

1. Введение

В Go нет недостатка хеш-таблиц. Вы всегда можете использовать встроенную map[Key]Val, с ошеломительной скоростью обладающую непревзойденным удобством!

А изобилие типов Key, разрешенных к использованию, способно довести до изумления!

Вот только ни указатель, ни слайс не подходят... Невозможно подсунуть свои операции (равенства и хеширования). Но хоть со скоростью все хорошо! (извините, не удержался)

Итого, мне пришлось написать HashMap[K, V any], закрывающую проблемы. Пристегните ремни, скучно не будет!

С уважением, Сергей Деревяго.

2. UintMap

Все дети знают, что в Google работают Самые Лучшие профессионалы, легко и просто создающие ЧУДОВИЩНО эффективные алгоритмы! И потом полирующие их до ЛЮТОГО совершенства, за восемнадцать доступных лет...

Дети вообще любят сказки.

Баста, карапузики! Кончилися танцы:

R0R1
ns/opB/opallocs/opns/opB/opallocs/op
GoUintMap246813459148179167733029555233
MyUintMap1280396899584149759303522602
Go/My1.930.665.641.720.8416.50

В это трудно поверить, но:

Нет, все-таки вдумайтесь!

На коленке написанная хеш-таблица для целых чисел UintMap почти в два раза обгоняет ЖУТКО оптимизированную нативную map[uint64]uint64!! И особенно менее мусорит!!!

Но раз трудно поверить, то давайте проверим:

bench1\uintmap.go 
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? Гмм... Лучше сразу позорить! Позвоните родителям.

3. HashMap

Знатоки языка меня сразу поправят, что дозволены указатели! Ну, вместо типа ключа: map[*Key]Val. Типа того.

Ну так и все грибы можно кушать! Некоторые, лишь раз...

Как вы правильно разумеете, map[*Key]Val функционально эквивалентен map[uintptr]Val, т.е. там сравниваются значения указателей, что глупо почти всегда! А социум жаждет объекты: "одинаковые" объекты по разному адресу должны быть равны.

И вот, кстати, о людях:

bench1\hashmap.go 
type Person struct {
    Id    int
    Name  FullName
    Other [100]byte
}

type FullName struct {
    First string
    Last  string
}

Набор Person где-то там в памяти -- обычное дело. Яко же нужен поиск по имени, зело "индекс" придется себе сотворить: map[FullName]*Person. Как вы понимаете, другие прямые варианты отсутствуют!

Таким образом, для каждого Person в индексе будет храниться и полный объект FullName. Хотя точно такой же FullName уже есть в самом Person!

Безобразие? Безобразие!

Но можно ли ругать за это Google? Ну, вы поняли...

Не вопрос, Николай Гаврилович! Нам понятно, что делать. Будем делать HashMap[*FullName, *Person]. А пока создадим пару функций:

bench1\hashmap.go 
func HashFullName(k *FullName) uint64 {
    return lib.StrHash(k.First) ^ lib.StrHash(k.Last)
}

func EqualFullName(k1, k2 *FullName) bool {
    return *k1 == *k2
}

Все как обычно: равные объекты обязаны иметь равный хеш! Но обратное, вообще говоря, неверно.

В принципе, все. Начинаем:

bench1\hashmap.go 
func MyPersonHashMap() {
    const N = hmN

//R0|    hm := lib.NewHashMap[*FullName, *Person](HashFullName, EqualFullName, 0)
    hm := lib.NewHashMap[*FullName, *Person](HashFullName, EqualFullName, N) //R1|

    for i := 0; i < N; i++ {
        hm.Findsert(&Prs[i].Name, &Prs[i])
    }
    lib.Assert(hm.Size() == N)

    cnt := 0
    for i := 0; i < N; i++ {
        if *hm.Val(hm.Find(&Prs[i].Name)) == &Prs[i] {
            cnt++
        }

        if hm.Find(&BadPn.Name) == -1 {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := 0; i < N; i++ {
        hm.Delete(&Prs[i].Name)
    }
    lib.Assert(hm.Size() == 0)
}

func GoPersonMap() {
    const N = hmN

//R0|    m := make(map[FullName]*Person)
    m := make(map[FullName]*Person, N) //R1|

    for i := 0; i < N; i++ {
        m[Prs[i].Name] = &Prs[i]
    }
    lib.Assert(len(m) == N)

    cnt := 0
    for i := 0; i < N; i++ {
        if m[Prs[i].Name] == &Prs[i] {
            cnt++
        }

        if _, ok := m[BadPn.Name]; !ok {
            cnt++
        }
    }
    lib.Assert(cnt == N*2)

    for i := 0; i < N; i++ {
        delete(m, Prs[i].Name)
    }
    lib.Assert(len(m) == 0)
}

Может сразу не видно, но вызов hm.Findsert(&Prs[i].Name, &Prs[i]) использует адрес подобъекта Prs[i].Name, а не значение. Что дает очевидные выигрыши:

R0R1
ns/opB/opallocs/opns/opB/opallocs/op
GoPersonMap5649722156796979406222378707333
MyPersonHashMap400945512001301430919574341922
Go/My1.411.315.641.311.8116.50

Сиречь:

Подчеркну вдругорядь: map в Go -- это нативная, очень сильно оптимизированная структура! На чистом Go вы никогда такого не добьетесь.

И тем не менее, простая как лапоть HashMap (на чистом Go, без приключений) уверенно обгоняет map в полтора раза и использует в два раза меньше памяти! (ну, почти)

Что, в общем, не удивительно: указатель *FullName всегда будет легче и меньше объекта FullName.

4. BytesMap

А теперь про BytesMap. Как ни странно, с него все поехало. Но об этом в другой статье.

А потом уже вышли HashMap[K, V any] обобщенный, ну и очень конкретный UintMap.

Там с UintMap-ом вообще анекдот! Надо было проверить, в какой степени будет все плохо, если вдруг написать самому...

Поплохело в итоге у Google!

Только стоит ли их ругать? Обязательно звоните конгрессмену! И скажите, что тревожат увольнения. Мол, из Google увольнять и увольнять...

Чем еще они нас осчастливят? Ща аудитория займется депиляцией: Generics can make your Go code slower! Осознали последствия?! Впору рвать волосы на органах приседания! Я подожду.

Вот поэтому сделан BytesMap -- полная специализация HashMap[[]byte, []byte]. Ну а выигрыш?

А для выигрыша нам нужна еще жертва от Google: map[[]byte][]byte. Но, конечно же, так не получится: зело слайсы в ключах не дозволено!

А теперь улыбнемся, так как можно map[string][]byte. Ведь по сути внутри то же самое!

Все готово, поехали:

bench1\bytesmap.go 
func MyBytesMap() {
    const N = bmN

//R0|    bm := lib.NewBytesMap(0)
    bm := lib.NewBytesMap(N) //R1|

    for i := 0; i < N; i++ {
        bm.Findsert(Keys[i], Vals[i])
    }
    lib.Assert(bm.Size() == N)

    // ...
}

func MyBytesHashMap() {
    const N = bmN

//R0|    hm := lib.NewHashMap[[]byte, []byte](lib.MemHash, bytes.Equal, 0)
    hm := lib.NewHashMap[[]byte, []byte](lib.MemHash, bytes.Equal, N) //R1|

    for i := 0; i < N; i++ {
        hm.Findsert(Keys[i], Vals[i])
    }
    lib.Assert(hm.Size() == N)

    // ...
}

func GoBytesMap() {
    const N = bmN

//R0|    m := make(map[string][]byte)
    m := make(map[string][]byte, N) //R1|

    for i := 0; i < N; i++ {
        m[string(Keys[i])] = Vals[i]
    }
    lib.Assert(len(m) == N)

    // ...
}

Вы когда-нибудь видели МНОГО мусора? Ну вот как бы команда мартышек двадцать лет возле пальмы!

Так смотрите сюда: в 720 и 5017 раз больше мусора!!!

R0R1
ns/opB/opallocs/opns/opB/opallocs/op
GoBytesMap4515630164768610079306632686679510033
MyBytesHashMap394810619274241423958977536662
MyBytesMap357482319274241423256057536652
Go/MyBytesHash1.140.857201.281.155017
Go/MyBytes1.260.857201.321.155017
MyBytesHash/MyBytes1.101.03

Да, согрешило одно место: m[string(Keys[i])]. Мы всего-только делаем string из []byte. Создаем, чтобы варварски выбросить...

Берегите Природу, мать вашу!

Что тут скажешь...

Что еще? Ну так самое главное: BytesMap воистину быстрей HashMap! В нашем случае жалкие 10%, но это просто посчастливилось! А в общем случае, при передаче interface в generic function... Вы знаете, кого благодарить!

5. Заключение

Статья небольшая, нужны ли итоги?
Нелишними будут? OK, хорошо.
  1. Смело берите HashMap[K, V any] для слайсов и указателей!
  2. Немного оптимизированная BytesMap -- лучший выбор для []byte.
  3. Интересно оптимизированная UintMap -- это выбор для целых чисел. Разберитесь, что там "не так", и используйте за основу.
Ну и все мы тут очень надеемся, что Google разгонит своих раздолбаев... Но это не точно.
Copyright © С. Деревяго, 2025

Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.