mph

package module

v0.1.2 Latest Latest Go to latest Published: Nov 16, 2022 License: MIT Imports: 3 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Some quick benchmark results (this is on an Intel(R) Xeon(R) CPU @ 2.80GHz):

Build constructs a minimal perfect hash table from a 350k word dictionary in 100ms (construction time is linear in the size of the input).
Lookups on that dictionary take about 30ns and are 50% faster than a map[string]uint32:

name      time/op
Build      101ms ± 3%
Table     28.1ns ± 2%
TableMap  63.9ns ± 3%

Package mph implements a minimal perfect hash table over strings.

This section is empty.

This section is empty.

This section is empty.

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(keys []string) *Table

Build builds a Table from keys using the "Hash, displace, and compress" algorithm described in http://cmph.sourceforge.net/papers/esa09.pdf.

func (t *Table) Lookup(s string) (n uint32, ok bool)

Lookup searches for s in t and returns its index and whether it was found.