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 ShardedTable ¶
type ShardedTable struct {
// contains filtered or unexported fields
}
func LoadShardedTableFromFile ¶
func LoadShardedTableFromFile(filePath string) (*ShardedTable, error)
func NewShardedTable ¶
func NewShardedTable( keyLen, prefBits, buffSzBytes int, mphDirPath string, ) (*ShardedTable, error)
func (*ShardedTable) DumpToFile ¶
func (st *ShardedTable) DumpToFile(filePath string) error
func (*ShardedTable) GetCounts ¶
func (st *ShardedTable) GetCounts() []uint
func (*ShardedTable) Put ¶
func (st *ShardedTable) Put(key []byte) error
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. Returns an error if duplicate keys are detected.
Source Files