В книге «Численные рецепты» предлагается метод вычисления 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 ключей), это, вероятно, будет приемлемым.

ТИА!