равномерное хеширование

consistent hashing я знаю. А еще?

для md5 в качестве хф используй младший байт

judy array (int -> int);
или просто хэш-табл с хэшем : первые_4_байта_md5 % размер_таблицы_простое_число

для md5 в качестве хф используй младший байт

только если размер хэш-таблицы < 255

Пальцем в небо: пропустить имеющиеся md5-хэши через какую-нибудь compression function.

То есть разбить на блоки и xor'ом их между собой, например.

http://en.wikipedia.org/wiki/MurmurHash

А товарищи выше по треду вообще не в теме, советчики млин.

О - да - про этот я не знал, спасибо.

Так а что вам надо конкретно? Просто хеш-функция с (максимально) равномерным распределением?
index = crc32(data, data_size) % hash_table_size

consistent hashing я знаю. А еще?

extendible hashing?

Просто хеш-функция с (максимально) равномерным распределением?

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

Тоже интересно.

Без представления о характере исходного распределения (т.е. без предобработки или иных предположений) ничего не сделать.

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

Копать в сторону написания генераторов «случайных» чисел пробовал?

Копать в сторону написания генераторов «случайных» чисел пробовал?

Мне воспроизводимый алгоритм нужен - то есть одни и те же данные должны выдать один и тот же хеш.

:) в генераторах «случайных» чисел данные _всегда_ воспроизводимы 1 в 1, поэтому для «случайности» просто берут разные входные данные - привязываются к таймеру и фазе луны. На 2-м курсе в универе штук 5-6 разных генераторов писал в рамках курса теория вероятности и мат статистика.

Я это знаю. Я не вижу пока как ты хочешь привязать псевдопоследовательность к входным данным - чтобы получать один и тот же ключ на один и тот же вход.

Объясни, в чем ты видишь проблему, может я неправильно понимаю задачу, но имхо все очевидно - пишешь генератор с равномерным разбросом, от данных он не зависит как и от количества поступающих данных.

от данных он не зависит

Мне надо чтобы от данных он зависел. Чтобы одни и те же данные бросались туда же.

Мне надо чтобы от данных он зависел. Чтобы одни и те же данные бросались туда же.

Т.е. во входном потоке данных у тебя могут быть одни и те же данные, но различном порядке? И необходимо чтобы разброс по структуре был привязан не к порядку входных данных, а к самим данным? Я правильно понял задачу?

Мне воспроизводимый алгоритм нужен - то есть одни и те же данные должны выдать один и тот же хеш.

А одни и те же данные в _другом_ порядке выдают тот же результирующий хэш?

Т.е. во входном потоке данных у тебя могут быть одни и те же данные, но различном порядке?

могут. угу

А одни и те же данные в _другом_ порядке выдают тот же результирующий хэш?

Соответствие между входом и выходом должно быть 100% воспроизводимым на любой последовательности данных. Привязка исключительно к данным но не к порядку.

Привязка исключительно к данным но не к порядку.
Привязка исключительно к данным

Ну ты понел. Т.е. тебе как минимум нужно знать что за данные. Попробуй перед распределением их, данные, сортировать ;) Или посмотри, как устроены различные sorted dictionary, но это будет и времязатратно, и предобратка. Но сами данные затронуты не будут. А порядок тебе, исходя из постановки вопроса, фиолетов.

Т.е. тебе как минимум нужно знать что за данные.

Все что известно про данные описано в топике:)

Попробуй перед распределением их, данные, сортировать ;)

Не есть возможным.

Ну ты сам подумай. Чтобы разместить данные в необходимом тебе порядке (например равномерное распределение) при чем чтобы порядок входных данных при одинаковых данных давал равные результаты распределения - тебе неупорядоченные данные нужно сначала упорядочить, а потом сделать распределение. Я тут логически даже не вижу других путей. Почему нельзя их отсортировать по алфавиту?

Почему нельзя их отсортировать по алфавиту?

Их нет - их константный поток, старые вайпаются.

Я тут логически даже не вижу других путей.

Логически они есть - перебалансировки. Примеры - АВЛ и прочие самобалансирующиеся деревья.

я предлагаю DHT

Их нет - их константный поток, старые вайпаются.

А ты сортируй по-порядку, тебе все не нужны сразу чтобы начать сортировать. Все-таки посмотри как устроены sorted dictionary. И сложность алгоритма у них нормальная от log N до 2*log N.

Логически они есть - перебалансировки.

А они на святом духе работают, а не сравнении и сортировке? :)

Примеры - АВЛ и прочие самобалансирующиеся деревья.

Ну, sorted dict это красно-черное дерево например.

Без представления о характере исходного распределения (т.е. без предобработки или иных предположений) ничего не сделать.

Внезапно, HyperLogLog без знания исходного распределения дает оценку на основе равномерно распределенной хеш-функции.

// Хотя, кому это я говорю. Кто из лоровской школоты слышал про подсчет статметрик на потоке данных.

Внезапно, HyperLogLog без знания исходного распределения дает оценку на основе равномерно распределенной хеш-функции.

ты совсем тупой? HLL заранее требует достаточно хорошую хэш-функцию для входных данных. Возьмёшь хреновый хэш - получишь хреновую оценку.

Молодец, какой-то просвет замелькал. А теперь перечитай ОП пост и сделай последнее ментальное усилие.