Блог

# #go #hash #perfect-hash

Вопрос:

 
package main

import (
    "fmt"
    "strconv"
    "unsafe"
)

//go:linkname strhash runtime.strhash
func strhash(p unsafe.Pointer, h uintptr) uintptr

const seed = 666
func main() {
    m := make(map[uintptr]string)
    for i := 0; i < 1000000000; i   {
        key := strconv.Itoa(i)
        hash := strhash(unsafe.Pointer(amp;key), seed)
        _, exist := m[hash]
        if exist {
            fmt.Println("collision")
            break
        }
        m[hash] = key
    }

    fmt.Println("finish")
}

 

Комментарии:

1. Идеальные хэш-функции определяются только для заданного набора возможных входных данных (каждая хэш-функция постоянного размера в конечном итоге приводит к столкновениям, если разрешены все входные данные, потому что существует бесконечное количество входных данных, но конечное количество выходных данных). Поскольку вы не указали ни одного, на ваш вопрос нельзя ответить. Однако, учитывая набор входных данных, вычисление выходных данных для каждого из них, безусловно, является одним из возможных способов убедиться в отсутствии коллизий.

2.встроенный тип карты реализует алгоритм, который обрабатывает конфликты, подробнее см. на hackernoon.com/some-insights-on-maps-in-golang-rm5v3ywh Учитывая, что эта функция ref используется для map[string]... cs.opensource.google/go/go/ /master:src/runtime/… Я думаю, что она не свободна от столкновений. Хотя на практике я не понимаю, как они формализуют доказательство в математическом аспекте этой вещи. Но тестирование на компьютере может быть выполнено только на подмножестве. В противном случае вам понадобится бесконечная память.

Ответ №1: