gifts2017

Простая и быстрая хэш функция (hash) средствами 1С

Опубликовал Влад Косилов (kosilov) в раздел Программирование - Практика программирования

Вроде бы не нужна в 1С хэш функция, а всё таки иногда без неё не обойтись.
В частности для индексирования строк неограниченной длины или групп строк.
Готовую нашел здесь (реализация MD5), но уж очень медленно работает и оптимизировать её не получится - в 1С нет быстрой работы с битами.
Вот нашел выход. Спасибо сайту за теорию http://www.strchr.com/hash_functions
Оказывается своя хэш функция - это просто.
Скорость для 64 битного хэш (кво в минуту):  

Для строки "http://infostart.ru/public/edit/" - 55000
Для этого текста(600 символов) - 3048


Пример использования с тестом скорости работы в разделе файлов.
Скорость расчитывается как количество хэшей из заданного Вами текста за минуту.

http://www.strchr.com/hash_functions

//////////////////////////////////////////////////////////////////////
 //СтрокаХэш - исходный текст
 //hash- начальное значение hash
 // М - множитель (влияет накачество хэш и производительность)
 // TABLE_SIZE - размер получаемого ключа, как Максимальная величина + 1
Функция Хэш(СтрокаХэш, hash=0, M = 31, TABLE_SIZE = 18446744073709551616)
   
//TABLE_SIZE = 18446744073709551615; 64 бита
    //M = 31; Умножитель
   
ДлинаСтроки = СтрДлина(СтрокаХэш);
    Для
к=1 по ДлинаСтроки цикл
       
hash = M * hash + КодСимвола(Сред(СтрокаХэш,к,1));
    конеццикла;
    возврат
hash%TABLE_SIZE;
КонецФункции

// Для ускорения работы с большими текстами их надо передавать блоками
// Данная функция разбивает исходный текст (Параметр "Строка") на блоки
// длиной ДлинаБлока и вычислет хэш блоками возвращая результат для всего текста.
Функция ХэшБлоками(Строка, ДлинаБлока = 64, hash = 0, M = 31, TABLE_SIZE = 18446744073709551616)
    
НачПозиция = 1;
    
ДлинаСтроки = СтрДлина(Строка);
      Пока 
НачПозиция<=ДлинаСтроки цикл
       
hash = Хэш(Сред(Строка, НачПозиция, ДлинаБлока), hash, M, TABLE_SIZE);
       
НачПозиция = НачПозиция + ДлинаБлока;
    КонецЦикла;
    возврат
hash;
КонецФункции


Скачать файлы

Наименование Файл Версия Размер
Простая и быстрая ХЭШ функция (с оптимизацией от alexk-is) версия 2 264
.epf 7,13Kb
30.10.14
264
.epf 7,13Kb Скачать
Предыдущая версия 8
.epf 7,20Kb
30.10.14
8
.epf 7,20Kb Скачать

См. также

Подписаться Добавить вознаграждение

Комментарии

1. Артур Аюханов (artbear) 13.05.10 20:21
Интересно, плюсанул.
(0) Но также очень интересно практическое применение:
цитата "Вроде бы не нужна в 1С хэш функция, а всё таки иногда без неё не обойтись.
В частности для индексирования строк неограниченной длины или групп строк"
вот увидеть бы пример индексирования и сравнить со встроенными методами 1С (например, соответствие) !
2. Влад Косилов (kosilov) 13.05.10 21:11
А попробуй в запросе поставить ГДЕ <строка неограниченной длины> = "Слово из 3-х букв" и поймешь.
Строка неограниченной длины - реквизит объекта неоганиченной длины.
Посмотри зачем нужна хэш функция.
Сравнивать длинные текстовые поля так эффективнее.
3. Артур Аюханов (artbear) 14.05.10 07:45
(2) Пример с ГДЕ не подходит.
Я в таких случаях юзаю внутри запроса
ГДЕ
ВЫРАЗИТЬ(ИнвентаризацияОС.Комментарий КАК Строка(200)) = &Комментарий
запрос прекрасно работает.

Покажи пример индексирования и поиска

ЗЫ я прекрасно знаю назначения хеш-функций :)
Большой опыт программирования на С++ никуда не денется
4. Александр Тимошенко (Adept) 14.05.10 09:48
(3) пример, буквально сегодня применю у себя в конфе,
Есть справочник юзерей, и справочник ролей, они само собой связаны, для того что бы не лезть в БД и каждый раз не проверять есть ли у меня там все необходимые юзеры и роли, те что и в конфе, я буду их собирать в строку и хешировать, и сравнивать с хешем скажем в константе и если уже хеши отличаются то лезть в бд и синхронизировать юзерей и роли.
Вот так например :)
5. Артур Аюханов (artbear) 14.05.10 10:15
(4) Нифига не понял пример.
Расшифруй примерчик.
"Собирать в строку и хешировать", "чтобы не проверять если ли у меня там необходимые юзеры и роли" и т.д.
Жду.
6. Александр Тимошенко (Adept) 14.05.10 10:30
(5) Все просто, при запуске предприятия проводиться проверка соответствие справочника пользователи с тч роли и справочника роли, текущему состоянию (пользователям и ролям внесенными в конфигуратор) , проводиться проверка соответствия если его нет то справочники синхронизируются с системой, для того что бы не сверять при каждом входе со справочниками (строить запросы бд), просто сохранить хэш из строки с именами и ролями пользователей, проверять при входе соответствие хэша, если были изменения, уже лезть в БД и искать где надо добавить пользователей или изменить состав ролей и тд.
7. Артур Аюханов (artbear) 14.05.10 17:42
(6) 1. Перед тем, как сверять, ты же все равно должен исходные значения получить, значит, все равно будет запрос к БД.

(0) Автор, дай пример использования.
Я не против разработки, плюсанул сразу. мне интересно, где именно в 1С можно юзать подобную хеш-функцию.
Ведь у 1С уже есть Соответствие и Структура для быстрого поиска, а также Индексы у таблиц.

Всем - помните, что значения хеш-а совершенно не обязательно должны быть уникальными :( При работе с хеш-функцией вполне могут быть коллизии, об этом нужно всегда помнить!
8. Влад Косилов (kosilov) 15.05.10 03:01
(7) Я сейчас разрабатываю аналитическую базу данных, в которой в качестве источника аналитики используются RSS каналы.
RSS генератор, не отслеживает какие новости пользоватль прочитал (получил), а какие нет. Т.е. это задача RSS приемника определить какая новость уже есть в базе, а какая нет.
Некоторые каналы пересылают поле (тэг) id новости, некоторые нет.
Соответственно, для таких каналов, которые не пересылают тэг id (да и вобщем-то для всех для надежности) необходимо как-то определить новая это новость или нет. Для этого само собой используются некоторый набор тэгов, таких как title, дата публкации и пр. Этот набор тэгов выбирает пользователь отдельно для каждого канала, а каналов может быть много. Здесь есть две проблемы.
С одной стороны не очень приятный запрос, где на лету должны генериться условия (т.е. в тексте), во вторых некоторые поля неограниченной длины. Можно конечно брать подстроку, но подстрока - это всегда ограничение. Дляна заголовка может теоретически быть до 2кб., а я возьму только 500 символов (это ограничение 1С).
В третьих, при большом количестве записей и условий, где сравниваются строки, скорость выполнения запроса будет низкой, а запрос мне надо сделать на каждую новость, которых в канале от 10 до 20 (и больше). Соответственно при получении новостей от 10-20 каналов в которых 10-20 новостей придется выполнить 200-400 запросов, каждый из которых может выполняться секунд по 10.
При хэшировании размер индекса (длина) составлет всего 10-20 символов (вместо 500) и он один для всех текстовых и не текстовых полей. Кроме этого хэш поле индексировано в базе (текстовых поля неограниченной длины нельзя индексировать).
В результате использования хэш функции имеем следующие преимущества:
1. Не надо генерить текст запроса на лету
2. Нет ограничений на длину индексируемой текстовой строки
3. Многократный выигрышь в скорости.

Это по моей задаче.

Есть другой пример.
Допустим вы храните в базе данных текстовые документы (приказы, письма, книги, статьи и пр). Тут уж точно нельзя ограничиваться 200 или 500 первыми символами, так как они могут совпадать для различых текстов. Выход здесь будет один - хэшировать текст.

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

Что же касается возможности коллизии хэш, то такая вероятность практически равна нулю. Коллизии могут возникать только при умышленной подделки исходного текста, или при очень коротком хэш (например 16 бит)
Если же нет опасности, что кто-то будет подстраиваться под хэш и хэш длинный, то коллизии не будет. Вспомните информацию про GUID. При его длине вероятность совпадения ближайшие сколько-то лет (50 что ли) практически равна нулю.

9. Артур Аюханов (artbear) 15.05.10 07:15
(8) Спасибо, хорошие примеры.

ОФФ По поводу ГУИД кто-то на ИС или еще где :) выкладывал статью, где показывалось, что не слишком уж случайное число получается :)
10. Артур Аюханов (artbear) 15.05.10 07:26
(8) Слегка бы поправить функции для оптимизиции и исключения ошибок.
1. непонятно, как поведет себя функция ХэшБлоками, если длина блока будет больше, чем длина строки - Сред обрежет строку или нет, не помню/не знаю :(
2. ИМХО 1С переменную окончания цикла каждый раз пересчитывает, поэтому СтрДлина лучше считать в отдельной переменной до цикла.

Лучше всего проверить функцию на автоматических тестах, которые совсем несложно сделать.
11. Влад Косилов (kosilov) 15.05.10 11:01
(10) Всё верно. У меня была ошибка. При смене блока пропускался один символ за счет цикла Для. Исправил.
Что касается Сред("йцукен",1,1000), то он работает корректно. В данном примере будет просто выбрана вся строка.
12. Артур Аюханов (artbear) 15.05.10 11:14
(11) Вот я и говорю, лучше проверять на автоматических тестах.
Тем более, задача простая, и тестами ее охватить легко :)
13. Артур Аюханов (artbear) 15.05.10 11:16
(11) По вычислении СтрДлина при каждой итерации поправь.
все-таки хеш-функция должна быть максимально быстрой :)
14. Влад Косилов (kosilov) 16.05.10 02:29
15. Алексей Константинов (alexk-is) 18.05.10 11:32
(14) Я подозревал, что у меня шустрый компьютер, только не знал, что на столько. А ведь ему уже 3 года.
...подшаманил чуток :)
Прикрепленные файлы:
16. Влад Косилов (kosilov) 18.05.10 11:59
(15) Боюсь в код закралась ошибка после последней правки.
В функции хэшБлоками было ДлинаСтроки = СтрДлина(СтрокаХэш) вместо ДлинаСтроки = СтрДлина(Строка) (как правильно и как сейчас).
Странно что 1С не ругнулась, но думаю так как СтрокаХэш в этой функции неопределено, то длина была 0 соответственно у Вас хэш высчитывался один рах для всего текста, а не 2-3 раза.
Попробуйте теперь. :)
У меня на ноуте 10тыс. для текста анонса.
17. Алексей Константинов (alexk-is) 18.05.10 12:16
(16) Спасибо подправил. Замер для текста на картинке. Жаль, что у меня нет ноута :)
Прикрепленные файлы:
18. Артур Аюханов (artbear) 18.05.10 14:38
19. Алексей Константинов (alexk-is) 18.05.10 14:55
(18) Внутренности конечно. Ну, и внешний вид чуток.
20. Влад Косилов (kosilov) 18.05.10 21:12
(18) Я же написал: В функции хэшБлоками было ДлинаСтроки = СтрДлина(СтрокаХэш) вместо ДлинаСтроки = СтрДлина(Строка) (как правильно и как сейчас).
21. Алексей Константинов (alexk-is) 19.05.10 12:36
(18) (20) Во вложении вариант с некоторыми изменениями оптимизированный под 8.1.

Суть изменений
1. Исправлена ошибка в фунции ХэшБлокамиСОбраткой
2. Добавлена возможность сохранения текста
3. Начало замера с начала секунды

Суть оптимизации
1. Незначительная оптимизация кода
2. Сокращено количество команд выполняемых интерпретатором (наиболее заметно при использовании отладчика с включенным замером производительности)
3. Подобран более оптимальный размер блока, как мне кажется
Прикрепленные файлы:
SimpleHash2.epf
22. Влад Косилов (kosilov) 19.05.10 22:48
(21) Скачал. Посмотрю сейчас
23. Влад Косилов (kosilov) 19.05.10 23:00
(21) Скрин говорит сам за себя. Плюс однозначно.
PS Никогда бы не подумал, что написание текста модуля в одну строку улучшает производительность :D
Прикрепленные файлы:
24. Влад Косилов (kosilov) 19.05.10 23:31
Забавно, но еще 2%-3% прироста скорости можно получить переведя текст на анлийский вариант.
Прикрепленные файлы:
25. Алексей Константинов (alexk-is) 20.05.10 06:21
(23) Не совсем так. Всё дело в переходах между командами. Поэтому если смотреть в замере производительности, то цикл в строке ДЛЯ из 10000 повторов записанный обычной структурой будет выполнен 10001 раз, а записанный в 1 строку 1 раз. Разумеется, что при этом результат выполнения будет одинаковый.

Кроме этого править такую форму записи очень сложно. Поэтому, если команды отрабатываются 1 раз, то нет особого смысла записывать их в 1 строку.
26. Влад Косилов (kosilov) 20.05.10 22:04
Есть тут ещеодин момент, незнаю как онотразится на стойкости функции.
Изначально функция расчитывалась (смотри ссылку на теорию в заголовке) на анлийский алфавит (или по крайней мере на 255 символов). У нас для русских букв мы имеем юникод 2 байта (КодСимвола(Сред(СтрокаХэш,к,1)) для русской буквы даст число больше 255).
27. Алексей Константинов (alexk-is) 20.05.10 23:11
КодСимвола("z") = 122
КодСимвола("я") = 1103
КодСимвола("ё") = 1105
28. Сергей Старых (tormozit) 22.05.10 14:37
Может кому пригодится такой вариант подсчета хеша. http://www.forum.mista.ru/topic.php?id=483601
29. GSoft. (GSoft) 30.05.10 23:33
Ребят а кто делал или встречал функции шифрования-дешифрования на 1С
30. Федор (tdr1225) 31.05.10 10:39
(29) CodeString() в v7icq.dll (Абадонна)
31. Владислав Цылёв (vet7777) 31.08.10 13:22
Более быстрый вариант :
(несмотря на то, что код более объёмный по сравнению с авторским)
Функция ХэшБыстрый2(СтрокаХэш, Знач Основание = 31, Знач TABLE_SIZE = 18446744073709551616) Экспорт
	Хэш = 0;ДлинаСтроки=СтрДлина(СтрокаХэш);
	КоличествоПовторенийВРазвёртке = 60;Основание2=Основание*Основание;Основание3=Основание2*Основание;Основание4=Основание3*Основание;
	Для Сч = 0 по Цел(ДлинаСтроки/КоличествоПовторенийВРазвёртке)-1 Цикл
		//1С неэффективно работает с длинными строками, поэтому сначала откусываем кусочек
		//складывать начинаем с меньших чисел, т.к. арифметика больших затратнее
		ТекСтрока = Сред(СтрокаХэш, Сч*КоличествоПовторенийВРазвёртке+1, КоличествоПовторенийВРазвёртке);
		Хэш = КодСимвола(ТекСтрока, 4) + Основание * КодСимвола(ТекСтрока, 3) + Основание2 * КодСимвола(ТекСтрока, 2) + Основание3 * КодСимвола(ТекСтрока) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 8) + Основание * КодСимвола(ТекСтрока, 7) + Основание2 * КодСимвола(ТекСтрока, 6) + Основание3 * КодСимвола(ТекСтрока, 5) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 12) + Основание * КодСимвола(ТекСтрока, 11) + Основание2 * КодСимвола(ТекСтрока, 10) + Основание3 * КодСимвола(ТекСтрока, 9) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 16) + Основание * КодСимвола(ТекСтрока, 15) + Основание2 * КодСимвола(ТекСтрока, 14) + Основание3 * КодСимвола(ТекСтрока, 13) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 20) + Основание * КодСимвола(ТекСтрока, 19) + Основание2 * КодСимвола(ТекСтрока, 18) + Основание3 * КодСимвола(ТекСтрока, 17) + Основание4 * (Хэш % TABLE_SIZE);
		Хэш = КодСимвола(ТекСтрока, 24) + Основание * КодСимвола(ТекСтрока, 23) + Основание2 * КодСимвола(ТекСтрока, 22) + Основание3 * КодСимвола(ТекСтрока, 21) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 28) + Основание * КодСимвола(ТекСтрока, 27) + Основание2 * КодСимвола(ТекСтрока, 26) + Основание3 * КодСимвола(ТекСтрока, 25) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 32) + Основание * КодСимвола(ТекСтрока, 31) + Основание2 * КодСимвола(ТекСтрока, 30) + Основание3 * КодСимвола(ТекСтрока, 29) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 36) + Основание * КодСимвола(ТекСтрока, 35) + Основание2 * КодСимвола(ТекСтрока, 34) + Основание3 * КодСимвола(ТекСтрока, 33) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 40) + Основание * КодСимвола(ТекСтрока, 39) + Основание2 * КодСимвола(ТекСтрока, 38) + Основание3 * КодСимвола(ТекСтрока, 37) + Основание4 * (Хэш % TABLE_SIZE);
		Хэш = КодСимвола(ТекСтрока, 44) + Основание * КодСимвола(ТекСтрока, 43) + Основание2 * КодСимвола(ТекСтрока, 42) + Основание3 * КодСимвола(ТекСтрока, 41) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 48) + Основание * КодСимвола(ТекСтрока, 47) + Основание2 * КодСимвола(ТекСтрока, 46) + Основание3 * КодСимвола(ТекСтрока, 45) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 52) + Основание * КодСимвола(ТекСтрока, 51) + Основание2 * КодСимвола(ТекСтрока, 50) + Основание3 * КодСимвола(ТекСтрока, 49) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 56) + Основание * КодСимвола(ТекСтрока, 55) + Основание2 * КодСимвола(ТекСтрока, 54) + Основание3 * КодСимвола(ТекСтрока, 53) + Основание4 * Хэш;
		Хэш = КодСимвола(ТекСтрока, 60) + Основание * КодСимвола(ТекСтрока, 59) + Основание2 * КодСимвола(ТекСтрока, 58) + Основание3 * КодСимвола(ТекСтрока, 57) + Основание4 * (Хэш % TABLE_SIZE);
	КонецЦикла;
	
	Для Сч = ДлинаСтроки - ДлинаСтроки%КоличествоПовторенийВРазвёртке + 1 По ДлинаСтроки Цикл
		Хэш = Основание * Хэш + КодСимвола(СтрокаХэш, Сч);
	КонецЦикла;		
	
	Возврат Хэш%TABLE_SIZE;
	
КонецФункции
...Показать Скрыть
32. Евгений Мартыненков (JohnyDeath) 07.07.11 09:44
А как, например, расчитать хэш для файла (эксель, дбф и т.п.)?
Передавать в качестве строки биты данных?
33. Евгений Мартыненков (JohnyDeath) 07.07.11 10:34
Написал вот так:
Функция ХэшФайла(Знач ИмяФайла) Экспорт
	двФайл = Новый ДвоичныеДанные(ИмяФайла);
	СтрокаФайла = Base64Строка(двФайл);
	Возврат Из_Число_В_16(ХэшБлоками(СтрокаФайла,, 5381, 33));
КонецФункции	//ХэшФайла
...Показать Скрыть

Насколько это правильно?
35. Евгений L (laeg) 11.11.11 18:44
ХЭШ использую как одностороннего криптования пароля.
ТС и (31) спасибо за более быстрые алгоритмы.
36. Осипов Сергей (fixin) 07.12.11 01:54
да, мне тоже актуально. Делаю подпись документа, просто сцепляя гуиды его реквизитов. Так вот для этих целей как раз и годится хэш. МД5 вычисляется долго или через внешние компоненты. Надо поизучать эту методику, заранее плюсанул...
37. Тарас Гулеватый (Foxx) 08.12.11 00:36
Вот если кому интересно - оптимизированный вариант хэш функции (http://infostart.ru/public/100845/). На строках более килобайта - прирост до 50% по скорости.
38. Serj (Serj1C) 04.07.12 07:09
Этот день настал! Встречаем 8.3 и встроенный MD5 в платформу! http://downloads.v8.1c.ru/content/Platform/8_3_1_531/1cv8upd.htm
39. Вячеслав Клюев (slavik27) 20.06.13 07:52
Спасибо, очень полезная штука, попробую!
40. Allexey (alex_4x) 20.05.14 22:00
А сталкивался кто нибудь, как в 1С запросе посчитать хэш от полученной строки?
Цель - получить таблицу с хешем документов, сравнив её с другой такой же таблицей - понять, какие документы отличаются. И всю эту операцию провернуть на сервере.
41. Сергей (ildarovich) 20.03.15 14:54
(40) alex_4x, в статье "Расчет хэш-функции в запросе" описывается один из возможных подходов к решению этой задачи.
42. Сергей Аблаев (serg1974) 15.04.15 10:00
Напомните пожалуйста значение значение функции % - я вероятно знал - но забыл её, и никак не могу понять смысл выражения hash%TABLE_SIZE

ну и заодно разъясните - как получено число TABLE_SIZE = 18446744073709551616? Очень интересно!
я на ассемблере не программировал с 1997 года...

Спасибо!
Для написания сообщения необходимо авторизоваться
Прикрепить файл
Дополнительные параметры ответа