README
¶
Minimal Perfect Hashing for Go
This library provides Minimal Perfect Hashing (MPH) using the Compress, Hash and Displace (CHD) algorithm.
What is this useful for?
Primarily, extremely efficient access to potentially very large static datasets, such as geographical data, NLP data sets, etc.
On my 2012 vintage MacBook Air, a benchmark against a wikipedia index with 300K keys against a 2GB TSV dump takes about ~200ns per lookup.
How would it be used?
Typically, the table would be used as a fast index into a (much) larger data set, with values in the table being file offsets or similar.
The tables can be serialized. Numeric values are written in little endian form.
Example code
Building and serializing an MPH hash table (error checking omitted for clarity):
b := mph.Builder()
for k, v := range data {
b.Add(k, v)
}
h, _ := b.Build()
w, _ := os.Create("data.idx")
_ := h.Write(w)
Deserializing the hash table and performing lookups:
r, _ := os.Open("data.idx")
h, _ := mph.Read(r)
v := h.Get([]byte("some key"))
if v == nil {
// Key not found
}
MMAP is also indirectly supported, by deserializing from a byte slice and slicing the keys and values.
The API documentation has more details.
Documentation
¶
Overview ¶
Package mph is a Go implementation of the compress, hash and displace (CHD) minimal perfect hash algorithm.
See http://cmph.sourceforge.net/papers/esa09.pdf for details.
To create and serialize a hash table:
b := mph.Builder()
for k, v := range data {
b.Add(k, v)
}
h, _ := b.Build()
w, _ := os.Create("data.idx")
b, _ := h.Write(w)
To read from the hash table:
r, _ := os.Open("data.idx")
h, _ := h.Read(r)
v := h.Get([]byte("some key"))
if v == nil {
// Key not found
}
MMAP is also indirectly supported, by deserializing from a byte slice and slicing the keys and values.
See https://github.com/alecthomas/mph for source.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CHD ¶
type CHD struct {
// contains filtered or unexported fields
}
CHD hash table lookup.
type CHDBuilder ¶
type CHDBuilder struct {
// contains filtered or unexported fields
}
Build a new CDH MPH.
func (*CHDBuilder) Add ¶
func (b *CHDBuilder) Add(key []byte, value []byte)
Add a key and value to the hash table.
func (*CHDBuilder) Build ¶
func (b *CHDBuilder) Build() (*CHD, error)
Source Files