Быстрый длинный расчет

Question

У меня есть следующая задача.

У меня есть 1 миллиард или более 20-байтовых различных хэшей (хранящихся в некоторой базе данных), общее число которых меньше Java Long.MAX_VALUE;

После этого у меня есть почти бесконечный поток таких хешей.

Есть ли возможность создать некоторое биективное отображение из набора этих 20-байтовых различных хешей в набор чисел от 0 до Long.MAX_VALUE?

Вид полиномиального вычисления типа Лагранжа - но может быть что-то действительно быстрое и эффективное для такого случая.

Нам нужно быстрое long вычисление значения для каждого га sh из этого почти бесконечного потока .

Каждые 20 байтов га sh - это просто число.

Перед обработкой потока мы можем создать отображение

  20-byte | 8-byte
    (hash1 1) 
    .... 
    (hashN N) 

После этого, когда у нас будет следующий ха sh из бесконечного потока, мы получим 8-байтовое значение га sh без поиска, используя только арифметические расчеты.

Answer 1

Будет ли это работать примерно так?

aNextHash = Stream.getHash();
long aValue = aNextHash % Long.MAX_VALUE;

Answer 2

Поскольку вы не дали никаких практических ограничений по размеру или объему хранилища, кроме «Это должно быть быстро», я собираюсь предположить, что вы можете потратить время на предварительную обработку набора хэшей, чтобы «сделать это быстро». Я также предполагаю, что хэши распределяются случайным образом и что сопоставление с 8-байтовыми числами также непредсказуемо.

Мой первый подход - локальная база данных SQLite. Это позволяет вам использовать встроенную индексацию BTree для быстрого получения результатов. При достаточно большом размере страницы вы можете хранить 256 указателей на узел BTree для ожидаемого количества log_256 (10 ^ 9) = 3.737169106748283 запросов на диск при поиске. Это улучшится по мере кэширования большего количества ваших структур BTree.

Второй подход, если у вас есть память для него: BTree в памяти.