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

Question

Я довольно новичок в хешировании в Java и застрял на нескольких частях. У меня есть список из 400 предметов (и хранится в списке 1,5x = 600), диапазон идентификаторов предметов которого составляет 1-10k. Я смотрел на несколько хеш-функций, и я сначала скопировал примеры в пакете, который просто использовал свертывание. Я заметил, что я получаю около 50-60% нулевых узлов, что, по-видимому, слишком много. Я также заметил, что простое изменение идентификатора на 600 приводит к снижению значения до 50%.

Моя текущая хеш-функция выглядит примерно так, и, несмотря на то, что она такая уродливая, она только уменьшает значение NULL на 1% по сравнению с простым моддингом со средней длиной списка 1,32 ...

   public int getHash( int id )
   {
      int hash = id;

      hash <<= id % 3;
      hash += id << hash % 5;

      /* let's go digit by digit! */          
      int digit;
      for( digit = id % 10;
           id != 0;
           digit = id % 10, id /= 10 )
      {
         if ( digit == 0 ) /* prevent division by zero */
            continue;
         hash += digit * 2;
      }

      hash >>= 5;
      return (hash % 600);
   }

Какие хорошие методы для создания простых хеш-функций?

Answer 1

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

Java HashMap использует следующий метод перефразировки:

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Answer 2

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