Насколько вероятно столкновение HashCode с этой функцией хэш-кода? - PullRequest
Новая
       8

Насколько вероятно столкновение HashCode с этой функцией хэш-кода?

5 голосов
/ 17 марта 2011

Какова вероятность получения коллизии HashCode с функцией ниже в следующих сценариях:

  1. Со случайными значениями int для ключа [0], ключа [1], ключа [2], ключа[3]
  2. со случайными значениями ключей со следующими ограничениями
    • ключ [0] <1 000 000 </li>
    • ключ [1] <10 000 </li>
    • ключ [2] <1000 </li>
    • ключ [3] <1000 </li>

Предположим, у нас есть 10 миллионов объектов. 

int[] key=new int[4];    
public override int GetHashCode()
{
    // Use large prime multiples to create a unique hash key
    // Create the hash offsets using a "even powers of 2 minus 1" method, which gives 
    // primes most of the time.  
    int hashKey = 0;
    hashKey += 2047 * key[0];
    hashKey += 8191 * key[1];
    hashKey += 32767 * key[2];
    hashKey += 131071 * key[3];
    return hashKey;
}

Ответы [ 3 ]

9 голосов
/ 17 марта 2011

Это довольно странный вопрос. Начнем с очевидных ошибок в коде: 

// Use large prime multiples to create a unique hash key     
// Create the hash offsets using a "even powers of 2 minus 1" method, which gives      
// primes most of the time.

Во-первых, это все странные силы двух минус один; ни одна из них не является степенью двух минус один.

Во-вторых, из четырех множителей, выбранных вами как «большие простые множители», половина из них не является простым числом. 2047 и 32767 являются составными.

В-третьих, если мы "исправим" - и я буду использовать слово с осторожностью - утверждение будет "нечетными степенями 2 минус единица, которая дает простые числа большую часть времени", то это утверждение абсурдно неверно , Простое число этой формы известно как простое число Мерсенна, и есть только 47 известных простых чисел Мерсенна . Уверяю вас, плотность простых чисел Мерсенна значительно меньше половины. Скажем так: из нечетных чисел Мерсенна между 2 ^ 1-1 и 2 ^ 43112609−1 известно, что 46 из них являются простыми числами, что составляет примерно один на полмиллиона, а не половину.

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

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

В-шестых, предположим, что у вашей хеш-функции было совершенно случайное распределение по пространству 32-битных целых чисел. К «парадоксу» дня рождения вы ожидаете, что вероятность по крайней мере одного столкновения будет гораздо больше, чем 99%, при случайном рисовании десяти миллионов чисел из 32-битного пространства. На самом деле, ожидаемое количество столкновений будет порядка десяти или двадцати тысяч. (Мы могли бы определить точное число ожидаемых столкновений, но кого волнует, что это такое; это в таком порядке.)

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

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

Меня очень смущает этот вопрос и то, что вы надеетесь получить от его ответа. Вы можете объяснить?

4 голосов
/ 17 марта 2011

Я написал быстрый скрипт для проверки этого. 

import random

def hash(key):
    hashKey = 0
    hashKey += 2047 * key[0]
    hashKey += 8191 * key[1]
    hashKey += 32767 * key[2]
    hashKey += 131071 * key[3]
    return hashKey

seen = set()
collisions = 0
for i in range(0,10000000):
    x = hash([random.randint(0,1000000), random.randint(0,10000), random.randint(0,1000), random.randint(0,1000)])
    if x in seen:
        collisions += 1
    else:
        seen.add(x)

print collisions

Когда я его запустил, мне сказали, что я столкнулся с 23735 столкновениями. Я также попробовал это на одном миллионе элементов, и я получил 247 столкновений. Оба числа являются средними за 4 прогона.

2 голосов
/ 17 марта 2011

Я собирался сказать, что вы должны использовать 

int hashKey = key[0].GetHashCode();
hashKey ^= key[1].GetHashCode();
hashKey ^= key[2].GetHashCode();
hashKey ^= key[3].GetHashCode();

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

Collisions1 - ваш метод, Collisions2 - мой метод, это результаты 4 прогонов 

Collisions1: 23744
Collisions2: 8996107

Collisions1: 23825
Collisions2: 8996215

Collisions1: 23771
Collisions2: 8996119

Collisions1: 24031
Collisions2: 8996157
...