Всем добрый вечер! Понадобилось тут зашифровать списки сотрудников так, чтобы сохранить возможность их сопоставления. Решил использовать хеширование. Но оказалось, грамотно его построить непросто. Hash1 создаёт коллизии даже на 50 сотрудниках. Hash2 - вроде бы, по-лучше, но приходится использовать вспомогательный столбец, да и подтормаживать начинает. Может подскажет кто из опытных в этой теме людей более простые и эффективные решения?
Всем добрый вечер! Понадобилось тут зашифровать списки сотрудников так, чтобы сохранить возможность их сопоставления. Решил использовать хеширование. Но оказалось, грамотно его построить непросто. Hash1 создаёт коллизии даже на 50 сотрудниках. Hash2 - вроде бы, по-лучше, но приходится использовать вспомогательный столбец, да и подтормаживать начинает. Может подскажет кто из опытных в этой теме людей более простые и эффективные решения?Формуляр
Формуляр, здравствуйте. Если интересно, я использовал хеш-функцию здесь http://www.excelworld.ru/forum/3-717-3, правда она на VBA, но зато компактная (на мой взгляд). Разумеется, основная беда "хешей" - коллизии, как с ними бороться, думаю, знаете : )
Формуляр, здравствуйте. Если интересно, я использовал хеш-функцию здесь http://www.excelworld.ru/forum/3-717-3, правда она на VBA, но зато компактная (на мой взгляд). Разумеется, основная беда "хешей" - коллизии, как с ними бороться, думаю, знаете : )nerv
Чебурашка стал символом олимпийских игр. А чего достиг ты? Тишина - самый громкий звук
nerv, посмотрел предложенную ф-цию - похоже, её можно реализовать на формулах. Только хотелось бы сократить те элементы, которые не очень принципиальны. Ежели, конечно, таковые имеются. Можете ли вы вкратце прокоментировать каждую из используемых констант? Для меня это всё - пляски с бубном.
[vba]
Код
Private Function EasyHash(ByRef Str$) As Long Dim i As Integer, Hash As Long For i = 1 To Len(Str) Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223 EasyHash = ((Hash Xor Abs(1365 / i)) And 65535) + EasyHash Next End Function
[/vba]
Цитата (nerv)
как с ними бороться, думаю, знаете : )
Даже не понял, вшутку это или всерьёз. На всякий случай, отвечаю: ни малейшего понятия!
PS: Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем?
nerv, посмотрел предложенную ф-цию - похоже, её можно реализовать на формулах. Только хотелось бы сократить те элементы, которые не очень принципиальны. Ежели, конечно, таковые имеются. Можете ли вы вкратце прокоментировать каждую из используемых констант? Для меня это всё - пляски с бубном.
[vba]
Код
Private Function EasyHash(ByRef Str$) As Long Dim i As Integer, Hash As Long For i = 1 To Len(Str) Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223 EasyHash = ((Hash Xor Abs(1365 / i)) And 65535) + EasyHash Next End Function
[/vba]
Цитата (nerv)
как с ними бороться, думаю, знаете : )
Даже не понял, вшутку это или всерьёз. На всякий случай, отвечаю: ни малейшего понятия!
PS: Xor и And (я так понимаю - побитовые) в формулу не лезут. Можно как-нибудь без них или заменить чем?Формуляр
Excel 2003 EN, 2013 EN
Сообщение отредактировал Формуляр - Четверг, 27.10.2011, 22:33
Буду разбираться, чем можно пожертвовать при реализации на формулах.
\Попробуйте такой вариант. На первый взгляд результат вполне приемлемый. Я бы даже сказал лучше, чем был
[vba]
Код
Private Function EasyHash(ByRef Str$) As Long Dim i As Integer, Hash As Long For i = 1 To Len(Str) Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223 EasyHash = (Hash / i And 1048575) + EasyHash Next End Function
[/vba]
Какая хорошая разница: Алла | 2036555 аллА | 1090691 баа | 2089824 ааб | 980141
Цитата (Формуляр)
Не пойму в чём смысл преобразования
Судя по всему остаточный артефакт от копи-паста
Цитата (Формуляр)
Буду разбираться, чем можно пожертвовать при реализации на формулах.
\Попробуйте такой вариант. На первый взгляд результат вполне приемлемый. Я бы даже сказал лучше, чем был
[vba]
Код
Private Function EasyHash(ByRef Str$) As Long Dim i As Integer, Hash As Long For i = 1 To Len(Str) Hash = i + 1664525 * AscB(Mid(Str, i, 1)) + 1013904223 EasyHash = (Hash / i And 1048575) + EasyHash Next End Function
[/vba]
Какая хорошая разница: Алла | 2036555 аллА | 1090691 баа | 2089824 ааб | 980141nerv
попытался перевести функцию Александра в Excel, результат получается другой в отличии от UDF, ОСТАТ(...;2^20), аналог AND 1048575, делаю после суммирования, чтобы ограничить конечный хэш 20 битами:
попытался перевести функцию Александра в Excel, результат получается другой в отличии от UDF, ОСТАТ(...;2^20), аналог AND 1048575, делаю после суммирования, чтобы ограничить конечный хэш 20 битами:
for (i = 0; i < len; str++, i++) { hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223; }
[/vba] Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения). С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз). И вообще непонятно зачем прибавлять константу, половина которой тут же улетает за границы разрядной сетки? Короче, загадок меньше не стало...
for (i = 0; i < len; str++, i++) { hash = (hash * 1664525) + (unsigned char)(*str) + 1013904223; }
[/vba] Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения). С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз). И вообще непонятно зачем прибавлять константу, половина которой тут же улетает за границы разрядной сетки? Короче, загадок меньше не стало...Формуляр
Excel 2003 EN, 2013 EN
Сообщение отредактировал Формуляр - Воскресенье, 30.10.2011, 19:42
Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения).
Цитата с сайта
Quote
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:
Американский словарь из проекта Ispell, 62075 слов. Русский словарь из проекта Ispell, 128900 слов. Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.
Общее количество после слияния — 326797 уникальных слов.
В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:
Немецкий словарь из проекта Ispell, 39612 слов. Венгерский словарь из проекта Ispell, 211880 слов. Итальянский словарь из проекта Ispell, 37268 слов. Шведский словарь из проекта Ispell, 24019 слов.
Общее количество после слияния — 310595 уникальных слов.
CRC32 Function. Знакомое название, не правда ли?) Только если посмотреть код на той странице, ссылку на кот. я давал выше, саму таблицу вы не найдете) А она не маленькая : )
Quote (Формуляр)
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).
Не знаю, как работает C, но если писать в Ассемблере, то, действительно, будет установлен флаг OF, но при этом работа программы продолжится. Хотя, как запрограммируешь...*
*на сколько мне известно
Quote (Формуляр)
Логично, мне кажется, предположить что константы были определены именно для данной последовательности операций, и как только мы её меняем меняются и качественные хар-ки хэш-функции (и скорее всего не в сторону улучшения).
Цитата с сайта
Quote
Для проверки эффективности хэш-функций были выбраны следующие тестовые данные:
Американский словарь из проекта Ispell, 62075 слов. Русский словарь из проекта Ispell, 128900 слов. Список имен, извлеченный из всех библиотек на моем linux-компьютере (libc.a и прочие), 136073 слов.
Общее количество после слияния — 326797 уникальных слов.
В предыдущем тесте данные имели общее свойство - неизменный старший бит каждого байта. Это могло повлиять на результат. Поэтому был проведен повторный тест, для которого были выбраны другие наборы данных:
Немецкий словарь из проекта Ispell, 39612 слов. Венгерский словарь из проекта Ispell, 211880 слов. Итальянский словарь из проекта Ispell, 37268 слов. Шведский словарь из проекта Ispell, 24019 слов.
Общее количество после слияния — 310595 уникальных слов.
CRC32 Function. Знакомое название, не правда ли?) Только если посмотреть код на той странице, ссылку на кот. я давал выше, саму таблицу вы не найдете) А она не маленькая : )
Quote (Формуляр)
С другой стороны, если тупо следовать первоисточнику, сразу после 1го цикла получаем переполнение разрядов, причём в С, по идее, происходит то же самое (если у кого есть возможность - проверьте, плз).
Не знаю, как работает C, но если писать в Ассемблере, то, действительно, будет установлен флаг OF, но при этом работа программы продолжится. Хотя, как запрограммируешь...*
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
Судя по всему остаточный артефакт от копи-паста 
