| Сейчас на форуме: (+2 невидимых) |
 |
eXeL@B —› Оффтоп —› Хэширование без коллизий |
| Посл.ответ | Сообщение |
|
|
Создано: 22 мая 2011 01:15 · Поправил: 4kusNick · Личное сообщение · #1 Привет, ищу наиболее эффективный алгоритм хэширования по соотношению производительность\устойчивость к коллизиям\минимальный размер данных на выходе %) То есть, никакой криптостойкости или вроде того не нужно вообще - задача захэшировать огромное количество разных id с максимальной гарантией, что хэши не повторятся, и соответственно, на приемлемой скорости, да так, чтобы полученные хэши потом можно было свободно использовать как имена файлов (отсюда - пожелания к размеру данных - в некоторых осях есть ограничения на длину имени файла). Пока смотрю в сторону md5\sha, как думаете - подойдут они тут, или есть что-то более подходящее? ----- Флэш, ява, дотнет - на завтрак, обед и ужин. Unity3D на закуску.  |
|
|
Создано: 22 мая 2011 06:54 · Личное сообщение · #2 4kusNick насколько огромное количество? Уверен на 99%, что с любым из предложенных тобой алгоритмов коллизий не будет |
|
|
Создано: 22 мая 2011 09:03 · Личное сообщение · #3 CityHash128. Очень быстрый, но криптографически нестойкий. ----- PGP key |
|
|
Создано: 22 мая 2011 09:57 · Личное сообщение · #4 ntldr а про коллизии ничего не слышно? ----- Yann Tiersen best and do not fuck |
|
|
Создано: 22 мая 2011 11:12 · Личное сообщение · #5 Специально можно найти коллизию, но полагаю что на обычных наборах данных при 128 бит длине хэша коллизий не будет. Если нужно что-то очень быстрое и криптографически стойкое, то советую обратить внимание на ECHO hash , хотя он все-же сыроват для ответственных применений. ----- PGP key | Сообщение посчитали полезным: 4kusNick |
|
|
Создано: 22 мая 2011 20:12 · Личное сообщение · #6 Magister Yoda Теоретически - может достигать 10 в 12 степени. ntldr Большое спасибо, интересный, быстрый, свежий и от гугла... Попробую. ----- Флэш, ява, дотнет - на завтрак, обед и ужин. Unity3D на закуску. |
|
|
Создано: 22 мая 2011 21:41 · Личное сообщение · #7 ntldr пишет: но полагаю что на обычных наборах данных при 128 бит длине хэша коллизий не будет. на обычных данных и у md5 не будет в 99,8%, особенно, если данные не бинарные, а ограниченные алфавитом, а т.к. нужно id, то не думаю, что стоит беспокоиться приведите пример 2х чисел из интервала 0..10^12 с одинаковым md5 
----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
|
Создано: 23 мая 2011 06:17 · Личное сообщение · #8 Isaev он говорит про количество, не обязательно, что даже id входят в этот промежуток. хотя вообще в этом промежутке вряд ли есть одинаковые хэши |
|
|
Создано: 23 мая 2011 13:16 · Личное сообщение · #9 Magister Yoda пишет: он говорит про количество, не обязательно, что даже id входят в этот промежуток. Ну как же? он именно про id говорил 4kusNick пишет: То есть, никакой криптостойкости или вроде того не нужно вообще - задача захэшировать огромное количество разных id с максимальной гарантией, что хэши не повторятся ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh |
|
|
Создано: 23 мая 2011 13:53 · Личное сообщение · #10 Если диапазон id ограничен, то зачем вообще хэш, проще напрямую использовать id и не беспокоиться насчет коллизий. Если из id нужно получить нечто псевдослучайно выглядящее и длина id <= 128 бит, то можно шифровать id любым блочным шифром с нулевым ключом (или применить любую другую обратимую функцию), получим "хэш" гарантированно без коллизий. ----- PGP key |
|
|
Создано: 23 мая 2011 13:54 · Поправил: Azur1d · Личное сообщение · #11 Я может фигню ляпну, но зачем хешировать IDшники? 10^12 это максимум 48 бит, а md5 это 128 бит. Объем данных больше, поиск медленнее, еще коллизии могут быть. IDшники как имена файлов вполне можно использовать. --- ntldr опередил
|
|
|
Создано: 23 мая 2011 19:17 · Поправил: 4kusNick · Личное сообщение · #12 Isaev ntldr Azur1d Прошу прощения, что сразу не объяснил - под id я подразумевал записи вида $55eggg^:cdvhg/ffd5435/m.,<.d5gt /d/gfhhd\567]fvgnb %vbbg/uu54.64>?4 и т.д., то есть там каждый "id" может быть сформирован в виде любого набора символов (в том числе, и не из алфавита), длиной от 1 до 1000, и они не могу повторяться, то есть каждый "id" - уникален, напрямую их использовать не выйдет, т.к. нужно сопоставлять им имена файлов в разных операционках. ntldr А на счёт блочных шифров - эта идея ещё актуальна, с учётом вышесказанного? Если да, то будет ли оно по производительности на уровне хэш-алгоритмов md5\sha или даже CityHash? ----- Флэш, ява, дотнет - на завтрак, обед и ужин. Unity3D на закуску. |
|
|
Создано: 23 мая 2011 20:28 · Личное сообщение · #13 4kusNick пишет: А на счёт блочных шифров - эта идея ещё актуальна, с учётом вышесказанного? Не актуальна, т.к. в общем случае нельзя однозначно отобразить большее множество на меньшее. Если хотите гарантированно без коллизий - конструируйте perfect hash функцию для своего заранее известного набора ключей. Может быть вам поможет. Хотя для набора из триллиона ключей генерировать perfect hash будет долго. Либо используйте любой 128 битный хэш с хорошей диффузией, тогда на произвольном наборе данных будет в среднем одна коллизия на 2^64 ключей. С perfect hash можно без проблем уложиться в 64 бита без коллизий (обычный 64 битный хэш скорее всего будет иметь коллизии на вашем наборе ключей). Ну и наконец - если набор ключей не определен, т.е. нет возможности сгенерировать и проверить все варианты, то не существует способов хэширования гарантированно без коллизий. ----- PGP key | Сообщение посчитали полезным: Isaev, tundra37, Gerpes, 4kusNick |
|
|
Создано: 25 мая 2011 11:16 · Личное сообщение · #14 ntldr Понятно, спасибо за идею с perfect hash - возьму на вооружение. Набор ключей определён, то есть есть возможность на одном и том же наборе несколько разных алгоритмов попробовать и потестировать на коллизии. Всем большое спасибо за ценные советы и помощь, дальше я уже сам. ----- Флэш, ява, дотнет - на завтрак, обед и ужин. Unity3D на закуску. |
|
eXeL@B —› Оффтоп —› Хэширование без коллизий |
Для печати