Go-фича: Хешеры

Часть серии Принято! В ней простыми словами объясняются новые фичи Go.

Стандартный подход к вычислению хеша и проверке на равенство в пользовательских структурах данных.

Версия 1.26 • Станд. библиотека • Полезно

Что

Новый интерфейс maphash.Hasher — это стандартный способ хешировать и сравнивать элементы в пользовательских коллекциях, например, в собственных картах или множествах.

// Hasher реализует хеширование и проверку на равенство для типа T.
type Hasher[T any] interface {
    Hash(hash *maphash.Hash, value T)
    Equal(T, T) bool
}

Тип ComparableHasher — это стандартная реализация хешера для сравнимых (comparable) типов — таких как числа, строки и структуры с сравнимыми полями.

Зачем

Пакет maphash предоставляет хеш-функции для срезов байтов и строк, но не объясняет, как создавать собственные структуры данных, основанные на хешировании.

Чтобы это исправить, в Go добавят хешер (hasher) — стандартный интерфейс для хеширования и сравнения элементов коллекции, а также его реализацию по умолчанию.

Подробности

Добавить интерфейс хешера в пакет maphash:

// Hasher - это тип, который реализует хеширование
// и сравнение на равенство для типа T.
//
// Hasher не должен иметь состояние, и его
// нулевое значение должно быть валидным.
// Поэтому обычно Hasher - это пустая структура.
type Hasher[T any] interface {
    // Hash обновляет хеш в соответствии со значением value.
    //
    // Если два значения равны (Equal), их хеш тоже должен совпадать.
    // То есть, если Equal(a, b) возвращает true, то Hash(h, a) и Hash(h, b)
    // должны записывать одинаковые данные в h.
    Hash(hash *maphash.Hash, value T)
    Equal(T, T) bool
}

Добавить умолчательную реализацию хешера для сравнимых типов:

// ComparableHasher - это реализация Hasher для сравнимых типов.
// Его метод Equal(x, y) логически соответствует x == y.
type ComparableHasher[T comparable] struct{}
func (h ComparableHasher[T]) Hash(hash *Hash, value T)
func (h ComparableHasher[T]) Equal(x, y T) bool

Пример

Вот нечувствительный к регистру строк хешер:

// CaseInsensitive - это хешер для сравнения строк без учета регистра.
type CaseInsensitive struct{}

func (CaseInsensitive) Hash(h *maphash.Hash, s string) {
    // Используем lowercase вместо case folding для простоты.
    h.WriteString(strings.ToLower(s))
}

func (CaseInsensitive) Equal(a, b string) bool {
    return strings.ToLower(a) == strings.ToLower(b)
}

И дженерик-множество Set, с настраиваемым хешером для проверки на равенство и хеширования:

// Set - это универсальная реализация множества
// с возможностью подставить свой хешер.
// Значения хранятся в карте корзин (bucket),
// корзины идентифицируются по хешу от значения.
// Если несколько значений попадают в одну и ту же корзину,
// используется линейный поиск, чтобы найти нужное.
type Set[H maphash.Hasher[V], V any] struct {
    seed   maphash.Seed   // случайный посев для хеширования
    hasher H              // выполняет хеширование и проверку на равенство
    data   map[uint64][]V // корзины значений, индексированные по хешу
}

// NewSet создает новый экземпляр Set с указанной функцией хеширования.
func NewSet[H maphash.Hasher[V], V any](hasher H) *Set[H, V] {
    return &Set[H, V]{
        seed:   maphash.MakeSeed(),
        hasher: hasher,
        data:   make(map[uint64][]V),
    }
}

Вспомогательный метод calcHash использует хешер, чтобы вычислить хеш значения:

// calcHash вычисляет хеш значения.
func (s *Set[H, V]) calcHash(val V) uint64 {
    var h maphash.Hash
    h.SetSeed(s.seed)
    s.hasher.Hash(&h, val)
    return h.Sum64()
}

Этот хеш используется в методах Has и Add. Он служит ключом в карте корзин, чтобы найти нужную корзину для значения.

Метод Has проверяет, есть ли значение в соответствующей корзине:

// Has возвращает true, если указанное значение есть в множестве.
func (s *Set[H, V]) Has(val V) bool {
    hash := s.calcHash(val)
    if bucket, ok := s.data[hash]; ok {
        for _, item := range bucket {
            if s.hasher.Equal(val, item) {
                return true
            }
        }
    }
    return false
}

Add добавляет значение в соответствующую корзину:

// Add добавляет значение в множество, если его там еще нет.
func (s *Set[H, V]) Add(val V) {
    if s.Has(val) {
        return
    }
    hash := s.calcHash(val)
    s.data[hash] = append(s.data[hash], val)
}

Теперь мы можем создать регистро-независимое множество строк:

func main() {
    set := NewSet(CaseInsensitive{})

    set.Add("hello")
    set.Add("world")

    fmt.Println(set.Has("HELLO")) // true
    fmt.Println(set.Has("world")) // true
}

true
true

Или обычное множество строк с помощью maphash.ComparableHasher:

func main() {
    set := NewSet(maphash.ComparableHasher[string]{})

    set.Add("hello")
    set.Add("world")

    fmt.Println(set.Has("HELLO")) // false
    fmt.Println(set.Has("world")) // true
}

false
true

Ссылки

𝗣 70471 • 𝗖𝗟 657296

★ Подписывайтесь на канал и проходите курсы.