хэш-функция для строк

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

во-вторых, вы хотите убедиться, что каждый бит ввода может/будет влиять на результат. Один простой способ сделать это-повернуть текущий результат на некоторое количество бит, а затем XOR текущий хэш-код с текущим байтом. Повторяйте, пока не дойдете до конца из строки. Обратите внимание, что вы обычно делаете не хотите, чтобы вращение было четным кратным размеру байта.

например, предполагая общий случай 8-битных байтов, вы можете повернуть на 5 бит:

int hash(char const *input) { 
    int result = 0x55555555;

    while (*input) { 
        result ^= *input++;
        result = rol(result, 5);
    }
}

Edit: Также обратите внимание, что 10000 слотов редко является хорошим выбором для размера хэш-таблицы. Обычно вам нужно одно из двух: вы либо хотите простое число в качестве размера (требуется для обеспечения правильности с некоторыми типами разрешения хэша), либо мощность 2 (поэтому уменьшение значения до правильного диапазона можно сделать с помощью простой битовой маски).

существует ряд существующих реализаций hashtable для C, от стандартной библиотеки C hcreate/hdestroy / hsearch, до тех, что находятся в APR и glib, которые также предоставляют готовые хэш-функции. Я бы настоятельно рекомендовал использовать их, а не изобретать свою собственную хэш-таблицу или хэш-функцию; они были сильно оптимизированы для общих случаев использования.

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

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

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

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

хэш-функция с хорошей репутацией-это MurmurHash3.

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

Я пробовал эти хэш-функции и получил следующий результат. У меня есть около 960^3 записей, каждая длиной 64 байта, 64 символа в другом порядке, хэш-значение 32 бит. Коды от здесь.

Hash function  |  collision rate | how many minutes to finish
MurmurHash3    |    6.?%         |       4m15s
Jenkins One..  |    6.1%         |       6m54s   
Bob, 1st in link|   6.16%        |       5m34s
SuperFastHash  |    10%          |       4m58s
bernstein      |    20%          | 14s only finish 1/20
one_at_a_time  |    6.16%        |       7m5s
crc            |    6.16%        |       7m56s

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

хотя djb2, а представлено на stackoverflow от cnicutar, почти наверняка лучше, я думаю, что это стоит показать K&R хэши тоже:

1) видимо a Грозный хэш-алгоритм, представленный в K&R 1st edition (источник)

unsigned long hash(unsigned char *str)
{
    unsigned int hash = 0;
    int c;

    while (c = *str++)
        hash += c;

    return hash;
}

2) вероятно, довольно приличный алгоритм хэша, как представлено в версии K&R 2 (проверено мной на стр. 144 книги); Примечание: обязательно удалить % HASHSIZE из оператора return, если вы планируете выполнять модульную калибровку по длине массива вне алгоритма хэша. Кроме того, я рекомендую вам сделать возврат и тип "hashval"unsigned long вместо простого unsigned (int).

unsigned hash(char *s)
{
    unsigned hashval;

    for (hashval = 0; *s != ''; s++)
        hashval = *s + 31*hashval;
    return hashval % HASHSIZE;
}

обратите внимание, что из двух алгоритмов ясно, что одна из причин, по которой хэш 1-го издания настолько ужасен, заключается в том, что он не учитывает строковый символ заказ, так что будет возвращает то же значение, что и hash("ba"). Это не так что с хэшем 2-го издания, однако, который был бы (намного лучше!) возвращает два разных значения для этих строк.

функции хэширования GCC C++11, используемые для unordered_map (шаблон хэш-таблицы) и unordered_set (шаблон набора хэшей) выглядит следующим образом.

• этой - это частичный ответ на вопрос что в GCC C++11 используются хэш-функции, заявив, что GCC использует реализацию "MurmurHashUnaligned2", Остин Эпплби (http://murmurhash.googlepages.com/).
• в файле "gcc / libstdc++ - v3 / libsupc++/hash_bytes.cc", здесь (https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc), я нашел реализации. Вот один для" 32-битного size_t " возвращаемого значения, например (вытащил 11 августа 2017):

код:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

одна вещь, которую я использовал с хорошими результатами, заключается в следующем (я не знаю, упоминалось ли это уже, потому что я не могу вспомнить его имя).

вы предварительно вычисляете таблицу T со случайным числом для каждого символа в алфавите вашего ключа [0,255]. Вы хэш-ключ 'К0 К1 К2 ... кн, взяв Т[К0] гаммирования Т[К1] гаммирования ... исключающее Т[кн]. Вы можете легко показать, что это так же случайно, как ваш генератор случайных чисел, и его вычислительно очень возможно, и если вы действительно столкнетесь с очень плохим экземпляром с большим количеством столкновений, вы можете просто повторить все это, используя свежую партию случайных чисел.