ReSQL.ru
     
powered by simpleCommunicator - 2.0.53     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / функция hash
79 сообщений из 79, показаны все 4 страниц
  все  
функция hash
    #39161724
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
Какой алгоритм используется в встроенной функции hash?

Решил при миграции на 3-ку максимально вычистить самописные UDF и вот что получилось
Код: plsql
1.
2.
select hash('АРЛЕТ'), hash('БАЛЕТ')
from RDB$DATABASE


Код: plaintext
1.
HASH	HASH1
13490210	13490210
...
Рейтинг: 0 / 0
03.02.2016, 11:17
| Ответить | Цитировать | Написать  
функция hash
    #39161739
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Viktor_bsРешил при миграции на 3-ку
Это неправильные пчёлы! Совсем неправильные! И они, наверное, делают неправильный мёд!

HASHHASH114 970 874 536 61014 974 901 068 450
...
Рейтинг: 0 / 0
03.02.2016, 11:37
| Ответить | Цитировать | Написать  
функция hash
    #39161750
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
Viktor_bsКакой алгоритм используется в встроенной функции hash?
ELF
...
Рейтинг: 0 / 0
03.02.2016, 11:45
| Ответить | Цитировать | Написать  
функция hash
    #39161755
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
wadmanViktor_bsРешил при миграции на 3-ку
Это неправильные пчёлы! Совсем неправильные! И они, наверное, делают неправильный мёд!

HASHHASH114 970 874 536 61014 974 901 068 450
Проверил на V2.5.5.26916


...
Рейтинг: 0 / 0
03.02.2016, 11:49
| Ответить | Цитировать | Написать  
функция hash
    #39161760
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Viktor_bsПроверил на V2.5.5.26916
И на 2.5.х результат как у меня выше.
...
Рейтинг: 0 / 0
03.02.2016, 11:52
| Ответить | Цитировать | Написать  
функция hash
    #39161762
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
wadmanViktor_bsПроверил на V2.5.5.26916
И на 2.5.х результат как у меня выше.
Видимо, у меня руки кривые. :(
...
Рейтинг: 0 / 0
03.02.2016, 11:53
| Ответить | Цитировать | Написать  
функция hash
    #39161766
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
Viktor_bs,

Ну можно конечно и другой хэш получить. Например так:
Код: sql
1.
  select hash(cast('БАЛЕТ' as char(255))) from rdb$database


но ты прав - хэши одинаковые для АРЛЕТ/БАЛЕТ.
...
Рейтинг: 0 / 0
03.02.2016, 11:55
| Ответить | Цитировать | Написать  
функция hash
    #39161768
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
DarkMasterно ты прав - хэши одинаковые для АРЛЕТ/БАЛЕТ.
То есть у меня действительно руки не оттуда?
...
Рейтинг: 0 / 0
03.02.2016, 11:57
| Ответить | Цитировать | Написать  
функция hash
    #39161777
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
wadman,

Ну у меня появилось несколько минут свободных, я и сделал это:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
execute block
returns (x varchar(255))
as
begin
  x='АРЛЕТ';
  x=hash(x);
  suspend;
  x='БАЛЕТ';
  x=hash(x);
  suspend;
end


и это:

Код: sql
1.
2.
3.
select hash(cast('АРЛЕТ' as varchar(255))),1 from rdb$database
union
select hash(cast('БАЛЕТ' as varchar(255))),2 from rdb$database
...
Рейтинг: 0 / 0
03.02.2016, 12:04
| Ответить | Цитировать | Написать  
функция hash
    #39161781
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
wadmanDarkMasterно ты прав - хэши одинаковые для АРЛЕТ/БАЛЕТ.
То есть у меня действительно руки не оттуда?

У тебя там случайно какой-нить UDF не затесалось?
...
Рейтинг: 0 / 0
03.02.2016, 12:05
| Ответить | Цитировать | Написать  
функция hash
    #39161782
Мимопроходящий
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Мимопроходящий
Участник
Hello, Darkmaster!
You wrote on 3 февраля 2016 г. 12:00:02:

Darkmaster> но ты прав - хэши одинаковые для АРЛЕТ/БАЛЕТ.нет.
select hash('БАЛЕТ'),
hash('АРЛЕТ')
from rdb$database

14 974 901 068 450 14 970 874 536 610

V2.5.1.26351 (64-битный, на win7 x64)
ods 11.2
dialect 3

Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
03.02.2016, 12:05
| Ответить | Цитировать | Написать  
функция hash
    #39161789
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
DarkMasterНу у меня появилось несколько минут свободных, я и сделал это:
У меня - секунд :)
DarkMaster
Код: sql
1.
2.
3.
select hash(cast('АРЛЕТ' as varchar(255))),1 from rdb$database
union
select hash(cast('БАЛЕТ' as varchar(255))),2 from rdb$database


F_1CONSTANT149708745366101149749010684502
И еще:
Код: sql
1.
select cast(hash('АРЛЕТ') as varchar(255)), cast(hash('БАЛЕТ') as varchar(255)) from RDB$DATABASE


CASTCAST11497087453661014974901068450
...
Рейтинг: 0 / 0
03.02.2016, 12:08
| Ответить | Цитировать | Написать  
функция hash
    #39161792
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
DarkMasterwadmanпропущено...

То есть у меня действительно руки не оттуда?

У тебя там случайно какой-нить UDF не затесалось?
Четыре FB и все одно и тоже возвращают. Нет udf для хэша.
...
Рейтинг: 0 / 0
03.02.2016, 12:10
| Ответить | Цитировать | Написать  
функция hash
    #39161793
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
Мимопроходящий,

Извини, не соглашусь - тот же запрос на FB 2.5.4.26856 (Win, ODS 11.2, WIN1251) мне отдает то же, что и у ТС.
...
Рейтинг: 0 / 0
03.02.2016, 12:10
| Ответить | Цитировать | Написать  
функция hash
    #39161796
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
У меня FB x86, а Windows x64
...
Рейтинг: 0 / 0
03.02.2016, 12:11
| Ответить | Цитировать | Написать  
функция hash
    #39161798
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Viktor_bsУ меня FB x86, а Windows x64
И такое есть. Еще варианты?
...
Рейтинг: 0 / 0
03.02.2016, 12:11
| Ответить | Цитировать | Написать  
функция hash
    #39161816
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
wadman,

Ха. Ларчик открывался просто ;)

У меня данные в Win1251 лежат и хэши получаю одинаковые. Если данные в UNICODE_FSS - то да хэши разные, и да - те же самые, что приводил ты и Мимопроходящий. Так что где-то так.
...
Рейтинг: 0 / 0
03.02.2016, 12:22
| Ответить | Цитировать | Написать  
функция hash
    #39161818
fb user
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fb user
Гость
МимопроходящийHello, Darkmaster!
You wrote on 3 февраля 2016 г. 12:00:02:

Darkmaster> но ты прав - хэши одинаковые для АРЛЕТ/БАЛЕТ.нет.
select hash('БАЛЕТ'),
hash('АРЛЕТ')
from rdb$database

14 974 901 068 450 14 970 874 536 610

V2.5.1.26351 (64-битный, на win7 x64)
ods 11.2
dialect 3


Не воспроизводится:
V2.5.1.26351 (64-битный, на win7 x64)
ods 11.2
dialect 3

Код: sql
1.
2.
3.
select hash('БАЛЕТ'),
       hash('АРЛЕТ')
from rdb$database


13490210 13490210

Не смешно уже.
...
Рейтинг: 0 / 0
03.02.2016, 12:23
| Ответить | Цитировать | Написать  
функция hash
    #39161821
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гаджимурадов Рустам
Участник
Не спорьте, ничего удивительного в коллизиях нет.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
03.02.2016, 12:24
| Ответить | Цитировать | Написать  
функция hash
    #39161827
fb user
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fb user
Гость
Если чарсет коннекта поставить UTF8, то хеши разные :)
...
Рейтинг: 0 / 0
03.02.2016, 12:25
| Ответить | Цитировать | Написать  
функция hash
    #39161835
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гаджимурадов Рустам
Участник
Функция-то побайтово работает, а не посимвольно.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
03.02.2016, 12:27
| Ответить | Цитировать | Написать  
функция hash
    #39161844
fb user
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
fb user
Гость
нужно 2 функции:
- character_hash, и приводить параметр к utf8
- binary_hash
...
Рейтинг: 0 / 0
03.02.2016, 12:29
| Ответить | Цитировать | Написать  
функция hash
    #39161847
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
Гаджимурадов РустамНе спорьте, ничего удивительного в коллизиях нет.

При этом самописная UDF c кастрированной до 8 байт sha1 таким не болеет лет 15. Т.е. ни одной коллизии за все время, иначе бы пользователи убили из-за невозможности внести записи справочники (защита от дублей)
...
Рейтинг: 0 / 0
03.02.2016, 12:30
| Ответить | Цитировать | Написать  
функция hash
    #39161874
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гаджимурадов Рустам
Участник
Ну так это другой алгоритм, как и MD5 и пр., со своими коллизиями.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
03.02.2016, 12:49
| Ответить | Цитировать | Написать  
функция hash
    #39161910
WildSery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WildSery
Участник
Viktor_bsТ.е. ни одной коллизии за все время, иначе бы пользователи убили из-за невозможности внести записи справочники (защита от дублей)
Если у вас на хеш навешен уник, поздравляю, "Шарик, ты балбес!" (ц)
...
Рейтинг: 0 / 0
03.02.2016, 13:12
| Ответить | Цитировать | Написать  
функция hash
    #39162347
Фотография DarkMaster
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
DarkMaster
Участник
WildSeryViktor_bsТ.е. ни одной коллизии за все время, иначе бы пользователи убили из-за невозможности внести записи справочники (защита от дублей)
Если у вас на хеш навешен уник, поздравляю, "Шарик, ты балбес!" (ц)

Ну такое возможно, если достаточно длинные строки вводить - коллизия может и не проявится. Но вешать уник на поле, которое вычисляется по алгоритму, предполагающему возникновение коллизии - это да, не хорошо.
...
Рейтинг: 0 / 0
03.02.2016, 19:02
| Ответить | Цитировать | Написать  
функция hash
    #39162660
WildSery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WildSery
Участник
DarkMasterНу такое возможно, если достаточно длинные строки вводить - коллизия может и не проявится. Но вешать уник на поле, которое вычисляется по алгоритму, предполагающему возникновение коллизии - это да, не хорошо.
Хеш - это и есть "алгоритм, предполагающий возникновение коллизии".
Хеш без коллизий возможен, но его объём в таком случае мало отличается от объёма хешируемых данных, потому для простоты можно использовать сами данные.
...
Рейтинг: 0 / 0
04.02.2016, 10:00
| Ответить | Цитировать | Написать  
функция hash
    #39162693
Фотография Док
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Док
Участник
DarkMasterХа. Ларчик открывался просто ;)
+1

на последнем релизе птицы в win1251 результат как у ТС, в utf8 - как у вадмана и МП
...
Рейтинг: 0 / 0
04.02.2016, 10:31
| Ответить | Цитировать | Написать  
функция hash
    #39162785
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
WildSeryViktor_bsТ.е. ни одной коллизии за все время, иначе бы пользователи убили из-за невозможности внести записи справочники (защита от дублей)
Если у вас на хеш навешен уник, поздравляю, "Шарик, ты балбес!" (ц)
:) Как по-вашему это (уникальность строк) нужно было делать?
...
Рейтинг: 0 / 0
04.02.2016, 11:44
| Ответить | Цитировать | Написать  
функция hash
    #39162803
Фотография wadman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wadman
Участник
Viktor_bsWildSeryпропущено...

Если у вас на хеш навешен уник, поздравляю, "Шарик, ты балбес!" (ц)
:) Как по-вашему это (уникальность строк) нужно было делать?
По самим строкам и делать.
...
Рейтинг: 0 / 0
04.02.2016, 11:56
| Ответить | Цитировать | Написать  
функция hash
    #39162808
miwaonline
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miwaonline
Участник
wadmanViktor_bsпропущено...

:) Как по-вашему это (уникальность строк) нужно было делать?
По самим строкам и делать.
Предугадывая вопросс "а если строк очень много" - можно использовать хеш, но при совпадение хешей обязательно дополнительно проверять совпадение строк. Вешать юник на чистый хеш - да, очень плохая идея.
...
Рейтинг: 0 / 0
04.02.2016, 12:00
| Ответить | Цитировать | Написать  
функция hash
    #39162881
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
а можно по двум хешам, например md5 и sha2

а если чуть серьезней, а почему тогда на GUID'ы можно юники вешать?
...
Рейтинг: 0 / 0
04.02.2016, 13:13
| Ответить | Цитировать | Написать  
функция hash
    #39162889
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Arioch,

каким образом связаны GUID'ы и хэши?
...
Рейтинг: 0 / 0
04.02.2016, 13:21
| Ответить | Цитировать | Написать  
функция hash
    #39162890
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
miwaonlinewadmanпропущено...

По самим строкам и делать.
Предугадывая вопросс "а если строк очень много" - можно использовать хеш, но при совпадение хешей обязательно дополнительно проверять совпадение строк. Вешать юник на чистый хеш - да, очень плохая идея.
Я не зря задал этот вопрос, т.к. предполагал такие ответы :)
1. Напомните мне когда появилась возможность строить индекс по строкам длиннее 84 символов?
2. В критичных местах так и было, но с юником. Процедура вставляющая запись и возвращающая ее ID проверяла на совпадение строк в случае нахождения хеша и при коллизии (несовпадении строк) давала ошибку. За 15 лет ни одной ошибки. Наверное везет.
2. Если не строить уникальный индекс то в многопользовательской среде возможны дубли и они на практике были, а для некоторых задач (синдикативная информация) дубли критичнее чем возможные отлупы.
3. В наиболее критичном месте используем 2 разных хеш-алгоритма, но с уником и дополнительной постобработкой отпупов на уникальность (возникают при одновременной вставке с разных транзакций одинакового нового написания).

Еще варианты решения? Мне действительно интересно, но для отсечения теоретиков с.м. картину ниже:
Размер баы >1Тб, количество пользователей ~200
...
Рейтинг: 0 / 0
04.02.2016, 13:21
| Ответить | Цитировать | Написать  
функция hash
    #39162898
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Viktor_bs,

> 1. Напомните мне когда появилась возможность строить индекс по строкам длиннее 84 символов?

начиная с Firebird 2.0 (2006-2007 год) разрешено делать индексы до 1/4 страницы

> 2. Если не строить уникальный индекс то в многопользовательской среде возможны дубли и они на практике были, а для некоторых задач (синдикативная информация) дубли критичнее чем возможные отлупы.

дык я не пойму, если вы там решили переписать полсистему чтобы заменить UDF на встроенную функцию, то какая вам разница, что придётся индексы переделывать на обычные юники
...
Рейтинг: 0 / 0
04.02.2016, 13:28
| Ответить | Цитировать | Написать  
функция hash
    #39162903
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Симонов Денис,

тем, что GUIDы тоже пересекаются, хотя и с вероятностью 2^-128 - но у длиных хороших хешей примерно так же
...
Рейтинг: 0 / 0
04.02.2016, 13:31
| Ответить | Цитировать | Написать  
функция hash
    #39162914
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
AriochGUIDы тоже пересекаются, хотя и с вероятностью 2^-128 - но у длиных хороших
хешей примерно так же
Э-э-э... Они как бы для совсем разных целей выдумывались и совершенно не взаимозаменяемы.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
04.02.2016, 13:39
| Ответить | Цитировать | Написать  
функция hash
    #39162923
miwaonline
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miwaonline
Участник
Viktor_bsЕще варианты решения?
Решения чего именно? Соблюдения уникальности строк? Ничего умнее сравнения хеша и при совпадении - сравнения исходной строки не придумали, насколько мне известно.

Интенсивная многопользовательская работа, как и любая другая реальная ситуация, может внести свои дополнения, конечно.

Viktor_bsдля отсечения теоретиков с.м. картину ниже
Теоретикам как раз все равно, о чем теоретизировать, это ты практиков пугаешь
...
Рейтинг: 0 / 0
04.02.2016, 13:45
| Ответить | Цитировать | Написать  
функция hash
    #39162934
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
Симонов ДенисViktor_bs,

> 1. Напомните мне когда появилась возможность строить индекс по строкам длиннее 84 символов?

начиная с Firebird 2.0 (2006-2007 год) разрешено делать индексы до 1/4 страницы

> 2. Если не строить уникальный индекс то в многопользовательской среде возможны дубли и они на практике были, а для некоторых задач (синдикативная информация) дубли критичнее чем возможные отлупы.

дык я не пойму, если вы там решили переписать полсистему чтобы заменить UDF на встроенную функцию, то какая вам разница, что придётся индексы переделывать на обычные юники

Та основную систему никто не трогает. Одну из некритических баз решил перевести на 3-ку, а поскольку поглядываю на x64, то по "совету друзей" решил заменять UDF типа trim, power и т.д. на встроенные, и дрогнула рука заменить хеш, тем более поле в обоих случаях INT64. На более глубокие переделки нет времени и пока вся эта миграция на 3-ку на "добровольных началах".
...
Рейтинг: 0 / 0
04.02.2016, 13:53
| Ответить | Цитировать | Написать  
функция hash
    #39162939
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Dimitry Sibiryakov,

но в плане их использования в качестве Unique ID разница не важна IMHO
...
Рейтинг: 0 / 0
04.02.2016, 13:57
| Ответить | Цитировать | Написать  
функция hash
    #39162941
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Чудо
 

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
#include <stdio.h>

unsigned long ElfHash ( const unsigned char *s )
{
    unsigned long   h = 0, high;
    while ( *s )
    {
        h = ( h << 4 ) + *s++;
        if ( high = h & 0xF0000000 )
            h ^= high >> 24;
        h &= ~high;
    }
    return h;
}

void main()
{
	const unsigned char arl[] = "АРЛЕТ";
	const unsigned char bal[] = "БАЛЕТ";

	printf("%u\n", ElfHash(arl));
	printf("%u\n", ElfHash(bal));

}


D:\VSProjects\elfhash>elfhash.exe
13490210
13490210

Вообще то четырехбайтный хэш это как то слабовато для БД
...
Рейтинг: 0 / 0
04.02.2016, 13:59
| Ответить | Цитировать | Написать  
функция hash
    #39162942
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Ariochно в плане их использования в качестве Unique ID разница не важна IMHO

Это ты как-то неправильно понимаешь идею использования хэша...
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
04.02.2016, 13:59
| Ответить | Цитировать | Написать  
функция hash
    #39163483
Фотография Tonal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tonal
Участник
Siemargl,
Чудо не случилось:
Код: sql
1.
2.
3.
4.
$ g++ -Wall -O3 -o elfhash elfhash.cpp
$ ./elfhash
228925186
228924466


У тебя исходник в cp1251, а у меня в utf-8. :)
О чём тут неоднократно писали.
...
Рейтинг: 0 / 0
05.02.2016, 08:20
| Ответить | Цитировать | Написать  
функция hash
    #39163537
WildSery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WildSery
Участник
Viktor_bs:) Как по-вашему это (уникальность строк) нужно было делать?Зависит от контекста задачи.
Уникальность текстовых строк (а не каких-нибудь строковых кодов) сама по себе задача редкая и с кучей нюансов в каждом конкретном случае.
...
Рейтинг: 0 / 0
05.02.2016, 09:37
| Ответить | Цитировать | Написать  
функция hash
    #39163681
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Dimitry Sibiryakov,

при чём тут вообещ хэш, если я говорил о GUID ?
...
Рейтинг: 0 / 0
05.02.2016, 11:22
| Ответить | Цитировать | Написать  
функция hash
    #39163742
WildSery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WildSery
Участник
Arioch,

Сперва искусственно ввёл в беседу о хеше GUID, и теперь заявляешь "при чём тут хеш"?
Не веди так дискуссию.
...
Рейтинг: 0 / 0
05.02.2016, 12:11
| Ответить | Цитировать | Написать  
функция hash
    #39163758
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
TonalSiemargl,
Чудо не случилось:
Код: sql
1.
2.
3.
4.
$ g++ -Wall -O3 -o elfhash elfhash.cpp
$ ./elfhash
228925186
228924466


У тебя исходник в cp1251, а у меня в utf-8. :)
О чём тут неоднократно писали.
Чудо в том, что алгоритм соответствует и дает тот же результат (у меня).

Кстати, у тебя то не совпал результат - должно быть
HASHHASH114 970 874 536 61014 974 901 068 450 - разбирайся где напортачил, не смог правильно скомпилировать 3 строки? =)

И разверну мысль - для 4х байтного хэша слишком высокая вероятность коллизий для СУБД, которые оперируют сотнями миллионов записей.
...
Рейтинг: 0 / 0
05.02.2016, 12:20
| Ответить | Цитировать | Написать  
функция hash
    #39163772
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Siemargl,

вопрос в том для чего ты этот хеш будешь применять. Для паролей в FB используется другой алгоритм.

Если ты говоришь про HASH JOIN (я не знаю какой там алгоритм используется), то там коллизии неизбежны, так как размер хеш таблицы всё равно ограничен, иначе будет гигантский оверхэд по памяти.

Что касается встроенной функции, то она в будущем может быть расширена так чтобы принимать дополнительные необязательные параметры, например алгоритм и др. Но я думаю приоритет данной фичи будет ниже плинтуса.
...
Рейтинг: 0 / 0
05.02.2016, 12:34
| Ответить | Цитировать | Написать  
функция hash
    #39163801
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
ИМНО, для текущего поколения техники 64-бит было бы оптимальным.
...
Рейтинг: 0 / 0
05.02.2016, 12:52
| Ответить | Цитировать | Написать  
функция hash
    #39163815
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
хеш и так 64-битный
...
Рейтинг: 0 / 0
05.02.2016, 13:02
| Ответить | Цитировать | Написать  
функция hash
    #39163947
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
WildSeryСперва искусственно ввёл в беседу о хеше GUID, и теперь заявляешь "при чём тут хеш"?

"хэш" - это что, заклинание такое?

WildSeryХеш - это и есть "алгоритм, предполагающий возникновение коллизии".

одно из двух, либо ты "искусственно ввёл в беседу о хеше" какие-то алгоритмы, либо GUID - это просто (также как и любой хэш) ещё один ЧАСТНЫЙ СЛУЧАЙ "алгоритмa, предполагающий возникновение коллизии". И дело именно в коллизиях, а не в волшебных словах "хэш", "MD5" и прочее
...
Рейтинг: 0 / 0
05.02.2016, 14:09
| Ответить | Цитировать | Написать  
функция hash
    #39163953
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Arioch"хэш" - это что, заклинание такое?
Нет, это точный математический термин.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
05.02.2016, 14:12
| Ответить | Цитировать | Написать  
функция hash
    #39163959
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Dimitry Sibiryakov,

в контекте Unique constraint единственное, что из этого термина важно, это возникновение коллизий.

и random (в том числе GUID), у которого тоже нормально возникновение коллизий, в контексте Unique constraint от хэша отличается только номинально.
...
Рейтинг: 0 / 0
05.02.2016, 14:14
| Ответить | Цитировать | Написать  
функция hash
    #39163962
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Ariochв контекте Unique constraint единственное, что из этого термина важно, это
возникновение коллизий.
Нет, гораздо важнее однозначное соответствие объекту, чья уникальность контролируется.
Собственно, это, в данном случае, жизненно важная характеристика.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
05.02.2016, 14:16
| Ответить | Цитировать | Написать  
функция hash
    #39163968
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Dimitry Sibiryakovоднозначное соответствие объекту

обеспечивается как раз уникальностью поля, будь оно хоть хэшом, хоть целочисленным по генератору, хоть чем угодно вообще, лишь бы уникальным и постоянным для этой строки (в отличии от rdb$key)
...
Рейтинг: 0 / 0
05.02.2016, 14:19
| Ответить | Цитировать | Написать  
функция hash
    #39163981
Гаджимурадов Рустам
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гаджимурадов Рустам
Участник
Arioch> лишь бы уникальным и постоянным для этой строки

А "для какой строки" GUID ?

P.S. Может не надо спорить ради спора?
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
05.02.2016, 14:29
| Ответить | Цитировать | Написать  
функция hash
    #39164158
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Гаджимурадов Рустам,

Для каждой.

Речь иждет про использование в unique-полях принципиально не-unique значений.
...
Рейтинг: 0 / 0
05.02.2016, 16:02
| Ответить | Цитировать | Написать  
функция hash
    #39164168
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
AriochРечь иждет про использование в unique-полях принципиально не-unique значений.

Нет, не об этом идёт речь.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
05.02.2016, 16:05
| Ответить | Цитировать | Написать  
функция hash
    #39164268
Фотография Tonal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tonal
Участник
[quot Siemargl]TonalSiemargl,
Чудо в том, что алгоритм соответствует и дает тот же результат (у меня).

Кстати, у тебя то не совпал результат - должно быть
HASHHASH114 970 874 536 61014 974 901 068 450 - разбирайся где напортачил, не смог правильно скомпилировать 3 строки? =)

После исправления ошибок ( main не может быть void ) и устранения предупреждений в твоём коде, мои результаты соответствуют тестовым:
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
#include <stdio.h>
#include <stdint.h>

uint64_t ElfHash ( const unsigned char *s )
{
    //unsigned long   h = 0, high;
    uint64_t   h = 0, high;
    while ( *s )
    {
        h = ( h << 4 ) + *s++;
        if ( (high = h & 0xF0000000) != 0 )
            h ^= high >> 24;
        h &= ~high;
    }
    return h;
}

int main()
{
	const unsigned char arl[] = "АРЛЕТ";
	const unsigned char bal[] = "БАЛЕТ";
	const unsigned char aaa[] = "jdfgsdhfsdfsd 6445dsfsd7fg/*/+bfjsdgf%$^";

	printf("%lu\n", ElfHash(arl));
	printf("%lu\n", ElfHash(bal));
	printf("%lu\n", ElfHash(aaa));
}


Например отсюда
Код: sql
1.
2.
3.
4.
5.
$ g++ -Wall -O3 -o elfhash elfhash.cpp
$ ./elfhash 
228925186
228924466
248446350


Так что с кодом всё в порядке.
А вот с данными вполне возможны различия. Например если сервер работает с utf данными в utf-16, а не в utf-8, как у меня в исходнике. :)
...
Рейтинг: 0 / 0
05.02.2016, 17:09
| Ответить | Цитировать | Написать  
функция hash
    #39164297
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Tonal,

Неверный ответ.
...
Рейтинг: 0 / 0
05.02.2016, 17:25
| Ответить | Цитировать | Написать  
функция hash
    #39164336
WildSery
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
WildSery
Участник
AriochWildSeryХеш - это и есть "алгоритм, предполагающий возникновение коллизии".
одно из двух, либо ты "искусственно ввёл в беседу о хеше" какие-то алгоритмы, либо GUID - это просто (также как и любой хэш) ещё один ЧАСТНЫЙ СЛУЧАЙ "алгоритмa, предполагающий возникновение коллизии". И дело именно в коллизиях, а не в волшебных словах "хэш", "MD5" и прочее
Я тебе ещё только один раз отвечу без тега.
Разумеется, не все алгоритмы с коллизиями являются хешами. "А есть Б" не означает "Б есть А", это простейшая математика и/или логика.

Прошу вернуться к теме хешей, и не писать оффтоп.
...
Рейтинг: 0 / 0
05.02.2016, 17:50
| Ответить | Цитировать | Написать  
функция hash
    #39164341
dimitr
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
dimitr
Участник
TonalПосле исправления ошибок
если делаешь хеш из 32-битного 64-битный, то меняй и константы 0xF0000000 на 0xF000000000000000 и 24 на 56
...
Рейтинг: 0 / 0
05.02.2016, 17:55
| Ответить | Цитировать | Написать  
функция hash
    #39164414
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
dimitrхеш и так 64-битный
Интересные результаты.

1. Хэш в ФБ похоже что 64-битный судя по результату, но
2. Хэш который Elf - и он же Elf64 на самом деле 32-битный
3. Elf это PJW-32
https://en.wikipedia.org/wiki/PJW_hash_function
https://uclibc.org/docs/elf-64-gen.pdf стр.17
4. Если реализовать PJW-64 то результат расходится с ФБ и с ELF. И коллизии на АРЛЕТ БАЛЕТ нет и в 1251.

Как то так.
Я перевел на С#, чтобы не было расхождения в кодировках
 
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
using System;
using System.Text;

public class ElfHashPrg {


static ulong ElfHash (byte[] s)
{
    ulong   h = 0, high;
    foreach (byte c in s)
    {
        h = ( h << 4 ) + c;
	high = h & 0xF0000000;
        if ( high != 0 )
            h ^= high >> 24;
        h &= ~high;
    }
    return h;
}

static ulong ElfHash64 (byte[] s)
{
    ulong   h = 0, high;
    foreach (byte c in s)
    {
        h = ( h << 8 ) + c;
	high = h & 0xFF00000000000000UL;
        if ( high != 0 )
	{
            h ^= high >> 48;
        h &= ~high;
	}
    }
    return h;
}


public static void Main()
{
	Encoding  enc    = Encoding.UTF8;
//	Encoding  enc    = Encoding.GetEncoding(1251);


	byte[] arl = enc.GetBytes("АРЛЕТ");
	byte[] bal = enc.GetBytes("БАЛЕТ");


	Console.WriteLine(ElfHash(arl));
	Console.WriteLine(ElfHash(bal));

	Console.WriteLine(ElfHash64(arl));
	Console.WriteLine(ElfHash64(bal));

}

}



Ну и наконец статья, что коллизий в ELF слишком много
http://stackoverflow.com/questions/9159851/why-such-a-high-collision-rate-with-my-elf-hash-implementation
...
Рейтинг: 0 / 0
05.02.2016, 18:57
| Ответить | Цитировать | Написать  
функция hash
    #39164421
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
dimitrTonalПосле исправления ошибок
если делаешь хеш из 32-битного 64-битный, то меняй и константы 0xF0000000 на 0xF000000000000000 и 24 на 56

Вот значит, что сделано в ФБ (результат одинаков) и это _неверно_

 
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
static ulong ElfHash64_FB (byte[] s)
{
    ulong   h = 0, high;
    foreach (byte c in s)
    {
        h = ( h << 4 ) + c;
	high = h & 0xF000000000000000UL;
        if ( high != 0 )
	{
            h ^= high >> 56;
        h &= ~high;
	}
    }
    return h;
}


...
Рейтинг: 0 / 0
05.02.2016, 19:02
| Ответить | Цитировать | Написать  
функция hash
    #39164443
Фотография Tonal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tonal
Участник
Siemargl,
Таки, по ходу, разобрались, кто "не умеет компилить". :)

Я, чтоб закрыть все вопросы, перегнал приведённый мной исходник в кодировку cp1251, и получил ровно твои результаты:
Код: sql
1.
2.
3.
4.
5.
$ g++ -Wall -O3 -o elfhash elfhash.cpp
$ ./elfhash 
13490210
13490210
248446350


Так что в данной реализации рояль играет именно кодировка, а не мои "кривые ручки". :)
Заменив на реализацию от dimitr получаем для 1251:
Код: sql
1.
2.
3.
4.
5.
$ g++ -Wall -O3 -o elfhash elfhash.cpp
$ ./elfhash 
13490210
13490210
106287840125083790


и для utf-8
Код: sql
1.
2.
3.
14970874536610
14974901068450
106287840125083790


Т. е. для 1251 значения не меняются от реализации.
...
Рейтинг: 0 / 0
05.02.2016, 19:29
| Ответить | Цитировать | Написать  
функция hash
    #39164449
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Siemarglи это _неверно_
Это уже совершенно пофиг. Любое изменение этой функции сломает все базы, которые ею
пользовались.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
05.02.2016, 19:36
| Ответить | Цитировать | Написать  
функция hash
    #39164483
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Dimitry SibiryakovSiemarglи это _неверно_
Это уже совершенно пофиг. Любое изменение этой функции сломает все базы, которые ею
пользовались.

С одной, стороны "проблемы негров"

С другой - тройка еще не вышла.

Не зря функция называется evlHash [ EvilHash =)
...
Рейтинг: 0 / 0
05.02.2016, 20:15
| Ответить | Цитировать | Написать  
функция hash
    #39164509
Фотография Tonal
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tonal
Участник
Н.да. В этих ваших интернетов поразительное разнообразие реализаций этого хеша для 64 бит. И все даёт разные значения на одинаковых данных. :(
Вот есть же стандартизированные варианты. Тот же CRC CRC-64-ISO и CRC-64-ECMA...
Или взять те же гуглянские cityhash или farmhash .
И вопросов о реализации бы не возникало - всегда с тестовыми данными сравнить можно.
...
Рейтинг: 0 / 0
05.02.2016, 20:48
| Ответить | Цитировать | Написать  
функция hash
    #39164581
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
Пока вы тут дискутировали, я прогнал запрос по 25млн уникальных записей.
Кто угадает количество коллизий? :)
Делайте ставки господа...

P.S. При этом 64-битная хеш-udf отрабатывает отлично.

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

Если и делать, то добавить новую функцию в 3-ке, например тот-же sha1
...
Рейтинг: 0 / 0
05.02.2016, 23:36
| Ответить | Цитировать | Написать  
функция hash
    #39164590
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Viktor_bs,

Это не алгоритм неудачный, это из-за ошибки в реализации он работает чуть лучше чем 32-битный (и то не доказано). Причем чем короче ключ - тем больше % коллизий.
...
Рейтинг: 0 / 0
05.02.2016, 23:57
| Ответить | Цитировать | Написать  
функция hash
    #39164599
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
SiemarglViktor_bs,

Это не алгоритм неудачный, это из-за ошибки в реализации он работает чуть лучше чем 32-битный (и то не доказано). Причем чем короче ключ - тем больше % коллизий.
Та я уже перечитал вашу переписку и понял.
на 15млн записей - 4560 коллизий. Максимальное количество 8, там помимо текста еще и цифры (размерность).
...
Рейтинг: 0 / 0
06.02.2016, 00:04
| Ответить | Цитировать | Написать  
функция hash
    #39164619
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Viktor_bsSiemarglViktor_bs,

Это не алгоритм неудачный, это из-за ошибки в реализации он работает чуть лучше чем 32-битный (и то не доказано). Причем чем короче ключ - тем больше % коллизий.
Та я уже перечитал вашу переписку и понял.
на 15млн записей - 4560 коллизий. Максимальное количество 8, там помимо текста еще и цифры (размерность).
Это достаточно мало, даже лучше чем в статье. Да и на коротких данных применять хэш невыгодно - дольше раз в несколько чем прямое сравнение.
...
Рейтинг: 0 / 0
06.02.2016, 00:39
| Ответить | Цитировать | Написать  
функция hash
    #39165278
_Док_
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
_Док_
Гость
Viktor_bsЕсли и делать, то добавить новую функцию в 3-ке, например тот-же sha1
тоже давно об этом думаю мечтаю ...
...
Рейтинг: 0 / 0
08.02.2016, 10:06
| Ответить | Цитировать | Написать  
функция hash
    #39165313
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
_Док_Viktor_bsЕсли и делать, то добавить новую функцию в 3-ке, например тот-же sha1
тоже давно об этом думаю мечтаю ...

дык в чём проблема сделай и отошли патч. Время ещё есть.
Одному товарищу захотелось вкрутить статистические функции. Он их сделал, отослал патч и в результате они попали в Firebird 3.
...
Рейтинг: 0 / 0
08.02.2016, 10:53
| Ответить | Цитировать | Написать  
функция hash
    #39165324
Arioch
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Arioch
Участник
Симонов Денис,

в 3.0 ? там разве не feature freeze уже полгода как ?

вот в 3.1 тогда будет наверное
...
Рейтинг: 0 / 0
08.02.2016, 11:06
| Ответить | Цитировать | Написать  
функция hash
    #39165354
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Arioch,

3.1 скорее всего не будет вообще. Сразу 4.0 вроде делать собираются.

Ну такая встроенная функция не шибко уж большая фича. Может и прикрутят. Но даже если нет, то никто не отменял:

1. UDF
2. UDR
...
Рейтинг: 0 / 0
08.02.2016, 11:22
| Ответить | Цитировать | Написать  
функция hash
    #39165724
Viktor_bs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Viktor_bs
Участник
Симонов Денис_Док_пропущено...

тоже давно об этом думаю мечтаю ...

дык в чём проблема сделай и отошли патч. Время ещё есть.
Одному товарищу захотелось вкрутить статистические функции. Он их сделал, отослал патч и в результате они попали в Firebird 3.
Можно об этом поподробнее? Можно ссылку на эту инфу?
...
Рейтинг: 0 / 0
08.02.2016, 16:34
| Ответить | Цитировать | Написать  
функция hash
    #39165733
Фотография Симонов Денис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Симонов Денис
Участник
Viktor_bs,

О статистических функциях?

см. CORE-4714 . Их запилил некий Hajime Nakagami и передал патч, который после рихтовки применили.
...
Рейтинг: 0 / 0
08.02.2016, 16:39
| Ответить | Цитировать | Написать  
функция hash
    #39166117
Фотография Док
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Док
Участник
Симонов Денисдык в чём проблема сделай и отошли патч. Время ещё есть.
"Ты не забывай, что у меня в голове опилки. Длинные слова меня только расстраивают."

Винни-Пух и все-все-все ©
...
Рейтинг: 0 / 0
09.02.2016, 00:01
| Ответить | Цитировать | Написать  
79 сообщений из 79, показаны все 4 страниц
  все  
Форумы / Firebird, InterBase [игнор отключен] [закрыт для гостей] / функция hash
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=40&tid=1562357]:
 0ms
get settings:
 11ms
get forum list:
 15ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 40ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 94ms
get tp. blocked users:
 2ms
others: 12ms
total:  199ms
созд. / загр.: 199ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]