Более простой метод для вычисления минимального идеального хэша? - PullRequest
Новая
       31

Более простой метод для вычисления минимального идеального хэша?

0 голосов
/ 19 января 2019

У меня есть небольшие (?) Наборы (в диапазоне от 0 до 100) 32-разрядных целых чисел без знака. Для данного набора я хочу придумать минимальные параметры, чтобы описать минимальный (изометрический) совершенный хэш данного набора. Высокий уровень кода, который я использовал, чтобы поэкспериментировать с идеей, закончился примерно так: 

def murmur(key, seed=0x0):
    // Implements 32bit murmur3 hash...
    return theHashedKey

sampleInput = [18874481, 186646817, 201248225, 201248705, 201251025, 201251137, 201251185, 184472337, 186649073, 201248625, 201248721, 201251041, 201251153, 184473505, 186649089, 201248657, 201251009, 201251057, 201251169, 186646818, 201248226, 201248706, 201251026, 201251138, 201251186, 186649074, 201248626, 201248722, 201251042, 201251154, 186649090, 201248658, 201251010, 201251058, 201251170]

for seed in range(11111): // arbitrary upper seed limit
    for modulus in range(10000):
        hashSet = set((murmur(x, seed=seed) % modulus for x in sampleInput))
        if len(hashSet) >= len(allValves):
            print('minimal modulus', modulus, 'for seed', seed)
            break

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

Мне кажется, что должен быть более изящный / детерминированный способ придумать эти значения? Но здесь переполняются мои математические навыки.

Я сейчас экспериментирую на Python, но в конечном итоге хочу реализовать что-то на C на небольшой встроенной платформе.

...