Вероятность столкновения 64-битного хеш-кода
В книге «Численные рецепты» предлагается метод вычисления 64-битных хеш-кодов с целью уменьшения количества коллизий.
Алгоритм показан наhttp://www.javamex.com/tutorials/collections/strong_hash_code_implementation_2.shtml и скопирован сюда для справки:
private static final createLookupTable() {
byteTable = new long[256];
long h = 0x544B2FBACAAF1684L;
for (int i = 0; i < 256; i++) {
for (int j = 0; j < 31; j++) {
h = (h >>> 7) ^ h;
h = (h << 11) ^ h;
h = (h >>> 10) ^ h;
}
byteTable[i] = h;
}
return byteTable;
}
public static long hash(CharSequence cs) {
long h = HSTART;
final long hmult = HMULT;
final long[] ht = byteTable;
final int len = cs.length();
for (int i = 0; i < len; i++) {
char ch = cs.charAt(i);
h = (h * hmult) ^ ht[ch & 0xff];
h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
}
return h;
}
Мои вопросы:
1) Существует ли формула для оценки вероятности столкновений с учетом так называемого парадокса дня рождения?
2) Можете ли вы оценить вероятность столкновения (то есть два ключа, которые хешируют одно и то же значение)? Скажем, с 1000 ключей и с 10 000 ключей?
РЕДАКТИРОВАТЬ: перефразированный / исправленный вопрос 3
3) Можно ли предположить, что столкновение разумного количества ключей (скажем, менее 10 000 ключей) настолько маловероятно, что, если 2 хеш-кода совпадают, мы можем сказать, что ключи одинаковы без какой-либо дальнейшей проверки? например
static boolean equals(key1, key2) {
if (key1.hash64() == key2.hash64())
return true; // probability of collision so low we don't need further check
return false;
}
Это не для безопасности, но скорость выполнения является обязательной, поэтому избежание дальнейших проверок ключей сэкономит время. Если вероятность настолько мала, скажем, меньше (1 на 1 миллиард на 100 000 ключей), это, вероятно, будет приемлемым.
ТИА!