идеальная хеш-функция

Question

Я пытаюсь хэшировать значения

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

Мне нужна функция, которая отобразит их в массив размером 13 без каких-либо коллизий.

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

Как мне найти хэш-функцию такого рода?Я играл с gperf, но на самом деле я этого не понимаю и не смог получить результаты, которые искал.

Answer 1

если вы знаете точные ключи, то создать идеальную хеш-функцию будет тривиально -

int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    // ...
    default:   return -1;
  }
}

Answer 2

Найден один

Я попробовал несколько вещей и нашел один полуручный:

(n ^ 28) % 13

Полуручным был следующий скрипт ruby, который я использовал для тестирования функций-кандидатовдиапазон параметров:

t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
  t2 = t.map { |e| (e ^ i) % 13 }
  puts i if t2.uniq.length == t.length
end

Answer 3

На некоторых платформах (например, встроенных) операция по модулю обходится дорого, поэтому лучше избегать % 13.Но AND операция с битами младших разрядов обходится дешево и эквивалентна модулю степени 2.

Я попытался написать простую программу (на Python) для поиска идеального хэша ваших 11точки данных, используя простые формы, такие как ((x << a) ^ (x << b)) & 0xF (где & 0xF эквивалентно % 16, что дает результат в диапазоне 0..15, например).Мне удалось найти следующий хеш без столкновений, который дает индекс в диапазоне 0..15 (выраженный в виде макроса C):

#define HASH(x)    ((((x) << 2) ^ ((x) >> 2)) & 0xF)

Вот программа Python, которую я использовал:

data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
    """Shift right that allows for negative values, which shift left
    (Python shift operator doesn't allow negative shift values)"""
    if shift_value == None:
        return 0
    if shift_value < 0:
        return value << (-shift_value)
    else:
        return value >> shift_value

def find_hash():
    def hashf(val, i, j = None, k = None):
        return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) & 0xF

    for i in xrange(-7, 8):
        for j in xrange(i, 8):
            #for k in xrange(j, 8):
                #j = None
                k = None
                outputs = set()
                for val in data:
                    hash_val = hashf(val, i, j, k)
                    if hash_val >= 13:
                        pass
                        #break
                    if hash_val in outputs:
                        break
                    else:
                        outputs.add(hash_val)
                else:
                    print i, j, k, outputs

if __name__ == '__main__':
    find_hash()

Answer 4

Только некоторые квазианалитические споры:

В вашем наборе чисел, всего одиннадцать, три нечетных и восемь четных.Глядя на простейшие формы хеширования -% 13 - вы получите следующие значения хеш-функции: 10 - 3, 100 - 9, 32 - 6, 45 - 6, 58 - 6, 126 - 9, 3 - 3, 29 - 3, 200 - 5, 400 - 10, 0 - 0

Что, конечно, непригодно из-за количества столкновений.Нужно что-то более сложное.

Зачем указывать очевидное?Учитывая, что числа настолько малы, что любой сложный - или, скорее, «менее простой» - алгоритм, вероятно, будет медленнее, чем либо оператор switch, либо (что я предпочитаю), просто ищущий беззнаковый короткий / длинный вектор с размерами одиннадцати позиций и использующийиндекс совпадения.

Зачем использовать векторный поиск?

1. Точную настройку можно выполнить, поместив наиболее часто встречающиеся значения в начале вектора.
2. Я предполагаю, что цель состоит в том, чтобы включить хеш-индекс в коммутатор с хорошей последовательной нумерацией.В этом свете кажется расточительным сначала использовать переключатель, чтобы найти индекс, а затем подключить его к другому переключателю.Может быть, вам стоит подумать о том, чтобы вообще не использовать хеширование, и перейти непосредственно к последнему ключу?
3. Версия хеширования коммутатора не может быть точно настроена и из-за сильно отличающихся значений заставит компилятор генерировать двоичный файлдерево поиска, которое приведет к множеству сравнений и условных / других переходов (особенно дорогостоящих), которые занимают время (я предположил, что вы обратились к хешированию для его скорости) и требуют места.
4. Если вы хотитечтобы дополнительно ускорить поиск векторов и использовать x86-систему, вы можете реализовать поиск векторов на основе инструкций ассемблера repne scasw (short) / repne scasd (long), что будет намного быстрее.После установки нескольких инструкций вы найдете первую запись в одной инструкции, а последнюю в одиннадцати, а затем очистку нескольких инструкций.Это означает 5-10 инструкций в лучшем случае и 15-20 в худшем случае.Это должно превзойти хэширование на основе коммутатора во всех случаях, кроме одного или двух.

Answer 5

У Боба Дженкинса тоже есть программа для этого: http://burtleburtle.net/bob/hash/perfect.html

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

Answer 6

Попробуйте следующее, которое отображает ваши n значений на уникальные индексы от 0 до 12 (% Тысяча триста шестьдесят-девять (п + 1))% 13

Answer 7

Я сделал быструю проверку и использовал хеш-функцию SHA256, а затем выполнил модульное деление на 13, когда попробовал это в Mathematica. Для c ++ эта функция должна быть в библиотеке openssl. Смотрите этот пост .

Если вы выполняли много операций хеширования и поиска, модульное деление - довольно дорогая операция, которую нужно выполнять многократно. Существует еще один способ отображения n-битной хеш-функции в i-битные индексы. Посмотрите эту запись Майкла Митценмахера о том, как сделать это с помощью операции сдвига битов в C. Надеюсь, это поможет.