Облегченный вариант Guid'а

История

Использование Guid как идентификаторов всего и вся стало обычным делом в последнее время. Однако он занимает 16 байт при хранении в двоичном виде и целых 36 символов в привычном строковом представлении 931529A7-E79C-4691-B136-91E668BCEA74.

Проблема

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

Решение

Длинные и громоздкие гуиды можно заменить облегченной версией. Например, 2 байта - хэш текущего времени и 4 байта из генератора случайных чисел. Получается 2^48 чисел. Это конечно не 2^128, которые дает Guid (считая версию генератора записанную в гуид как увеличивающую количество его значений). Но для задач, когда общее количество объектов измеряется миллионами или миллиардами, получается вполне достаточно. Например, даже когда мы уже создали 2^20 или 1048576 чисел, вероятность коллизии все еще 1/2^28. Чтобы вероятность коллизии приблизилась к 1%, нужно создать по крайней мере 2^41 идентификатор.
Получается что 6-ти байтового локально уникального идентификатора вполне достаточно для задач, когда не требуется глобальная уникальность в любой точке пространства и времени. Кстати, MAC-адреса довольствуются как раз 6-ти байтами. Это позволяет хранить 6-ти байтовые Luid (Locally Unique IDentifier) как mac-адреса в базах данных вроде PostgreSQL. Он же подсказывает возможные строковые представления:

'08:00:2b:01:02:03'
'08-00-2b-01-02-03'
'08002b:010203'
'08002b-010203'
'0800.2b01.0203'
'08002b010203'

Сравните:

552DFCFA-332B-4707-B5C9-C439F69FB2E7 / 25B952DB-C6B4-4D9D-95CA-EF49A789C5F2 / 475301DC-1712-4B4C-8D2C-13AAEE4202CA

и

552D.FCFA.332B / 25B9.52DB.C6B4 / 4753.01DC.1712

Апдейт:
6-ти байтовый идентификаторы еще очень удобно кодировать в base64. Получается ровно 8 символов без паддинга. Соответственно, обратно тоже можно для ряда задач строки до 8 символов из латинских букв и цифр преобразовывать в 6-ти байтное представление.

Стандартная модель хэш-функций

Хэш-функции имеют некоторое внутреннее состояние, и функция mix используется для перемешивания внутреннего состояния. Другая функция, combine, используется для комбинации входных блоков с внутренним состоянием. Иногда эти функции объединяют в одну, что не меняет их сути. Потом состояние проходит постобработку (например, обрезается до нужной длины хэша). И все, хэш готов.

initialize the internal state;
for (each block in input)
{
  combine (the internal state, the current input block);
  mix (the internal state);
}
value = postprocess (the internal state);
return value;

Почти все известные хэш-функции построены по этой модели за исключением MD4 и некоторых других.