Tweetable вызов хэш-функции

73

В этом вы напишите хеш-функцию в 140 байтах 1 или менее исходного кода. Хеш-функция должна принимать строку ASCII в качестве входных данных и возвращать 24-разрядное целое число без знака ([0, 2 24 -1]) в качестве выходных данных.

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

Побеждает наименьшая оценка, разрывается связь с первым постером.

Прецедент

Перед отправкой, пожалуйста, проверьте ваш сценарий оценки на следующем входе:

duplicate
duplicate
duplicate
duplicate

Если он дает любой результат, кроме 4, он глючит.


Уточняющие правила:

  1. Ваша хеш-функция должна выполняться в одной строке, а не во всем массиве. Кроме того, ваша хеш-функция может не выполнять какой-либо другой ввод-вывод, кроме входной строки и выходного целого числа.
  2. Встроенные хеш-функции или аналогичные функции (например, шифрование в байты шифрования) запрещены.
  3. Ваша хеш-функция должна быть детерминированной.
  4. В отличие от большинства других конкурсов, оптимизация специально для подсчета очков разрешена.

1 Я знаю, что Twitter ограничивает символы вместо байтов, но для простоты мы будем использовать байты в качестве ограничения для этой задачи.
2 Изменено из wbritish-огромного Debian , удаляя любые слова, не входящие в ASCII.

orlp
источник
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Что за...?
Луис Мендо
8
@DonMuesli en.wikipedia.org/wiki/Llanfairpwllgwyngyll (забавный факт: это слово также есть во встроенном словаре сжатия Jelly)
Мартин Эндер,
8
Я думаю, что вы должны запретить встроенные словари.
Деннис
4
Для справки: взятие 24 MSB из SHA-512 принесло бы 6816 баллов.
Деннис
10
Некоторые расчеты за пределами конверта: со D=340275словами и R=2^24выходами хэша случайный хеш имеет ожидаемые D^2/(2*R) = 3450сталкивающиеся пары, некоторые из которых перекрываются. Есть ожидаемые D^3/(6*R^2) = 23сталкивающиеся тройки и незначительное число более крупных столкновений, что означает, что эти тройки, вероятно, не пересекаются. Это дает ожидаемые 6829слова, которые имеют общее значение хеша, ~ 70в тройках, а остальные в парах. Стандартное отклонение оценивается в 118, так что получение <6200со случайным хешем - это примерно 5 сигма событий.
XNOR

Ответы:

11

Хорошо, я пойду изучать язык игры в гольф.

CJam, 140 байтов, 3314 встречных слов

00000000: 7b5f 3162 225e d466 4a55 a05e 9f47 fc51  {_1b"^.fJU.^.G.Q
00000010: c45b 4965 3073 72dd e1b4 d887 a4ac bcbd  .[Ie0sr.........
00000020: 9c8f 70ca 2981 b2df 745a 10d0 dfca 6cff  ..p.)...tZ....l.
00000030: 7a3b 64df e730 54b4 b068 8584 5f6c 9f6b  z;d..0T..h.._l.k
00000040: b7f8 7a1f a2d3 b2b8 bcf5 cfa6 1ef7 a55c  ..z............\
00000050: dca8 795c 2492 dc32 1fb6 f449 f9ca f6b7  ..y\$..2...I....
00000060: a2cf 4772 266e ad4f d90c d236 b51d c5d5  ..Gr&n.O...6....
00000070: 5c46 3f9b 7cb4 f195 4efc fe4a ce8d 9aee  \F?.|...N..J....
00000080: 9dbc 223d 6962 3443 2329 257d            .."=ib4C#)%}

Определяет блок (анонимная функция). Для теста, можно добавить , qN%%N*Nчтобы взять новую строку списка разделенных слов на стандартном ввод и запись новой строки списка разделенных хэш на стандартном выводе. Эквивалентный код Python:

b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,ord('^\xd4fJU\xa0^\x9fG\xfcQ\xc4[Ie0sr\xdd\xe1\xb4\xd8\x87\xa4\xac\xbc\xbd\x9c\x8fp\xca)\x81\xb2\xdftZ\x10\xd0\xdf\xcal\xffz;d\xdf\xe70T\xb4\xb0h\x85\x84_l\x9fk\xb7\xf8z\x1f\xa2\xd3\xb2\xb8\xbc\xf5\xcf\xa6\x1e\xf7\xa5\\\xdc\xa8y\\$\x92\xdc2\x1f\xb6\xf4I\xf9\xca\xf6\xb7\xa2\xcfGr&n\xadO\xd9\x0c\xd26\xb5\x1d\xc5\xd5\\F?\x9b|\xb4\xf1\x95N\xfc\xfeJ\xce\x8d\x9a\xee\x9d\xbc'[b(s,1)%125]))%(8**8+1)

Pyth, 140 байтов, 3535 3396 встречных слов

00000000: 4c25 4362 2d68 5e38 2038 2a36 3643 4022  L%Cb-h^8 8*66C@"
00000010: aa07 f29a 27a7 133a 3901 484d 3f9b 1982  ....'..:9.HM?...
00000020: d261 79ab adab 9d92 888c 3012 a280 76cf  .ay.......0...v.
00000030: a2e5 8f81 7039 acee c42e bc18 28d8 efbf  ....p9......(...
00000040: 0ebe 2910 9c90 158e 3742 71b4 bdf5 59c2  ..).....7Bq...Y.
00000050: f90b e291 8673 ea59 6975 10be e750 84c8  .....s.Yiu...P..
00000060: 0b0f e7e8 f591 f628 cefa 1ab3 2e3c 72a3  .......(.....<r.
00000070: 7f09 6190 dbd2 d54e d6d0 d391 a780 ebb6  ..a....N........
00000080: ae86 2d1e 49b0 552e 7522 4362            ..-.I.U.u"Cb

Определяет функцию с именем y. Чтобы проверить, вы можете добавить, jmyd.zчтобы взять список слов, разделенных символом новой строки, в stdin и написать список хэшей, разделенных символом новой строки, в stdout. Эквивалентный код Python:

b=lambda s,a:reduce(lambda n,c:n*a+ord(c),s,0)
f=lambda s:b(s,256)%(8**8+1-66*ord("\xaa\x07\xf2\x9a'\xa7\x13:9\x01HM?\x9b\x19\x82\xd2ay\xab\xad\xab\x9d\x92\x88\x8c0\x12\xa2\x80v\xcf\xa2\xe5\x8f\x81p9\xac\xee\xc4.\xbc\x18(\xd8\xef\xbf\x0e\xbe)\x10\x9c\x90\x15\x8e7Bq\xb4\xbd\xf5Y\xc2\xf9\x0b\xe2\x91\x86s\xeaYiu\x10\xbe\xe7P\x84\xc8\x0b\x0f\xe7\xe8\xf5\x91\xf6(\xce\xfa\x1a\xb3.<r\xa3\x7f\ta\x90\xdb\xd2\xd5N\xd6\xd0\xd3\x91\xa7\x80\xeb\xb6\xae\x86-\x1eI\xb0U.u"[b(s,256)%121]))

Теоретические пределы

Насколько хорошо мы можем ожидать сделать? Здесь представлен график зависимости x от числа сталкивающихся слов и y от энтропии в байтах, необходимой для получения не более x встречных слов. Например, точка (2835, 140) говорит нам, что случайная функция получает не более 2835 сталкивающихся слов с вероятностью 1/256 ** 140, поэтому крайне маловероятно, что мы когда-либо сможем добиться гораздо большего успеха, чем при 140 байты кода.

график

Андерс Касеорг
источник
Хороший анализ теоретических пределов. Чтобы преодолеть этот теоретический предел, вероятно, придется использовать язык со встроенными функциями, оптимизированными для словаря в вопросе (что будет обманом). Если язык имеет встроенный криптографический хэш, предел можно превратить в более или менее конструктивный метод поиска оптимального решения. Учтите это: $ h (w || c)% 2 ^ {24} $, где $ c $ - константа байтовой строки. В случайной модели оракула это может быть показано, что она приближается к оптимальной с высокой вероятностью. Конечно, грубое принуждение к $ c $ было бы невозможным.
Касперд
Как вы рассчитали формулу для графика? Очень интересно!
NikoNyrh
@NikoNyrh Динамическое программирование. Пусть ( w , c , h ) представляет состояние со словами w , из которых c сталкивается с h различными хэшами, а все остальные w - c имеют различные хэши. Если мы добавим случайное слово, состояние станет ( w + 1, c , h ) с вероятностью 1 - ( h + w - c ) / 2 ^ 24 или ( w + 1, c + 1, h ) с вероятностью h / 2 ^ 24 или ( ш + 1, с+ 2, h + 1) с вероятностью ( w - c ) / 2 ^ 24. Тогда конечная энтропия, построенная с помощью х встречных слов, является логарифмической базой 1/256 суммы вероятностей в состояниях (340275, c , h ) с cx .
Андерс Касеорг
Я не могу поверить, что никто не спросил, как вы пришли к хэш-функции? Мне было бы очень интересно узнать.
Ануш
22

Python, 5333 4991

Я считаю, что это первый претендент, который выиграл значительно лучше, чем случайный оракул.

def H(s):n=int(s.encode('hex'),16);return n%(8**8-ord('+%:5O![/5;QwrXsIf]\'k#!__u5O}nQ~{;/~{CutM;ItulA{uOk_7"ud-o?y<Cn~-`bl_Yb'[n%70]))
kasperd
источник
1
Волшебство! def H(s):n=int(s.encode('hex'),16);return n%...сохраняет 5 байтов, в случае, если вы можете использовать их как-то ...
Деннис
3
@Dennis Я мог бы использовать 5 байтов, чтобы сделать строку постоянной на 5 байтов длиннее. Но мне бы пришлось начать с создания константы с нуля, если я изменю длину. И я не уверен, что эти 5 байтов дадут мне достаточно улучшений, так что стоит начать с построения строки. Я потратил часы процессорного времени на оптимизацию строковой константы.
kasperd
@ Денис Я думаю, что несколько дополнительных байтов дадут мне свободу использовать некоторые символы в константе, нуждающейся в экранировании. Таким образом, я мог бы потенциально использовать несколько дополнительных байтов, не создавая строку заново.
kasperd
7
Если вы хотите еще один байт, 2**24 == 8**8.
Андерс Касеорг
20

Python 2, 140 байт, 4266 встречных слов

Я действительно не хотел начинать с непечатных байтов, учитывая их непонятную гибкость, но я не начал. :-П

00000000: efbb bf64 6566 2066 2873 293a 6e3d 696e  ...def f(s):n=in
00000010: 7428 732e 656e 636f 6465 2827 6865 7827  t(s.encode('hex'
00000020: 292c 3336 293b 7265 7475 726e 206e 2528  ),36);return n%(
00000030: 382a 2a38 2b31 2d32 3130 2a6f 7264 2827  8**8+1-210*ord('
00000040: 6f8e 474c 9f5a b49a 01ad c47f cf84 7b53  o.GL.Z........{S
00000050: 49ea c71b 29cb 929a a53b fc62 3afb e38e  I...)....;.b:...
00000060: e533 7360 982a 50a0 2a82 1f7d 768c 7877  .3s`.*P.*..}v.xw
00000070: d78a cb4f c5ef 9bdb 57b4 7745 3a07 8cb0  ...O....W.wE:...
00000080: 868f a927 5b6e 2536 375d 2929            ...'[n%67]))

Python 2, 140 байт для печати, 4662 4471 4362 встречных слова

def f(s):n=int(s.encode('hex'),16);return n%(8**8+3-60*ord('4BZp%(jTvy"WTf.[Lbjk6,-[LVbSvF[Vtw2e,NsR?:VxC0h5%m}F5,%d7Kt5@SxSYX-=$N>'[n%71]))

Вдохновленный формой решения Касперда, очевидно, но с важным добавлением аффинного преобразования в пространстве модулей и совершенно других параметров.

Андерс Касеорг
источник
+1 Я не сдамся без боя. Но я думаю, что должен прекратить оптимизацию моего текущего решения и найти другой подход, потому что я не собираюсь побеждать вас, если я буду продолжать использовать свой текущий подход к оптимизации параметров. Я вернусь с редактированием моего решения, как только я опередил ваше ...
kasperd
@kasperd: Отлично, принеси это. :-P
Андерс Касеорг
1
@AndersKaseorg Как вы находите строку?
Только для ASCII
@AndersKaseorg Мне удалось значительно ускорить поиск параметров. И я устранил препятствие, из-за которого мой поиск застрял на неоптимальных решениях. Но я все еще не мог сделать это лучше, чем 4885. После некоторых размышлений о том, почему я не мог сделать это дальше, я внезапно понял, что не так с моим решением и как это можно исправить. Теперь аффинное преобразование в вашем решении имеет для меня смысл. Я думаю, что единственный способ наверстать упущенное - это использовать аффинное преобразование самостоятельно.
kasperd
1
@kasperd: Очень мило. При поиске лучшей строки n%(8**8-ord('…'[n%70]))без других изменений параметров мне удалось добраться только до 4995, так что, похоже, ваш новый оптимизатор догнал мой. Теперь это становится интереснее!
Андерс Касеорг
16

CJam, 4125 3937 3791 3677

0000000: 7b 5f 39 62 31 31 30 25 5f 22 7d 13 25 77  {_9b110%_"}.%w
000000e: 77 5c 22 0c e1 f5 7b 83 45 85 c0 ed 08 10  w\"...{.E.....
000001c: d3 46 0c 5c 22 59 f8 da 7b f8 18 14 8e 4b  .F.\"Y..{....K
000002a: 3a c1 9e 97 f8 f2 5c 18 21 63 13 c8 d3 86  :.....\.!c....
0000038: 45 8e 64 33 61 50 96 c4 48 ea 54 3b b3 ab  E.d3aP..H.T;..
0000046: bc 90 bc 24 21 20 50 30 85 5f 7d 7d 59 2c  ...$! P0._}}Y,
0000054: 4a 67 88 c8 94 29 1a 1a 1a 0f 38 c5 8a 49  Jg...)....8..I
0000062: 9b 54 90 b3 bd 23 c6 ed 26 ad b6 79 89 6f  .T...#..&..y.o
0000070: bd 2f 44 6c f5 3f ae af 62 9b 22 3d 69 40  ./Dl.?..b."=i@
000007e: 62 31 35 32 35 31 39 25 31 31 30 2a 2b 7d  b152519%110*+}

Этот подход делит домен и кодомен на 110 непересекающихся множеств и определяет несколько отличную хеш-функцию для каждой пары.

Оценка / Проверка

$ echo $LANG
en_US
$ cat gen.cjam
"qN%{_9b110%_"
[125 19 37 119 119 34 12 225 245 123 131 69 133 192 237 8 16 211 70 12 34 89 248 218 123 248 24 20 142 75 58 193 158 151 248 242 92 24 33 99 19 200 211 134 69 142 100 51 97 80 150 196 72 234 84 59 179 171 188 144 188 36 33 32 80 48 133 95 125 125 89 44 74 103 136 200 148 41 26 26 26 15 56 197 138 73 155 84 144 179 189 35 198 237 38 173 182 121 137 111 189 47 68 108 245 63 174 175 98 155]
:c`"=i@b152519%110*+}%N*N"
$ cjam gen.cjam > test.cjam
$ cjam test.cjam < british-english-huge.txt | sort -n > temp
$ head -1 temp
8
$ tail -1 temp
16776899
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(uniq -u < temp | wc -l)
$ echo $[all - unique]
3677

Следующий порт для Python можно использовать с официальным фрагментом скоринга:

h=lambda s,b:len(s)and ord(s[-1])+b*h(s[:-1],b)

def H(s):
 p=h(s,9)%110
 return h(s,ord(
  '}\x13%ww"\x0c\xe1\xf5{\x83E\x85\xc0\xed\x08\x10\xd3F\x0c"Y\xf8\xda{\xf8\x18\x14\x8eK:\xc1\x9e\x97\xf8\xf2\\\x18!c\x13\xc8\xd3\x86E\x8ed3aP\x96\xc4H\xeaT;\xb3\xab\xbc\x90\xbc$! P0\x85_}}Y,Jg\x88\xc8\x94)\x1a\x1a\x1a\x0f8\xc5\x8aI\x9bT\x90\xb3\xbd#\xc6\xed&\xad\xb6y\x89o\xbd/Dl\xf5?\xae\xafb\x9b'
  [p]))%152519*110+p
Деннис
источник
1
Я перенес свой код на Python для легкой проверки.
Деннис
Соответствует ли hэтот порт Python встроенному CJam?
kasperd
Да. Это CJam b(базовая конверсия).
Деннис
Ваш процесс подсчета очков в bash?
GamrCorps
@GamrCorps Да, это Баш.
Деннис
11

Python, 6446 6372


Это решение достигает меньшего количества коллизий, чем все предыдущие записи, и ему требуется только 44 из 140 байтов, разрешенных для кода:

H=lambda s:int(s.encode('hex'),16)%16727401
kasperd
источник
2
@ mbomb007 Орловское собственное представление делает %(2**24-1), так что я думаю, что было бы хорошо попросить разъяснений
Sp3000
12
@ mbomb007 Задача говорит, что нет такой вещи. В нем говорится, что функция должна принимать строку ASCII в качестве входных данных и выводить целое число в этом диапазоне. Независимо от того, какой вход вы дадите моей функции, выход будет в этом диапазоне. Математическое определение функции слова не требует, чтобы она производила все разрешенные выходные данные. Если это то, что вы хотели, математический термин, который вы бы использовали, был сюръективной функцией. Но слово сюръектив не использовалось в требованиях.
kasperd
@ mbomb007: не требуется, чтобы хеш-функции были сюръективными. Например, многие хеш-функции, основанные на адресе памяти, могут выдавать кратные только небольшого значения степени 2 из-за выравнивания памяти, включая хеш-объект по умолчанию в более старых версиях Python. Многие хеш-функции даже имеют меньший домен, чем кодомен, поэтому в любом случае они не могут быть сюръективными.
user2357112
3
@ mbomb007 - На самом деле, учитывая, что числовых значений гораздо больше, [0, 2**24-1]чем слов в английском языке, было бы математически невозможно создать хеш, в котором было бы возможно каждое отдельное значение в этом диапазоне.
Даррел Хоффман
7

CJam, 6273

{49f^245b16777213%}

XOR каждого символа с 49 , уменьшить полученную строку с помощью x, y 5 245x + y и взять остаток по модулю 16 777 213 (наибольшее 24-битное простое число).

счет

$ cat hash.cjam
qN% {49f^245b16777213%} %N*N
$ all=$(wc -l < british-english-huge.txt)
$ unique=$(cjam hash.cjam < british-english-huge.txt | sort | uniq -u | wc -l)
$ echo $[all - unique]
6273
Деннис
источник
Я переопределил алгоритм в Python из вашего описания. Я могу подтвердить, что ваш результат проверяется с помощью официального расчета.
kasperd
7

JavaScript (ES6), 6389

Хеш-функция (105 байт):

s=>[...s.replace(/[A-Z]/g,a=>(b=a.toLowerCase())+b+b)].reduce((a,b)=>(a<<3)*28-a^b.charCodeAt(),0)<<8>>>8

Функция оценки (NodeJS) (170 байт):

h={},c=0,l=require('fs').readFileSync(process.argv[2],'utf8').split('\n').map(a=>h[b=F(a)]=-~h[b])
for(w of Object.getOwnPropertyNames(h)){c+=h[w]>1&&h[w]}
console.log(c)

Вызовите как node hash.js dictionary.txt, где hash.jsнаходится скрипт, dictionary.txtэто текстовый файл словаря (без последней новой строки), и Fон определен как функция хеширования.

Спасибо Нейлу за то, что он убрал 9 байтов из функции хеширования!

Mwr247
источник
Почему назначение на? Также вместо ((...)>>>0)%(1<<24)вас, вероятно, можно использовать (...)<<8>>>8.
Нейл
@Neil Потому что алфавит, и я скучный = P Кроме того, хорошая побитовая раскраска! Это сэкономило 7 байт =)
Mwr247
Хорошо, что это не кодовый гольф, в противном случае мне пришлось бы позвонить вам и за неиспользованную переменную i.
Нейл
@Neil Crap> _ <Я использую это при тестировании некоторых альтернативных идей хеширования и забыл удалить XD Да, хорошо, что это не гольф, хотя все равно, я бы с удовольствием, если бы я мог сжать хэш и функции подсчета очков в те же 140 байтов, так что каждый бит помогает;)
Mwr247
1
@ Sp3000 Гах, я понимаю, что ты имеешь в виду. Шахта не считает тех, кто был там изначально, когда было обнаружено столкновение. Я исправлю это.
Mwr247
5

Mathematica, 6473

Следующий шаг вверх ... вместо суммирования кодов символов мы рассматриваем их как цифры числа base-151, а затем принимаем их по модулю 2 24 .

hash[word_] := Mod[FromDigits[ToCharacterCode @ word, 151], 2^24]

Вот короткий скрипт для определения количества столкновений:

Total[Last /@ DeleteCases[Tally[hash /@ words], {_, 1}]]

Я только что систематически пробовал все базы 1, и до сих пор база 151 дала наименьшее количество столкновений. Я постараюсь еще немного понизить счет, но тестирование немного медленное.

Мартин Эндер
источник
5

Javascript (ES5), 6765

Это CRC24, уменьшенный до 140 байт. Мог бы играть в гольф больше, но хотел получить мой ответ :)

function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

Валидатор в node.js:

var col = new Array(16777215);
var n = 0;

var crc24_140 = 
function(s){c=0xb704ce;i=0;while(s[i]){c^=(s.charCodeAt(i++)&255)<<16;for(j=0;j++<8;){c<<=1;if(c&0x1000000)c^=0x1864cfb}}return c&0xffffff}

require('fs').readFileSync('./dict.txt','utf8').split('\n').map(function(s){ 
    var h = crc24_140(s);
    if (col[h]===1) {
        col[h]=2;
        n+=2;
    } else if (col[h]===2) {
        n++;
    } else {
        col[h]=1;
    }
});

console.log(n);
binarymax
источник
Добро пожаловать в Программирование Пазлов и Code Golf!
Алекс А.
... И спасибо за теплый прием @AlexA.!
binarymax
5

Python, 340053

Ужасная оценка от ужасного алгоритма, этот ответ существует больше, чтобы дать небольшой скрипт на Python, который отображает выигрыш.

H=lambda s:sum(map(ord, s))%(2**24)

Набрать:

hashes = []
with open("british-english-huge.txt") as f:
    for line in f:
        word = line.rstrip("\n")
        hashes.append(H(word))

from collections import Counter
print(sum(v for k, v in Counter(hashes).items() if v > 1))
orlp
источник
1
Может быть полезно, чтобы код оценки утверждал, что возвращаемое значение из хеш-функции является целым числом в допустимом диапазоне.
Касперд
4

Python, 6390 6376 6359

H=lambda s:reduce(lambda a,x:a*178+ord(x),s,0)%(2**24-48)

Можно считать тривиальной модификацией ответа Мартина Бюттнера .

ASCII-только
источник
3
@ mbomb007 Это не правда. Если ваша функция всегда выдает 4, она все еще выводит в диапазоне [0, 2**24-1]. Единственное, что не разрешено, это вывод любого числа, не входящего в этот диапазон, например, -1или 2**24.
orlp
2

Matlab, 30828 8620 6848

Он создает хэш, присваивая простое число каждому комбинированному символу / позиции ascii и вычисляя их произведение для каждого слова по модулю наибольшего простого числа, меньшего, чем 2 ^ 24. Обратите внимание, что для тестирования я переместил вызов простых чисел в тестер непосредственно перед циклом while и передал его в хэш-функцию, поскольку он ускорился примерно в 1000 раз, но эта версия работает и является автономной. Может произойти сбой со словами длиной более 40 символов.

function h = H(s)
p = primes(1e6);
h = 1;
for i=1:length(s)
    h = mod(h*p(double(s(i))*i),16777213);
end
end

Tester:

clc
clear variables
close all

file = fopen('british-english-huge.txt');
hashes = containers.Map('KeyType','uint64','ValueType','uint64');

words = 0;
p = primes(1e6);
while ~feof(file)
    words = words + 1;
    word = fgetl(file);
    hash = H(word,p);
    if hashes.isKey(hash)
        hashes(hash) = hashes(hash) + 1;
    else
        hashes(hash) = 1;
    end
end

collisions = 0;
for key=keys(hashes)

    if hashes(key{1})>1
        collisions = collisions + hashes(key{1});
    end
end
Годрик Провидец
источник
Если вы хотите сэкономить место в вашей программе, вам не нужно doubleявно преобразовывать свой символ . Также вы можете использовать, numelа не length. Не уверен, что вы будете делать со всеми этими дополнительными байтами!
августа
1

Рубин, 9309 столкновений, 107 байт

def hash(s);require'prime';p=Prime.first(70);(0...s.size).reduce(0){|a,i|a+=p[i]**(s[i].ord)}%(2**24-1);end 

Не очень хороший соперник, но я хотел изучить идею, отличную от других.

Присвойте первые n простых чисел первым n позициям строки, затем сложите все простые числа [i] ** (ascii-код строки [i]), затем mod 2 ** 24-1.

jose_castro_arnaud
источник
1

Java 8, 7054, 6467

Это вдохновлено (но не скопировано) встроенной функцией java.lang.String.hashCode, поэтому не стесняйтесь запрещать в соответствии с правилом № 2.

w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

Набрать:

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;

public class TweetableHash {
    public static void main(String[] args) throws Exception {
        List<String> words = Files.readAllLines(Paths.get("british-english-huge.txt"));

        Function<String, Integer> hashFunc = w -> { return w.chars().reduce(53, (acc, c) -> Math.abs(acc * 79 + c)) % 16777216; };

        Map<Integer, Integer> hashes = new HashMap<>();
        for (String word : words) {
            int hash = hashFunc.apply(word);
            if (hash < 0 || hash >= 16777216) {
                throw new Exception("hash too long for word: " + word + " hash: " + hash);
            }

            Integer numOccurences = hashes.get(hash);
            if (numOccurences == null) {
                numOccurences = 0;
            }
            numOccurences++;

            hashes.put(hash, numOccurences);
        }

        int numCollisions = hashes.values().stream().filter(i -> i > 1).reduce(Integer::sum).get();
        System.out.println("num collisions: " + numCollisions);
    }
}
Bewusstsein
источник
@muddyfish не могли бы вы проверить текущую версию? Я думаю, что я учел трехсторонние столкновения и все еще получаю тот же результат.
Bewusstsein
Это не учитывает трехсторонние столкновения. Если заменить hashesс , Map<Integer, Integer> hashes = new HashMap<>()а затем подсчитать количество слов для каждого хэша, вы можете объяснить их правильно.
Питер Тейлор
Ваша оценка все еще выглядит неправильно. Я думаю, чтобы вычислить правильный счет, вы должны вывести numHashes + numCollisions. (Что, я думаю, приблизит вас к моей оценке 6832 для случайного оракула.)
kasperd
Измените
разделы
да, исправил оценку, и теперь это выглядит как более разумное значение, ты
Bewusstsein
1

Python, 6995 6862 6732

Просто простая функция RSA. Довольно хромает, но бьет некоторые ответы.

M=0x5437b3a3b1
P=0x65204c34d
def H(s):
    n=0
    for i in range(len(s)):
        n+=pow(ord(s[i]),P,M)<<i
    return n%(8**8)
синий
источник
1

C ++: 7112 6694 6483 6479 6412 6339 коллизий, 90 байт

Я реализовал наивный генетический алгоритм для моего массива коэффициентов. Я обновлю этот код, так как он находит лучшие. :)

int h(const char*s){uint32_t t=0,p=0;while(*s)t="cJ~Z]q"[p++%6]*t+*s++;return t%16777213;}

Тестовая функция:

int main(void)
{
    std::map<int, int> shared;

    std::string s;
    while (std::cin >> s) {
        shared[h(s.c_str())]++;
    }

    int count = 0;
    for (auto c : shared) {
        if ((c.first & 0xFFFFFF) != c.first) { std::cerr << "invalid hash: " << c.first << std::endl; }
        if (c.second > 1) { count += c.second; }
    }

    std::cout << count << std::endl;
    return 0;
}
пушистый
источник
1

C #, 6251 6335

int H(String s){int h = 733;foreach (char c in s){h = (h * 533 + c);}return h & 0xFFFFFF;}

Константы 533 и 733, 889 и 155 дают лучший результат из всех, которые я искал до сих пор.

bmm6o
источник
1

TCL

88 байтов, 6448/3233 столкновений

Я вижу, что люди подсчитывают либо количество сталкивающихся слов, либо количество слов, помещенных в непустые ведра. Я даю оба счета - первый соответствует спецификации проблемы, а второй - о чем сообщают другие авторы.

# 88 bytes, 6448 collisions, 3233 words in nonempty buckets

puts "[string length {proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}}] bytes"

proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}

# change 2551 above to:
#   7: 85 bytes, 25839 colliding words, 13876 words in nonempty buckets
#   97: 86 bytes, 6541 colliding words, 3283 words in nonempty buckets
#   829: 87 bytes, 6471 colliding words, 3251 words in nonempty buckets


# validation program

set f [open ~/Downloads/british-english-huge.txt r]
set words [split [read $f] \n]
close $f

set have {};                        # dictionary whose keys are hash codes seen
foreach w $words {
    if {$w eq {}} continue
    set h [H $w]
    dict incr have $h
}
set coll 0
dict for {- count} $have {
    if {$count > 1} {
        incr coll $count
    }
}
puts "found $coll collisions"
Кевин Кенни
источник
2
Где вы видите ответы, используя неправильный метод для вычисления балла? Их было много, но все они были исправлены или удалены годы назад. Я вижу четыре ответа, оставшихся с оценками менее 6000, потому что эти четыре ответа на самом деле были оптимизированы, чтобы иметь такие низкие оценки.
Касперд
1
Насколько я могу судить, твой код proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... верно?
Эрик Outgolfer
@EriktheOutgolfer: Да, это так
sergiol
1
Я второй @kasperd: Можете ли вы указать, какие ответы не учитывают коллизии в соответствии со спецификацией вопроса? Вы действительно пытались запустить их?
sergiol
1

Python 3, 89 байтов, 6534 коллизий хешей

def H(x):
 v=846811
 for y in x:
  v=(972023*v+330032^ord(y))%2**24
 return v%2**24

Все большие магические числа, которые вы видите здесь, являются константами выдумки.

фуксин
источник
1

JavaScript, 121 байт, 3268 3250 3244 6354 (3185) коллизий

s=>{v=i=0;[...s].map(z=>{v=((((v*13)+(s.length-i)*7809064+i*380886)/2)^(z.charCodeAt(0)*266324))&16777215;i++});return v}

Параметры (13, 7809064, 380886, 2, 266324) являются методом проб и ошибок.

Я думаю, что все еще можно оптимизировать, и есть место для добавления дополнительных параметров, работающих для дальнейшей оптимизации ...

верификация

hashlist = [];
conflictlist = [];
for (x = 0; x < britain.length; x++) {
    hash = h(britain[x]);                      //britain is the 340725-entry array
    hashlist.push(hash);
}

conflict = 0; now_result = -1;
(sortedlist = sort(hashlist)).map(v => {
    if (v == now_result) {
        conflict++;
        conflictlist.push(v);
    }
    else
        now_result = v;
});

console.log(conflictlist);

var k = 0;
while (k < conflictlist.length) {
    if (k < conflictlist.length - 1 && conflictlist[k] == conflictlist[k+1])
        conflictlist.splice(k,1);
    else
        k++;
}

console.log(conflict + " " + (conflict+conflictlist.length));

3268> 3250 - изменен третий параметр с 380713 на 380560.

3250> 3244 - изменен 3-й параметр с 380560 на 380886.

3244> 6354 - изменил 2-й параметр с 7809143 на 7809064 и обнаружил, что я использовал неправильный метод расчета; P

Сиеру Асакото
источник
1

Вот несколько аналогичных конструкций, которые являются вполне «начальными» и делают возможной оптимизацию дополнительных параметров. Чёрт, сложно получить ниже 6к! Предполагая, что средний балл равен 6829, а средний - 118, я также рассчитал вероятность случайного получения таких низких баллов.

Clojure A, 6019, Pr = 1: 299,5e9

 #(reduce(fn[r i](mod(+(* r 811)i)16777213))(map *(cycle(map int"~:XrBaXYOt3'tH-x^W?-5r:c+l*#*-dtR7WYxr(CZ,R6J7=~vk"))(map int %)))

Clojure B, 6021, Pr = 1: 266.0e9

#(reduce(fn[r i](mod(+(* r 263)i)16777213))(map *(cycle(map int"i@%(J|IXt3&R5K'XOoa+Qk})w<!w[|3MJyZ!=HGzowQlN"))(map int %)(rest(range))))

Clojure C, 6148, Pr = 1: 254.0e6

#(reduce(fn[r i](mod(+(* r 23)i)16777213))(map *(cycle(map int"ZtabAR%H|-KrykQn{]u9f:F}v#OI^so3$x54z2&gwX<S~"))(for[c %](bit-xor(int c)3))))

Clojure, 6431, Pr = 1: 2.69e3 (что-то другое)

#(mod(reduce bit-xor(map(fn[i[a b c]](bit-shift-left(* a b)(mod(+ i b c)19)))(range)(partition 3 1(map int(str"w"%"m")))))16776869)

Это была моя оригинальная специальная хеш-функция, она имеет четыре настраиваемых параметра.

NikoNyrh
источник
Трюк с низким показателем - это строковая константа, в которой каждый символ может быть оптимизирован независимо, не нарушая оптимизацию, которую вы сделали для других символов.
Касперд
Да, я сначала попытался оптимизировать только для более коротких строк, так как добавление большего количества символов в строку «энтропия» не влияет на них (после rфиксированного множителя ). Но все же мой алгоритм поиска по сути является грубой силой, и я не уверен, rважен ли первоначальный выбор множителя или нет.
NikoNyrh,
Может быть, просто умножение значений ASCII не принесет достаточно энтропии в игру. Многие хорошо оцениваемые алгоритмы имеют вид f(n) % (8^8 - g(n)).
NikoNyrh
Есть один ответ, который объясняет, как он упал до 3677. Те, кто набрал баллы даже ниже, имеют мало объяснений.
Касперд
0

Ruby, 6473 столкновения, 129 байтов

h=->(w){@p=@p||(2..999).select{|i|(2..i**0.5).select{|j|i%j==0}==[]};c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+179)%((1<<24)-3)}}

Переменная @p заполнена всеми простыми числами ниже 999.

Это преобразует значения ascii в простые числа и принимает их произведение по модулю большого простого числа. Коэффициент выдумки 179 связан с тем фактом, что оригинальный алгоритм использовался для поиска анаграмм, где все слова, которые являются перестановками одних и тех же букв, получают одинаковый хэш. Добавляя фактор в цикл, он дает анаграммам разные коды.

Я мог бы удалить ** 0,5 (тест sqrt для простого) за счет более низкой производительности, чтобы сократить код. Я мог бы даже выполнить поиск простых чисел в цикле, чтобы удалить еще девять символов, оставив 115 байтов.

Чтобы проверить, следующее пытается найти лучшее значение для коэффициента выдумки в диапазоне от 1 до 300. Предполагается, что файл слова находится в каталоге / tmp:

h=->(w,y){
  @p=@p||(2..999).
    select{|i|(2..i**0.5). 
    select{|j|i%j==0}==[]};
  c=w.chars.reduce(1){|a,s|(a*@p[s.ord%92]+y)%((1<<24)-3)}
}

american_dictionary = "/usr/share/dict/words"
british_dictionary = "/tmp/british-english-huge.txt"
words = (IO.readlines british_dictionary).map{|word| word.chomp}.uniq
wordcount = words.size

fewest_collisions = 9999
(1..300).each do |y|
  whash = Hash.new(0)
  words.each do |w|
    code=h.call(w,y)
    whash[code] += 1
  end
  hashcount = whash.size
  collisions = whash.values.select{|count| count > 1}.inject(:+)
  if (collisions < fewest_collisions)
    puts "y = #{y}. #{collisions} Collisions. #{wordcount} Unique words. #{hashcount} Unique hash values"
    fewest_collisions = collisions
  end
end
Павел Чернох
источник
1
Счет выглядит подозрительно. Вы уверены, что считаете все встречные слова? Несколько предыдущих ответов по ошибке подсчитывали только одно слово для каждого встречного хеш-значения.
kasperd
Вы можете быть правы. Я должен подумать, как я считал, и посмотреть, совпадает ли это с вашим определением. Я считаю количество слов и вычитаю, сколько уникальных хеш-кодов было сгенерировано. Если слова A и B получают одинаковый хэш-код, это одно или два столкновения? Я считаю это как один.
Павел Чернох
1
Я не определил функцию подсчета очков. Я просто скопировал его из примера ответа, отправленного тем же пользователем, который разместил запрос. Большинство ответов имеют оценки в диапазоне от 6273 до 6848. Было несколько ответов, каждый из которых совершал одну и ту же ошибку в вычислении оценки, что приводило к вычислению оценки примерно вдвое меньше, чем должно было быть. (Точно половина правильного результата, если не было случаев трех встречных слов.)
kasperd
1
Да, я сделал ту же ошибку. Я исправлю свой ответ позже. Надо сесть на автобус.
Павел Чернох
Исправлена ​​оценка.
Павел Чернох
0

TCL

# 91 байт, 6508 столкновений

91 байт, 6502 столкновения

proc H s {lmap c [split $s ""] {incr h [expr [scan $c %c]*875**[incr i]]};expr $h&0xFFFFFF}

Компьютер все еще выполняет поиск, чтобы оценить, есть ли значение, которое вызывает меньше коллизий, чем база 147 875, которая по-прежнему является рекордсменом.

sergiol
источник