Package cuckoo implements d-ary bucketized cuckoo hashing with stash (bucketized cuckoo hashing is also known as splash tables).
This implementation uses configurable number of hash functions and cells per bucket.
Greedy algorithm for collision resolution is a random walk.
Cuckoo is a memory-efficient alternative to the built-in map[Key]Value type (where Key is an integer type and Value can be any type) with zero per-item overhead.
Hence, the memory-efficiency is equal to the load factor (which can be as high as 99%).
Benchmark results on linux/amd64 with i7-4770S (2M uint32 Key/Value insertion) with gc compiler (version 1.7):
go test -bench=. -v -cpu 1
=== RUN TestZero
--- PASS: TestZero (0.00s)
=== RUN TestSimple
--- PASS: TestSimple (1.28s)
=== RUN TestMem
--- PASS: TestMem (0.41s)
cuckoo_test.go:148: LoadFactor: 0.9534401893615723
cuckoo_test.go:149: Built-in map memory usage (MiB): 65.57434844970703
cuckoo_test.go:150: Cuckoo hash memory usage (MiB): 16.000137329101562
BenchmarkCuckooInsert 10000000 121 ns/op 0 B/op 0 allocs/op
BenchmarkCuckooSearch 20000000 83.8 ns/op 0 B/op 0 allocs/op
BenchmarkCuckooDelete 20000000 132 ns/op 0 B/op 0 allocs/op
BenchmarkMapInsert 10000000 130 ns/op 9 B/op 0 allocs/op
BenchmarkMapSearch 20000000 81.6 ns/op 0 B/op 0 allocs/op
BenchmarkMapDelete 100000000 11.7 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/salviati/cuckoo 12.941s
Cuckoo is SIMD-friendly by design, and there are plans for fast-path SIMD functions.
After cloning the repository, modify the definitions of Key and Value types to fit your needs. For optimal performance, you should also experiment with the fine-grade parameters of the algorithm listed in config.go.
This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.