mph

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

• type CHD
  • func Mmap(b []byte) (*CHD, error)
  • func Read(r io.Reader) (*CHD, error)
  • func (c *CHD) Get(key []byte) []byte
  • func (c *CHD) Iterate() *Iterator
  • func (c *CHD) Len() int
  • func (c *CHD) Write(w io.Writer) error
• type CHDBuilder
  • func Builder() *CHDBuilder
  • func (b *CHDBuilder) Add(key []byte, value []byte)
  • func (b *CHDBuilder) Build() (*CHD, error)
• type Iterator
  • func (c *Iterator) Get() (key []byte, value []byte)
  • func (c *Iterator) Next() *Iterator

Types

type CHD

type CHD struct {
	// contains filtered or unexported fields
}

CHD hash table lookup.

func Mmap

func Mmap(b []byte) (*CHD, error)

Mmap creates a new CHD aliasing the CHD structure over an existing byte region (typically mmapped).

func Read

func Read(r io.Reader) (*CHD, error)

Read a serialized CHD.

func (*CHD) Get

func (c *CHD) Get(key []byte) []byte

Get an entry from the hash table.

func (*CHD) Iterate

func (c *CHD) Iterate() *Iterator

Iterate over entries in the hash table.

func (*CHD) Len

func (c *CHD) Len() int

func (*CHD) Write

func (c *CHD) Write(w io.Writer) error

Serialize the CHD. The serialized form is conducive to mmapped access. See the Mmap function for details.

type CHDBuilder

type CHDBuilder struct {
	// contains filtered or unexported fields
}

Build a new CDH MPH.

func Builder

func Builder() *CHDBuilder

Create a new CHD hash table builder.

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)

type Iterator

type Iterator struct {
	// contains filtered or unexported fields
}

func (*Iterator) Get

func (c *Iterator) Get() (key []byte, value []byte)

func (*Iterator) Next

func (c *Iterator) Next() *Iterator