семейство бинарных хеш-функций - PullRequest
Новая
       12

семейство бинарных хеш-функций

1 голос
/ 01 июля 2010

Я ищу семейство хэш-функций F1, .. Fn, где каждый Fi отображает любую клавишу в [0,1]. Моей первой реализацией было Fi (k) = F (k, i) = hash (i, hash (k, 0)) ,. Здесь hash - это функция hashlittle, представленная здесь (http://burtleburtle.net/bob/c/lookup3.c). Я не смотрел под капотом того, что делает hashlittle.

Как проницательные читатели заметили бы, это потерпит неудачу. У меня вопрос, как этого добиться эффективно. Моя цель состоит в том, чтобы минимизировать, в среднем, наибольшее значение i, для которого Fi (k1) == Fi (k2) для любой данной пары k1, k2. Конечно, это тоже должно быть быстро ..

1 Ответ

3 голосов
/ 01 июля 2010

Ну, я немного заглянул под капот. 

uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
{
  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */

  u.ptr = key;
  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {

Запись u.ptr, а затем чтение пользовательского интерфейса - неопределенное поведение.

РЕДАКТИРОВАНИЕ

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

Хеш-функция принимает пакет данных произвольного размера в битах и ​​преобразует его в пакет данных фиксированного размера: 

hashval = Hash(data, len);

Вам нужна функция, в которой задан дополнительный параметри используется в преобразовании, верно? 

hashval = Hash(data, len, addval);

Самый простой способ - объединить дополнительные значения с пакетом данных: 

memcpy((char *)data + len, &addval, sizeof(addval));
hashval = Hash(data, len + sizeof(addval));

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

Before:
uint32_t Hash (const void *data, size_t len)
{
    uint32_t hashval = 0;
    ....
    return (hashval);
}

After:
uint32_t Hash (const void *data, size_t len, uint32_t init)
{
    uint32_t hashval = init;
    ....
    return (hashval);
}

Этот параметр может быть немного сложнее сделать, так как внутреннее состояние может быть намного больше, чем один hashval, и инициализация может быть довольно сложной, а не простоиспользуя 0. В hashlittle это: 

/* Set up the internal state */
a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
...