Вероятность столкновения 64-битного хеш-кода

Question

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

ТИА!

Answer 1

Существует ли формула для оценки вероятности столкновений с учетом так называемого парадокса дня рождения?

Использование формулы "Парадокс дня рождения" просто говорит о том, в какой момент вам нужно начать беспокоиться о случившемся столкновении. Это около Sqrt[n] где n это общее количество возможных значений хеша. В этом случае n = 2^64 поэтому формула "Парадокс дня рождения" говорит вам, что до тех пор, пока число ключей значительно меньше Sqrt[n] = Sqrt[2^64] = 2^32 или примерно 4 миллиарда, вам не нужно беспокоиться о столкновениях. Чем выше nТем точнее эта оценка. На самом деле вероятность p(k) что столкновение произойдет с k клавиши приближаются к ступенчатой ​​функции как n становится больше, где шаг происходит в k=Sqrt[n],

---

Можете ли вы оценить вероятность столкновения (т. Е. Два ключа, которые хешируют одно и то же значение)? Скажем, с 1000 ключей и с 10 000 ключей?

Предполагая, что хеш-функция равномерно распределена, легко получить формулу.

p(no collision for k keys) = 1 * (n-1)/n * (n-2)/n * (n-3)/n * ... * (n-(k-1))/n

Эта формула непосредственно следует из начала с 1 ключа: вероятность отсутствия столкновения с 1 ключом, конечно, равна 1. Вероятность отсутствия столкновения с 2 ключами равна 1 * (n-1)/n, И так далее для всех k ключи. Для удобства Mathematica имеет функцию Pochhammer[], чтобы выразить это кратко:

p(no collision for k keys) = Pochhammer[n-(k-1),k]/n^k

Затем, чтобы рассчитать вероятность того, что есть как минимум 1 столкновение для k ключи, вычтите это из 1:

p(k) = 1 - p(no collision for k keys) = 1 - Pochhammer[n-(k-1),k]/n^k

Используя Mathematica, можно рассчитать для n=2^64:

• р (1000) = 1 из 3,7 * 10¹³
• р (10000) = 1 из 3,7 * 10¹¹
• р (1 000 000) = 1 из 3,7 * 10⁷

---

Можно ли предположить, что столкновение разумного количества ключей (скажем, менее 10 000 ключей) настолько маловероятно, что, если 2 хеш-кода одинаковы, мы можем сказать, что ключи одинаковы без какой-либо дополнительной проверки?

Чтобы ответить на этот вопрос точно зависит от вероятности того, что 2 из 10 000 ключей были идентичны. Что мы ищем это:

p(a=b|h(a)=h(b)) = The probability that a=b given h(a)=h(b)

где a а также b являются ключами (возможно идентичными) и h() это функция хеширования. Мы можем применить теорему Байеса напрямую:

p(a=b|h(a)=h(b)) = p(h(a)=h(b)|a=b) * p(a=b) / p(h(a)=h(b))

Мы сразу видим, что p(h(a)=h(b)|a=b) = 1 (если a=b тогда конечно h(a)=h(b)) так мы получаем

p(a=b|h(a)=h(b)) = p(a=b) / p(h(a)=h(b))

Как вы можете видеть, это зависит от p(a=b) что является вероятностью того, что a а также b на самом деле один и тот же ключ. Это зависит от того, как группа из 10000 ключей была выбрана в первую очередь. Расчеты для двух предыдущих вопросов предполагают, что все ключи различны, поэтому для полного ответа на этот сценарий требуется дополнительная информация.

Answer 2

Я приведу грубое приближение к точным формулам, приведенным в других ответах; аппроксимация может помочь вам ответить на вопрос № 3. Грубая аппроксимация заключается в том, что вероятность столкновения с k ключами и n возможными значениями хеш-функции с хорошим алгоритмом хеширования составляет приблизительно (k^2)/2n, для k << n. Для 100 000 ключей с 64-битным хешем это 10^10 / 32x10^18 или около 1 на 3 миллиарда.

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

Answer 3

Существует ли формула для оценки вероятности столкновений с учетом так называемого парадокса дня рождения?

Смотрите: Атака на день рождения.

Предполагая, что распределение хэшей является равномерным, вероятность столкновения для n ключей примерно n 2/2 ⁶⁵.

Можно ли предположить, что столкновение разумного количества ключей (скажем, менее 10000 ключей) настолько маловероятно, что, если два хэш-кода различны, мы можем сказать, что ключи различны без какой-либо дополнительной проверки?

Это безопасно только при использовании криптографической хеш-функции. Даже если вы можете допускать ошибку каждые 3 * 10 ¹¹ раз, вам, возможно, придется рассмотреть возможность того, что вход специально создан для создания коллизии хешей, как атаку на вашу программу.

Answer 4

1) Существует ли формула для оценки вероятности столкновений с учетом так называемого парадокса дня рождения?

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

x = hash size
p(k=2) = (x-1)/x
p(k=3) = p(k=2)*(x-2)/x
..
p(k=n) = (x-1)*(x-2)..(x-n+1)/x^n

p(k=n) ~ e^-(n*n)/2x

p(collision|k=n) = 1-p(k=n) = 1 - e^(-n^2)/2x
p(collision) > 0.5 if n ~ sqrt(x)

Следовательно, если sqrt(2^64) ключи это 2^32 Ключ генерируется, есть более высокая вероятность того, что есть одно столкновение.

2) Можете ли вы оценить вероятность столкновения (т. Е. Два ключа, которые хешируют одно и то же значение)? Скажем, с 1000 ключей и с 10 000 ключей?

x = 2^64 
Use the formula pc(k=n) = 1 - e^-(n^2)/2x

3) Можно ли предположить, что столкновение разумного количества ключей (скажем, менее 10 000 ключей) настолько маловероятно, что, если 2 хеш-кода одинаковы, мы можем сказать, что ключи одинаковы без какой-либо дальнейшей проверки?

Это очень интересный вопрос, потому что он зависит от размера ключевого пространства. Предположим, что ваши ключи генерируются случайным образом из пространства size = s и хэш-пространство x=2^64 как вы упомянули. Вероятность столкновения Pc(k=n|x) = 1-e^(-n^2)/2x, Если вероятность выбора того же ключа в пространстве ключей P(k=n|s) = 1-e^(-n^2)/2s, Чтобы быть уверенным, что если хеш-код одинаков, ключи одинаковы:

P(k=n|s) > Pc(k=n|x)
1-e^-(n^2/2s) > 1-e^-(n^2/2x) 
n^2/2s > n^2/2x 
s < x
s < 2^64

Следовательно, это показывает, что для того, чтобы ключи были одинаковыми, если хеш одинаков, размер набора ключей должен быть меньше 2^64 в противном случае вероятность хэширования в хэше больше, чем в наборе ключей. Результат не зависит от количества сгенерированных ключей.