index

Documentation

Overview

Package index constructs a Bloom filter index for a set of string keys.

Index

• func Encode(idx *Index) *indexpb.Index
• type Index
  • func Decode(pb *indexpb.Index) (*Index, error)
  • func New(numKeys int, opts *Options) *Index
  • func (idx *Index) Add(key string)
  • func (idx *Index) Has(key string) bool
  • func (idx *Index) Len() int
  • func (idx *Index) Stats() Stats
• type Options
• type Stats

Examples

• Index

Functions

func Encode

func Encode(idx *Index) *indexpb.Index

Encode encodes idx as a protocol buffer message for storage.

Types

type Index

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

An Index holds a Bloom filter index for a set of keys.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/creachadair/ffs/index"
)

func main() {
	words := strings.Fields("a foolish consistency is the hobgoblin of little minds")

	idx := index.New(32, nil)
	for _, word := range words {
		idx.Add(word)
	}

	fmt.Printf("Has %q: %v\n", "foolish", idx.Has("foolish"))
	fmt.Printf("Has %q: %v\n", "cabbage", idx.Has("cabbage"))

	info := idx.Stats()
	fmt.Printf("%d keys, %d filter bits, %d hash seeds\n",
		info.NumKeys, info.FilterBits, info.NumHashes)

}

Output:

Has "foolish": true
Has "cabbage": false
9 keys, 256 filter bits, 6 hash seeds

func Decode

func Decode(pb *indexpb.Index) (*Index, error)

Decode decodes an encoded index from protobuf.

func New

func New(numKeys int, opts *Options) *Index

New constructs an empty index with capacity for the specified number of keys. A nil opts value is ready for use and provides default values as described on Options. New will panic if numKeys ≤ 0.

func (*Index) Add

func (idx *Index) Add(key string)

Add adds the specified key to the index.

func (*Index) Has

func (idx *Index) Has(key string) bool

Has reports whether key is one of the indexed keys. False positives are possible for keys that were not added to the index, but no false negatives.

func (*Index) Len

func (idx *Index) Len() int

Len reports the number of keys added to the index. This is shorthand for idx.Stats().NumKeys.

func (*Index) Stats

func (idx *Index) Stats() Stats

Stats returns size and capacity statistics for the index.

type Options

type Options struct {
	// Compute a 64-bit hash of s. If nil, uses xxhash.Sum64String.
	Hash func(s string) uint64

	// The maximum false positive rate to permit. A value ≤ 0 defaults to 0.03.
	// Decreasing this value increases the memory required for the index.
	FalsePositiveRate float64
}

Options provide optional settings for an index. A nil *Options is ready for use and provides default values as described.

type Stats

type Stats struct {
	NumKeys    int // the number of keys added to the index
	FilterBits int // the number of bits allocated to the Bloom filter (m)
	NumHashes  int // the number of hash seeds allocated (k)
}

Stats record size and capacity statistics for an Index.