Subj: процент невозможных x-битных хешей на 2^х уникальных чисел(длинна чисел x бит)? моск сгенерировал мысль но оформить её как запрос google не смог. прошу пояснить если не сложно дошло что коллизии у x-битной хеш функции могут встречаться и для данных длинною менее или равной x-бит следовательно при длине данных меньше чем длинна хэша есть значения которые хэш получить не может и при успешном поиске коллизии для этих "невозможных" значений хэша коллизии будут длиннее чем x бит следует мысль что такое вероятно и для данный незначительно длиннее чем длинна хэша тут собственно возник вопрос, а сколько таких невозможных хешей для различных функций? есть где-нибудь инфа? пример: берём хэш функцию производящую восмибитный хэш скармливаем ей все возможные восмибитные числа(поштучно) и записываем хэши в таблицу после этого убираем из таблицы дубликаты и считаем ((2^8) - количество_оставшихся_хэшей)/(2^8) заранее спасибо
все зависит от алгоритма, если взять за идеал что на 256 чисел будет 256 разных хэшей (8 бит), то не факт что на 512 чисел будет 50% колизий, может и больше - 75%. но не меньше 50%. Это если число длинее чем хэш, а если оно короче то возможно и 0% колизий т.к. 8 битный хэш = 256 различным числам, что в твоем случае и есть 2^8, на каждое число получаем свой хэш.
