Как генерировать уникальные 64-битные ключи

Question

Я хотел бы генерировать уникальные 64-битные ключи (псевдо) случайным образом для идентификации объектов в нашей модели. Мне нужно, чтобы ключи были настолько уникальными, насколько это возможно (минимизировать вероятность коллизий, когда любые N ключей используются вместе) для всех пользователей системы.

Обычные GUID пока не обсуждаются, потому что мы дешевые данные:). Поскольку я не предполагаю, что потребуется более 1 миллиона ключей, используемых в одном и том же контексте, я думаю, что достаточно 64-битного (вероятность коллизии будет около ~10e-7).

Как примечание, мне также понадобится схема для свертывания / хеширования этих ключей в один 64-битный ключ, который также должен быть хорошо распределенным / уникальным.

Так как в любом случае мне нужна хорошая (хорошо распределенная) функция хеширования, можно ли было бы сложить GUID пополам (возможно, каким-то образом учесть фиксированные биты в GUID)? Или лучше использовать местный ГСЧ? Как бы я посеял ГСЧ, чтобы максимизировать уникальность в пространстве / времени генерации? Насколько сильный RNG мне понадобится?

Я не особо стремлюсь к эффективности (до определенного момента), но мне бы очень хотелось, чтобы вероятности выполнили свое обещание!

Answer 1

Хеш счетчик с использованием быстрого 128-битного криптографического хеша, как md5, а затем разделить на две части. это даст вам "случайные", независимые значения по 64 бита каждое, и это должно быть довольно эффективно.

и вы уверены, что не можете использовать простой счетчик?

Обновите, если вам нужно распределенное решение, просто поместите счетчик на каждую машину и хэшируйте MAC-адрес машины плюс счетчик. для повышения пропускной способности используйте несколько счетчиков для каждой машины, каждая из которых имеет свое имя (A, B и т. д.), а также хэшируйте имя. это большое преимущество использования хэшей - вы можете добавить туда что угодно. просто будьте осторожны, чтобы не иметь двусмысленности (например, ставьте "-" между каждой хешируемой вещью, чтобы имя "1" плюс число "23" не путалось с именем "12" и числом "3").