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

Ответ 1

Найдено один

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

(n ^ 28) % 13

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

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

Ответ 2

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

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

Ответ 3

На некоторых платформах (например, вложенных) операция modulo стоит дорого, поэтому % 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()

Ответ 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 или (что я предпочитаю), просто просматривая беззнаковый короткий/длинный вектор размером одиннадцать позиций и используя индекс матча.

Зачем нужен векторный поиск?

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

Ответ 5

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

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

Ответ 6

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

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

Ответ 7

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