README
¶
mph
mph is a Go package for that implements a minimal perfect hash table over strings. It uses the "Hash, displace, and compress" algorithm and the Murmur3 hash function.
Some quick benchmark results (this is on an i7-8700K):
-
Buildconstructs a minimal perfect hash table from a 102k word dictionary in 18ms (construction time is linear in the size of the input). -
Lookups on that dictionary take about 30ns and are 27% faster than amap[string]uint32:BenchmarkTable-12 199293806 29.99 ns/op BenchmarkTableMap-12 145449822 40.92 ns/op
Documentation
¶
Overview ¶
Package mph implements a minimal perfect hash table over strings.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Table ¶
type Table struct {
// contains filtered or unexported fields
}
A Table is an immutable hash table that provides constant-time lookups of key indices using a minimal perfect hash.
func Build ¶
Build builds a Table from keys using the "Hash, displace, and compress" algorithm described in http://cmph.sourceforge.net/papers/esa09.pdf.
Source Files