Простые хеш-функции

Question

Я пытаюсь написать программу на C, которая использует хеш-таблицу для хранения разных слов, и я мог бы использовать некоторую помощь.

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

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int counter, hashAddress =0;
  for (counter =0; word[counter]!='\0'; counter++){
    hashAddress = hashAddress*word[counter] + word[counter] + counter;
  }
  return (hashAddress%hashTableSize);
}

это просто случайная функция, которую я придумал, но она дает мне лучшие результаты - около 35% столкновений.

Последние несколько часов я читал статьи о хэш-функциях и пытался использовать несколько простых, таких как djb2, но все они дали мне еще худшие результаты (djb2 привел к коллизии 37%, что ' намного хуже, но я ожидал чего-то лучшего, а не худшего) Я также не знаю, как использовать некоторые другие, более сложные, такие как murmur2, потому что я не знаю, какие параметры (key, len Семя) они берут в ан.

Нормально ли получать более 35% коллизий, даже с использованием djb2, или я делаю что-то не так? Каковы ключевые, лен и начальные значения?

Answer 1

Попробуйте SDBM:

hashAddress = 0;
for (counter = 0; word[counter]!='\0'; counter++){
    hashAddress = word[counter] + (hashAddress << 6) + (hashAddress << 16) - hashAddress;
}

Или djb2:

hashAddress = 5381;
for (counter = 0; word[counter]!='\0'; counter++){
    hashAddress = ((hashAddress << 5) + hashAddress) + word[counter];
}

Или Adler32:

uint32_t adler32(const void *buf, size_t buflength) {
     const uint8_t *buffer = (const uint8_t*)buf;

     uint32_t s1 = 1;
     uint32_t s2 = 0;

     for (size_t n = 0; n < buflength; n++) {
        s1 = (s1 + buffer[n]) % 65521;
        s2 = (s2 + s1) % 65521;
     }     
     return (s2 << 16) | s1;
}

// ...

hashAddress = adler32(word, strlen(word));

Однако, все это не очень хорошо. Если вы действительно хотите хорошие хэши, вам нужно что-то более сложное, например lookup3.

Обратите внимание, что ожидается, что в хеш-таблице будет много коллизий, как только она заполнится более чем на 70-80%. Это совершенно нормально и даже произойдет, если вы используете очень хороший алгоритм хеширования. Вот почему большинство реализаций хеш-таблицы увеличивают емкость хеш-таблицы (например, capacity * 1.5 или даже capacity * 2) как только вы добавляете что-то в хеш-таблицу и соотношение size / capacity уже выше 0,7 до 0,8. Увеличение емкости означает, что создается новая хеш-таблица с большей емкостью, все значения из текущего добавляются к новому (поэтому все они должны быть перефразированы, так как их новый индекс будет отличаться в большинстве случаев), новый массив hastable заменяет старый, а старый освобождается / освобождается. Если вы планируете хешировать 1000 слов, емкость хеш-таблицы составляет 1250 наименее рекомендуемых, лучше 1400 или даже 1500.

Hashtables не должны быть "заполнены до краев", по крайней мере, если они должны быть быстрыми и эффективными (таким образом, они всегда должны иметь запасные возможности). Это сокращение хеш-таблиц, они быстрые (O(1)), однако они обычно будут тратить больше места, чем необходимо для хранения тех же данных в другой структуре (когда вы сохраняете их в виде отсортированного массива, вам потребуется только емкость 1000 для 1000 слов; из-за уменьшения размера поиск не может быть быстрее чем O(log n) в таком случае). Хеш-таблица без столкновений в большинстве случаев невозможна. Практически все реализации хеш-таблиц ожидают возникновения коллизий и обычно имеют какой-то способ их устранения (обычно коллизии делают поиск несколько медленнее, но хеш-таблица по-прежнему будет работать и во многих случаях опережать другие структуры данных).

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

x % 4  == x & 3
x % 8  == x & 7
x % 16 == x & 15
x % 32 == x & 31
...

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

Я создал для вас упрощенную реализацию lookup3:

#include <stdint.h>
#include <stdlib.h>

#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

#define mix(a,b,c) \
{ \
  a -= c;  a ^= rot(c, 4);  c += b; \
  b -= a;  b ^= rot(a, 6);  a += c; \
  c -= b;  c ^= rot(b, 8);  b += a; \
  a -= c;  a ^= rot(c,16);  c += b; \
  b -= a;  b ^= rot(a,19);  a += c; \
  c -= b;  c ^= rot(b, 4);  b += a; \
}

#define final(a,b,c) \
{ \
  c ^= b; c -= rot(b,14); \
  a ^= c; a -= rot(c,11); \
  b ^= a; b -= rot(a,25); \
  c ^= b; c -= rot(b,16); \
  a ^= c; a -= rot(c,4);  \
  b ^= a; b -= rot(a,14); \
  c ^= b; c -= rot(b,24); \
}

uint32_t lookup3 (
  const void *key,
  size_t      length,
  uint32_t    initval
) {
  uint32_t  a,b,c;
  const uint8_t  *k;
  const uint32_t *data32Bit;

  data32Bit = key;
  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;

  while (length > 12) {
    a += *(data32Bit++);
    b += *(data32Bit++);
    c += *(data32Bit++);
    mix(a,b,c);
    length -= 12;
  }

  k = (const uint8_t *)data32Bit;
  switch (length) {
    case 12: c += ((uint32_t)k[11])<<24;
    case 11: c += ((uint32_t)k[10])<<16;
    case 10: c += ((uint32_t)k[9])<<8;
    case 9 : c += k[8];
    case 8 : b += ((uint32_t)k[7])<<24;
    case 7 : b += ((uint32_t)k[6])<<16;
    case 6 : b += ((uint32_t)k[5])<<8;
    case 5 : b += k[4];
    case 4 : a += ((uint32_t)k[3])<<24;
    case 3 : a += ((uint32_t)k[2])<<16;
    case 2 : a += ((uint32_t)k[1])<<8;
    case 1 : a += k[0];
             break;
    case 0 : return c;
  }
  final(a,b,c);
  return c;
}

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

Вы бы использовали эту функцию следующим образом:

unsigned int stringToHash(char *word, unsigned int hashTableSize){
  unsigned int initval;
  unsigned int hashAddress;

  initval = 12345;
  hashAddress = lookup3(word, strlen(word), initval);
  return (hashAddress%hashTableSize);
  // If hashtable is guaranteed to always have a size that is a power of 2,
  // replace the line above with the following more effective line:
  //     return (hashAddress & (hashTableSize - 1));
}

Вы задаетесь вопросом, что initval является. Ну, это то, что вы хотите, чтобы это было. Вы могли бы назвать это солью. Это повлияет на значения хеш-функции, однако значения хеш-функции не будут улучшаться или ухудшаться по качеству из-за этого (по крайней мере, не в среднем случае, это может привести к большему или меньшему количеству коллизий для очень специфических данных). Например, вы можете использовать разные initval значения, если вы хотите хешировать одни и те же данные дважды, но каждый раз должен выдавать разные значения хеша (нет никаких гарантий, что это произойдет, но, скорее всего, если initval это отличается; если он создает то же значение, это будет очень неудачное совпадение, что вы должны рассматривать это как своего рода столкновение). Не рекомендуется использовать разные initval значения при хешировании данных для одной и той же хеш-таблицы (это скорее вызовет больше коллизий в среднем). Другое использование для initval - если вы хотите объединить хеш с некоторыми другими данными, в этом случае уже существующий хеш становится initval при хешировании других данных (так что и другие, и предыдущие хеш-данные влияют на результат хеш-функции). Вы можете даже установить initval в 0 если вам нравится или выбирается случайное значение при создании хеш-таблицы (и всегда используйте это случайное значение для этого экземпляра хеш-таблицы, но каждая хеш-таблица имеет свое случайное значение).

Примечание о столкновениях:

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

Вы сказали, что имеете дело с 9000 слов. Если вы использовали несортированный массив, для поиска слова в массиве потребуется в среднем 4500 сравнений. В моей системе для 4500 сравнений строк (при условии, что длина слов составляет от 3 до 20 символов) требуется 38 микросекунд (0,000038 секунд). Так что даже такой простой, неэффективный алгоритм достаточно быстр для большинства целей. Предполагая, что вы сортируете список слов и используете бинарный поиск, для поиска слова в массиве потребуется в среднем только 13 сравнений. 13 сравнений с точки зрения времени близки к нулю, это слишком мало, чтобы даже надежно сравнивать. Поэтому, если для поиска слова в хеш-таблице требуется от 2 до 4 сравнений, я бы не стал тратить ни секунды на вопрос, может ли это быть огромной проблемой производительности.

В вашем случае отсортированный список с бинарным поиском может даже превзойти хеш-таблицу. Конечно, 13 сравнений требуют больше времени, чем 2-4 сравнения, однако в случае хеш-таблицы вы должны сначала хешировать входные данные, чтобы выполнить поиск. Одно только хэширование может занять более 13 сравнений! Чем лучше хеш, тем больше времени потребуется для хеширования того же объема данных. Таким образом, хеш-таблица окупается только с точки зрения производительности, если у вас действительно огромный объем данных или если вы должны часто обновлять данные (например, постоянно добавлять / удалять слова в / из таблицы, поскольку эти операции обходятся дешевле для хеш-таблицы, чем они для отсортированного списка). Тот факт, что O(1) только означает, что независимо от того, насколько он велик, поиск будет ок. всегда нужно одинаковое количество времени. O(log n) только означает, что поиск растет логарифмически с количеством слов, что означает больше слов, медленный поиск. Тем не менее, запись Big-O ничего не говорит об абсолютной скорости! Это большое недоразумение. Не сказано, что O(1) Алгоритм всегда работает быстрее, чем O(log n) один. Обозначение Big-O говорит только о том, что если O(log n) Алгоритм быстрее для определенного числа значений, и вы продолжаете увеличивать количество значений, O(1) алгоритм наверняка настигнет O(log n) алгоритм в некоторый момент времени, но ваш текущий счетчик слов может быть намного ниже этой точки. Без сравнения обоих подходов вы не можете сказать, какой из них быстрее, просто взглянув на нотацию Big-O.

Вернуться к столкновениям. Что делать, если вы столкнулись с столкновением? Если количество коллизий мало, и здесь я имею в виду не общее количество коллизий (количество слов, которые сталкиваются в хеш-таблице), а количество, указанное в индексе (количество слов, хранящихся в том же хеш-таблице, поэтому в вашем случае может быть 2-4), самый простой подход - хранить их как связанный список. Если пока для этого индекса таблицы не было коллизий, существует только одна пара ключ / значение. Если произошло столкновение, существует связанный список пар ключ / значение. В этом случае ваш код должен перебирать связанный список, проверять каждый из ключей и возвращать значение, если оно совпадает. Судя по вашим номерам, в этом связанном списке будет не более 4 записей, а выполнение 4 сравнений незначительно с точки зрения производительности. Таким образом, нахождение индекса O(1)нахождение значения (или обнаружение того, что этот ключ отсутствует в таблице) O(n), но здесь n только количество записей в связанном списке (максимум 4).

Если количество столкновений возрастает, связанный список может стать медленным, и вы также можете хранить динамически отсортированный массив пар ключ / значение, что позволяет искать O(log n) и опять, n это только количество ключей в этом массиве, а не всех ключей в таблице. Даже если в одном индексе было 100 столкновений, для поиска правильной пары ключ / значение требуется не более 7 сравнений. Это все еще почти ничего. Несмотря на то, что если у вас действительно 100 коллизий в одном индексе, либо ваш алгоритм хеширования не подходит для ваших ключевых данных, либо хеш-таблица слишком мала по емкости. Недостаток отсортированного массива динамического размера состоит в том, что добавление / удаление ключей несколько более трудоемко, чем в случае связанного списка (с точки зрения кода, не обязательно с точки зрения производительности). Поэтому использование связанного списка обычно достаточно, если вы сохраняете количество коллизий достаточно низким, и практически тривиально реализовать такой связанный список самостоятельно в C и добавить его в существующую реализацию с хеш-таблицами.

Мне кажется, что в большинстве реализаций хеш-таблиц такой "запасной вариант альтернативной структуры данных" используется для устранения коллизий. Недостатком является то, что для них требуется немного дополнительной памяти для хранения альтернативной структуры данных и немного больше кода для поиска ключей в этой структуре. Существуют также решения, которые хранят коллизии внутри самой хеш-таблицы и не требуют дополнительной памяти. Однако эти решения имеют пару недостатков. Первый недостаток заключается в том, что каждое столкновение увеличивает шансы на еще большее количество столкновений по мере добавления большего количества данных. Второй недостаток заключается в том, что, хотя время поиска ключей уменьшается линейно с ростом количества коллизий (и, как я уже говорил, каждое коллизия приводит к еще большему коллизии при добавлении данных), время поиска ключей, не включенных в хеш-таблицу, уменьшается еще хуже и, в конце концов, если вы выполняете поиск ключа, которого нет в хеш-таблице (но вы не можете узнать, не выполнив поиск), поиск может занять столько же времени, сколько и линейный поиск по всей хеш-таблице (YUCK!!!), Поэтому, если вы можете сэкономить дополнительную память, используйте альтернативную структуру для обработки коллизий.

Answer 2

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

...

return (hashAddress% hashTableSize);

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

Я сделал простой статистический тест со случайным хешем (это лучшее, что вы могли бы достичь) и обнаружил, что 26% - это ограниченная частота столкновений, если у вас есть #words == #different хэши.