Пакет maphash
Обзор
Пакет maphash предоставляет хеш-функции для последовательностей байтов и сравнимых значений. Он также определяет Hasher — интерфейс между хеш-функцией и хеш-таблицей.
Эти хеш-функции предназначены для реализации хеш-таблиц, фильтров Блума и других структур данных, которым необходимо отображать произвольные строки или последовательности байтов в равномерно распределённое множество беззнаковых 64-битных целых чисел.
Каждый экземпляр хеш-таблицы или структуры данных должен использовать собственный Seed.
Хеш-функции не являются криптографически стойкими. (Для криптографических целей см. crypto/sha256 и crypto/sha512.)
Пример
Код:
// The zero Hash value is valid and ready to use; setting an
// initial seed is not necessary.
var h maphash.Hash
// Add a string to the hash, and print the current hash value.
h.WriteString("hello, ")
fmt.Printf("%#x\n", h.Sum64())
// Append additional data (in the form of a byte array).
h.Write([]byte{'w', 'o', 'r', 'l', 'd'})
fmt.Printf("%#x\n", h.Sum64())
// Reset discards all data previously added to the Hash, without
// changing its seed.
h.Reset()
// Use SetSeed to create a new Hash h2 which will behave
// identically to h.
var h2 maphash.Hash
h2.SetSeed(h.Seed())
h.WriteString("same")
h2.WriteString("same")
fmt.Printf("%#x == %#x\n", h.Sum64(), h2.Sum64())
Пример (BloomFilter)
Код:
package maphash_test
// This file demonstrates a Bloom filter.
import (
"fmt"
"hash/maphash"
"math"
"math/bits"
)
// BloomFilter is a Bloom filter, a probabilistic space-efficient
// representation of a set of values of type V based on hashing.
//
// It provides two operations: Insert inserts an element and Contains
// queries whether a value is a member of the set.
//
// However, unlike a typical set, the size is independent of the
// number of elements. The catch: Contains is permitted to report
// true even for some elements that are not present. The trade-off
// between space and accuracy is determined by parameters at
// construction.
type BloomFilter[V any] struct {
hasher maphash.Hasher[V]
seeds []maphash.Seed // each seed determines a hash function
bytes []byte // bit vector
}
// NewBloomFilterComparable returns a new BloomFilter for the
// specified elements using their natural comparison.
func NewComparableBloomFilter[V comparable](n int, fpProb float64) *BloomFilter[V] {
return NewBloomFilter(maphash.ComparableHasher[V]{}, n, fpProb)
}
// NewBloomFilter constructs a new BloomFilter capable of holding n
// elements with the specified probability of false positive results,
// assuming a well dispersed hash function.
func NewBloomFilter[V any](hasher maphash.Hasher[V], n int, fpProb float64) *BloomFilter[V] {
nbytes, nseeds := calibrate(n, fpProb)
seeds := make([]maphash.Seed, nseeds)
for i := range nseeds {
seeds[i] = maphash.MakeSeed()
}
return &BloomFilter[V]{
hasher: hasher,
bytes: make([]byte, nbytes),
seeds: seeds,
}
}
func (f *BloomFilter[V]) Contains(v V) bool {
for _, seed := range f.seeds {
index, bit := f.locate(seed, v)
if f.bytes[index]&bit == 0 {
return false
}
}
return true
}
func (f *BloomFilter[V]) Insert(v V) {
for _, seed := range f.seeds {
index, bit := f.locate(seed, v)
f.bytes[index] |= bit
}
}
func (f *BloomFilter[V]) locate(seed maphash.Seed, v V) (uint64, byte) {
// Optimization note: the dynamic call to hasher.Hash causes h
// to escape. You can use a sync.Pool can help mitigate the
// allocation cost.
//
// Alternatively, you could copy and specialize the filter logic
// for a specific implementation of maphash.Hasher, allowing
// the compiler's escape analysis to determine that the
// hasher.Hash call does not in fact cause h to escape.
var h maphash.Hash
h.SetSeed(seed)
f.hasher.Hash(&h, v)
hash := h.Sum64()
index := reduce(hash, uint64(len(f.bytes)))
mask := byte(1 << (hash % 8))
return index, mask
}
// reduce maps hash to a value in the interval [0, n).
// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction
func reduce(hash, n uint64) uint64 {
if n > 1<<32-1 {
hi, _ := bits.Mul64(hash, n)
return hi
}
return hash >> 32 * n >> 32
}
func calibrate(n int, fpProb float64) (bytes, seeds int) {
// Following https://en.wikipedia.org/wiki/Bloom_filter:
// - k is the number of hash functions,
// - m is the size of the bit field;
// - n is the number of set bits.
if n == 0 {
return 1, 1
}
logFpProb := math.Log(fpProb)
m := -(float64(n) * logFpProb) / (math.Ln2 * math.Ln2)
// Round up to a byte.
// TODO(adonovan): opt: round up to the next allocation size
// class (see bytes.growSlice) and then compute the possibly
// smaller number of needed seeds based on this higher number.
bytes = int(m) / 8
if float64(bytes*8) < m {
bytes++
}
k := -logFpProb / math.Ln2
seeds = max(int(math.Round(k)), 1)
return bytes, seeds
}
func Example_bloomFilter() {
// Create a Bloom filter optimized for 2 elements with
// a one-in-a-billion false-positive rate.
//
// (This low rate demands a lot of space: 88 bits and
// 30 hash functions. More typical rates are 1-5%;
// at 5%, we need only 16 bits and 4 hash functions.)
f := NewComparableBloomFilter[string](2, 1e-9)
// Insert two elements.
f.Insert("apple")
f.Insert("banana")
// Check whether elements are present.
//
// "cherry" was not inserted, but Contains is probabilistic, so
// this test will spuriously report Contains("cherry") = true
// about once every billion runs.
for _, fruit := range []string{"apple", "banana", "cherry"} {
fmt.Printf("Contains(%q) = %v\n", fruit, f.Contains(fruit))
}
// Output:
//
// Contains("apple") = true
// Contains("banana") = true
// Contains("cherry") = false
}
Указатель
Примеры
Файлы пакета
hasher.go maphash.go
func Bytes 1.19
func Bytes(seed Seed, b []byte) uint64
Bytes возвращает хеш b с указанным начальным значением.
Bytes эквивалентна следующему коду, но более удобна и эффективна:
var h Hash h.SetSeed(seed) h.Write(b) return h.Sum64()
func Comparable 1.24
func Comparable[T comparable](seed Seed, v T) uint64
Comparable возвращает хеш сравнимого значения v с указанным начальным значением, при этом Comparable(s, v1) == Comparable(s, v2), если v1 == v2. Если v != v, результирующий хеш распределяется случайным образом.
func String 1.19
func String(seed Seed, s string) uint64
String возвращает хеш s с указанным начальным значением.
String эквивалентна следующему коду, но более удобна и эффективна:
var h Hash h.SetSeed(seed) h.WriteString(s) return h.Sum64()
func WriteComparable 1.24
func WriteComparable[T comparable](h *Hash, x T)
WriteComparable добавляет x к данным, хешируемым с помощью h.
type ComparableHasher
ComparableHasher — это реализация Hasher, метод Equal(x, y) которой согласуется с x == y.
ComparableHasher определён только для сравнимых типов. Система типов не помешает создать экземпляр типа вроде ComparableHasher[any]; тем не менее нельзя передавать несравнимые значения аргументов методам Hash или Equal этого типа.
type ComparableHasher[T comparable] struct {
// contains filtered or unexported fields
}
func (ComparableHasher[T]) Equal
func (ComparableHasher[T]) Equal(x, y T) bool
func (ComparableHasher[T]) Hash
func (ComparableHasher[T]) Hash(h *Hash, v T)
type Hash 1.14
Hash вычисляет хеш последовательности байтов с заданным начальным значением.
Нулевое значение Hash является допустимым и готовым к использованию. При первом вызове метода Reset, Write, Seed, Clone или Sum64 нулевой Hash выбирает случайное начальное значение. Чтобы задать начальное значение самостоятельно, используйте SetSeed.
Вычисленные значения хеша зависят только от исходного начального значения и последовательности байтов, переданных объекту Hash, но не от способа передачи этих байтов. Например, все три последовательности
h.Write([]byte{'f','o','o'})
h.WriteByte('f'); h.WriteByte('o'); h.WriteByte('o')
h.WriteString("foo")
дают одинаковый результат.
Хеши предназначены для защиты от коллизий, в том числе в ситуациях, когда противник контролирует хешируемые последовательности байтов.
Hash небезопасен для одновременного использования несколькими горутинами, но Seed — безопасен. Если нескольким горутинам необходимо вычислить один и тот же хеш с заданным начальным значением, каждая из них может объявить собственный Hash и вызвать SetSeed с общим значением Seed.
type Hash struct {
// contains filtered or unexported fields
}
func (*Hash) BlockSize 1.14
func (h *Hash) BlockSize() int
BlockSize возвращает размер блока h.
func (*Hash) Clone 1.25
func (h *Hash) Clone() (hash.Cloner, error)
Clone реализует интерфейс hash.Cloner.
func (*Hash) Reset 1.14
func (h *Hash) Reset()
Reset отбрасывает все байты, добавленные в h. (Начальное значение остаётся прежним.)
func (*Hash) Seed 1.14
func (h *Hash) Seed() Seed
Seed возвращает начальное значение h.
func (*Hash) SetSeed 1.14
func (h *Hash) SetSeed(seed Seed)
SetSeed задаёт для h начальное значение seed, которое должно быть возвращено функцией MakeSeed или другим методом Hash.Seed. Два объекта Hash с одинаковым начальным значением работают идентично. Объекты Hash с разными начальными значениями, скорее всего, будут работать по-разному. Все байты, добавленные в h до этого вызова, будут отброшены.
func (*Hash) Size 1.14
func (h *Hash) Size() int
Size возвращает размер значения хеша h — 8 байт.
func (*Hash) Sum 1.14
func (h *Hash) Sum(b []byte) []byte
Sum добавляет текущее 64-битное значение хеша к b. Метод нужен для реализации hash.Hash. При непосредственном вызове эффективнее использовать Hash.Sum64.
func (*Hash) Sum64 1.14
func (h *Hash) Sum64() uint64
Sum64 возвращает текущее 64-битное значение h, которое зависит от начального значения h и последовательности байтов, добавленных в h после последнего вызова Hash.Reset или Hash.SetSeed.
Все биты результата Sum64 распределены почти равномерно и независимо, поэтому результат можно безопасно уменьшать с помощью битовой маски, сдвига или модульной арифметики.
func (*Hash) Write 1.14
func (h *Hash) Write(b []byte) (int, error)
Write добавляет b к последовательности байтов, хешируемых с помощью h. Метод всегда записывает все байты b и никогда не завершается ошибкой; результаты с количеством записанных байтов и ошибкой нужны для реализации io.Writer.
func (*Hash) WriteByte 1.14
func (h *Hash) WriteByte(b byte) error
WriteByte добавляет b к последовательности байтов, хешируемых с помощью h. Метод никогда не завершается ошибкой; результат с ошибкой нужен для реализации io.ByteWriter.
func (*Hash) WriteString 1.14
func (h *Hash) WriteString(s string) (int, error)
WriteString добавляет байты строки s к последовательности байтов, хешируемых с помощью h. Метод всегда записывает всю строку s и никогда не завершается ошибкой; результаты с количеством записанных байтов и ошибкой нужны для реализации io.StringWriter.
type Hasher
Hasher определяет интерфейс между контейнером на основе хеширования и его элементами. Он предоставляет хеш-функцию и отношение эквивалентности для значений типа T, позволяя помещать эти значения в хеш-таблицы и подобные структуры данных.
Разумеется, сравнимые типы уже можно использовать в качестве ключей встроенного типа map в Go, но Hasher также позволяет использовать в качестве ключей подходящей хеш-таблицы несравнимые типы. Hasher может быть полезен и для сравнимых типов, если требуется определить отношение эквивалентности, отличное от обычного (==), например сравнение отдельных полей для типа указателя на структуру или сравнение строк без учёта регистра, как в этом примере:
// CaseInsensitive is a Hasher[string] whose
// equivalence relation ignores letter case.
type CaseInsensitive struct{}
func (CaseInsensitive) Hash(h *Hash, s string) {
h.WriteString(strings.ToLower(s))
}
func (CaseInsensitive) Equal(x, y string) bool {
// (We avoid strings.EqualFold as it is not
// consistent with ToLower for all values.)
return strings.ToLower(x) == strings.ToLower(y)
}
Hasher также позволяет использовать значения в других структурах данных на основе хеширования, таких как фильтр Блума. Тип ComparableHasher упрощает использование сравнимых типов в таких структурах данных с обычным отношением эквивалентности (==).
Инварианты хеширования
Если два значения равны согласно Equal(x, y), то они должны иметь одинаковый хеш согласно результату воздействия Hash(h, x) на h.
Hasher должны быть логически не имеющими состояния: поведение методов Hash и Equal зависит только от аргументов.
Как написать хорошую функцию
При определении хеш-функции и отношения эквивалентности для типа данных может быть полезно сначала задать каноническое представление значений этого типа в виде последовательности элементов, каждый из которых является числом, строкой, логическим значением или указателем. Представление является каноническим, если логически равные значения имеют одинаковое представление, даже если они представлены по-разному. Например, каноническим представлением строки без учёта регистра является strings.ToLower.
После определения представления метод Hash у Hasher должен кодировать значение в Hash с помощью последовательности вызовов Hash.Write для срезов байтов, Hash.WriteString для строк, Hash.WriteByte для байтов и WriteComparable для элементов других типов. Метод Equal у Hasher должен вычислить представления двух значений, а затем сравнить соответствующие элементы, возвращая false при первом несовпадении.
Метод Hash может отбрасывать информацию, если при этом сохраняется его согласованность с методом Equal, определённая выше. Например, допустимые реализации CaseInsensitive.Hash могут проверять только первую букву строки или даже использовать постоянное значение. Однако чем больше информации отбрасывает хеш-функция, тем чаще возникают коллизии хешей и тем медленнее работает хеш-таблица.
Некоторые типы данных, например множества, по своей природе неупорядочены: множество {a, b, c} равно множеству {c, b, a}. В некоторых случаях можно задать каноническое представление множества, отсортировав его элементы. В других случаях это может быть неэффективно, поскольку потребует выделения памяти, или невозможно, если удобный порядок отсутствует. Другой способ хеширования неупорядоченного множества — вычислить хеш каждого элемента отдельно, а затем объединить хеши всех элементов с помощью коммутативной (не зависящей от порядка) операции, например + или ^.
Приведённый ниже метод Hash для гипотетического типа Set иллюстрирует этот подход:
type Set[T comparable] struct{ ... }
type setHasher[T comparable] struct{}
func (setHasher[T]) Hash(hash *maphash.Hash, set *Set[T]) {
var accum uint64
for elem := range set.Elements() {
// Initialize a hasher for the element,
// using same seed as the outer hash.
var sub maphash.Hash
sub.SetSeed(hash.Seed())
// Hash the element.
maphash.WriteComparable(&sub, elem)
// Mix the element's hash into the set's hash.
accum ^= sub.Sum64()
}
maphash.WriteComparable(hash, accum)
}
Во многих языках операция хеширования типа данных просто возвращает целое число. Однако это позволяет противнику систематически создавать большое количество значений с одинаковым хешем, снижая асимптотическую производительность хеш-таблиц в результате атаки типа «затопление хешами», направленной на отказ в обслуживании. Напротив, вычисление хешей в виде последовательности значений, добавляемых в Hash с непредсказуемым Seed, который различается для разных хеш-таблиц, помогает смягчить эту атаку.
Фактически Seed выбирает одну из 2⁶⁴ различных хеш-функций. Пример кода выше вызывает SetSeed для подобъекта Hasher элемента, чтобы использовать ту же хеш-функцию, что и для самого Set, а не случайную.
type Hasher[T any] interface {
Hash(*Hash, T)
Equal(x, y T) bool
} type Seed 1.14
Seed — это случайное значение, определяющее конкретную хеш-функцию, вычисляемую объектом Hash. Если два объекта Hash используют одинаковые значения Seed, они будут вычислять одинаковые значения хеша для любых заданных входных данных. Если два объекта Hash используют разные значения Seed, они с большой вероятностью будут вычислять разные значения хеша для любых заданных входных данных.
Seed необходимо инициализировать вызовом MakeSeed. Нулевое значение Seed не инициализировано и недопустимо для использования с методом SetSeed типа Hash.
Каждое значение Seed действует только в пределах одного процесса; его нельзя сериализовать или иным образом воссоздать в другом процессе.
type Seed struct {
// contains filtered or unexported fields
}
func MakeSeed 1.14
func MakeSeed() Seed
MakeSeed возвращает новое случайное начальное значение.
© Google, Inc.
Licensed under the Creative Commons Attribution License 3.0.
http://golang.org/pkg/hash/maphash/
