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

Я пытаюсь написать программу 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, потому что я не знаю, какие параметры (ключ, len, seed) они принимают.

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

Ответ 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 array заменяет старый, а старый освобождается/освобождается. Если вы планируете хешировать 1000 слов, емкость хэш-таблицы в 1250 наименее рекомендуется, лучше 1400 или даже 1500.

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

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

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

Это работает только для мощности 2-х размеров. Если вы используете modulo, мощность 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 сравнений! Чем лучше хэш, тем дольше будет хватать один и тот же объем данных. Таким образом, хэш-таблица только окупается по производительности, если у вас действительно огромный объем данных или если вы должны часто обновлять данные (например, постоянно добавляя/удаляя слова в/из таблицы, так как эти операции менее дорогостоящие для хэш-таблицы, чем они для отсортированного списка). Тот факт, что hashatble O(1) означает только то, что независимо от того, насколько он большой, поиск будет ок. всегда требуется такое же количество времени. O(log n) означает, что поиск растет логарифмически с количеством слов, что означает больше слов, более медленный поиск. Но нотация Big-O ничего не говорит об абсолютной скорости! Это большое недоразумение. Не сказано, что алгоритм O(1) всегда выполняет быстрее, чем a 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 - это только количество ключей в этом массиве, а не всех клавиш в hastable. Даже если было 100 столкновений по одному индексу, поиск правой пары ключ/значение занимает не более 7 сравнений. Это все еще близко ни к чему. Несмотря на то, что если у вас действительно 100 столкновений по одному индексу, либо ваш хэш-алгоритм не подходит для ваших ключевых данных, либо хэш-таблица слишком мала по мощности. Недостатком сортированного массива с динамическим размером является то, что добавление/удаление ключей несколько больше, чем в случае связанного списка (по коду, не обязательно по производительности). Поэтому использование связанного списка обычно является достаточным, если вы сохраняете количество столкновений достаточно низкими, и почти тривиально реализовать такой связанный список самостоятельно на C и добавить его к существующей реализации хэш-таблицы.

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

Ответ 1

Ответ 2