Идеальная хэш-функция для удобочитаемых кодов заказа

Question

Я пытаюсь сгенерировать непоследовательные читаемые человеком порядковые коды, полученные из (скажем,) 32-битного внутреннего беззнакового идентификатора, который начинается с 1 и автоматически увеличивается для каждого нового заказа.будет ли каждый $hash уникальным?(Я планирую с помощью base34 кодировать $hash, чтобы сделать его читабельным для человека.)

<?php
function int_hash($key) {
  $key = ($key^0x47cb8a8c) ^ ($key<<12);
  $key = ($key^0x61a988bc) ^ ($key>>19);
  $key = ($key^0x78d2a3c8) ^ ($key<<5);
  $key = ($key^0x5972b1be) ^ ($key<<9);
  $key = ($key^0x2ea72dfe) ^ ($key<<3);
  $key = ($key^0x5ff1057d) ^ ($key>>16);
  return $key;
}

for($order_id = 1; $order_id <= PHP_INT_MAX; ++$order_id) {
  $hash = int_hash($order_id);
}
?>

Если нет, есть ли какие-либо предложения по замене int_hash?

скажем, кодировка base34 md5($order_id) слишком длинна для меня.

Answer 1

В моем примере кода ниже каждый $hash будет уникальным?

Почти. (Что, я думаю, означает "нет, но вэто легко исправить ".) Ваша функция состоит из последовательности независимых шагов;общая функция является биективной (обратимой) тогда и только тогда, когда каждый из этих шагов является.(Вы понимаете, почему?)

Теперь каждый шаг имеет одну из следующих форм:

  $key = ($key ^ CONSTANT) ^ ($key >> NUM_BITS);
  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

с NUM_BITS != 0.

На самом деле мы можем рассматривать их какварианты одной формы, рассматривая первый как почти эквивалентный этому:

  $key = invert_order_of_bits($key); # clearly bijective
  $constant = invert_order_of_bits(CONSTANT);
  $key = ($key ^ $constant) ^ ($key << NUM_BITS);
  $key = invert_order_of_bits($key); # clearly bijective

Итак, все, что нам нужно, это показать, что это:

  $key = ($key ^ CONSTANT) ^ ($key << NUM_BITS);

является биективным.Теперь XOR является коммутативным и ассоциативным, поэтому вышеприведенное эквивалентно этому:

  $key = $key ^ ($key << NUM_BITS);
  $key = $key ^ CONSTANT;

и (x ^ y) ^ y == x ^ (y ^ y) == x ^ 0 == x, поэтому ясно, что XOR с постоянным значением является обратимым (путем повторного XOR содинаковое значение);так что все, что мы должны показать, это то, что это биективно:

  $key = $key ^ ($key << NUM_BITS);

всякий раз, когда NUM_BITS != 0.

Теперь я не пишу строгое доказательство, поэтому я просто дам single аргументированный пример того, как это изменить.Предположим, что $key ^ ($key << 9) равно

0010 1010 1101 1110 0010 0101 0000 1100

Как мы можем получить $key?Итак, мы знаем, что последние девять битов $key << 9 - все нули, поэтому мы знаем, что последние девять битов $key ^ ($key << 9) совпадают с последними девятью битами $key.Итак, $key выглядит как

bbbb bbbb bbbb bbbb bbbb bbb1 0000 1100

, поэтому $key << 9 выглядит как

bbbb bbbb bbbb bb10 0001 1000 0000 0000

, поэтому $key выглядит как

bbbb bbbb bbbb bb00 0011 1101 0000 1100

(автор XOR-ing$key ^ ($key << 9) с $key << 9), поэтому $key << 9 выглядит как

bbbb b000 0111 1010 0001 1000 0000 0000

, поэтому $key выглядит как

bbbb b010 1010 0100 0011 1101 0000 1100

так $key << 9 выглядит как

0101 1000 0111 1010 0001 1000 0000 0000

так $key выглядит как

0111 0010 1010 0100 0011 1101 0000 1100

Итак.,,почему я говорю «почти», а не «да»?Почему ваша хеш-функция не является идеально биективной?Это связано с тем, что в PHP операторы побитового сдвига >> и << не являются вполне симметричными, и хотя $key = $key ^ ($key << NUM_BITS) является полностью обратимым, $key = $key ^ ($key >> NUM_BITS) - нет.(Выше, когда я писал, что два типа шагов были " почти эквивалентными", я действительно имел в виду , что "почти". Это имеет значение!) Вы видите, тогда как << обрабатывает знаковый бит точно так же, как любой другой бит, и вытесняет его из существования (вводит нулевой бит справа), >> обрабатывает знаковый бит специально и «расширяет» его: бит, который он вводитслева равен знаковый бит.(NB В вашем вопросе упоминаются 32-битные значения без знака, но PHP фактически не поддерживает это; его побитовые операции всегда выполняются на знаковых целых числах.)

Из-за этого расширения знака, если $key начинается с 0, затем $key >> NUM_BITS начинается с 0, а если $key начинается с 1, то $key >> NUM_BITS также начинается с 1.В любом случае $key ^ ($key >> NUM_BITS) начнется с 0.Вы потеряли ровно один бит энтропии.Если вы дадите мне $key ^ ($key >> 9) и не скажете, является ли $key отрицательным, то лучшее, что я могу сделать, - это вычислить два возможных значения для $key: одно отрицательное, одно положительное или нулевое.

Вы выполняете два шага, которые используют сдвиг вправо вместо сдвига влево, поэтому вы теряете два бита энтропии.(Я слегка машу рукой - все, что я на самом деле продемонстрировал, это то, что вы теряете как минимум один бит и максимум два бита - но я уверен, что из-захарактер шагов между этими шагами правого смещения, вы фактически теряете два полных бита.) Для любого заданного выходного значения есть ровно четыре различных входных значения, которые могут его получить.Так что это не уникально, но почти уникально;и это легко исправить, либо:

• изменив два шага вправо, чтобы вместо него использовать левое;или
• перемещая оба шага сдвига вправо в начало функции, перед любыми шагами сдвига влево, и говоря, что выходы уникальны для входов от 0 до 2 ³¹ −1а не входы между 0 и 2 ³² -1.