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

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

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

Прецедент

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

duplicate
duplicate
duplicate
duplicate

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

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

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

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

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

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 байты кода.

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]))

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]))

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

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

Python, 6446 6372

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

H=lambda s:int(s.encode('hex'),16)%16727401

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

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 байтов из функции хеширования!

Mathematica, 6473

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

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

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

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

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

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);

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))

Python, 6390 6376 6359

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

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

Питон, 9310

Да, не самый лучший, но, по крайней мере, это что-то. Как мы говорим в крипто, никогда не пишите свою собственную хеш-функцию .

Это также ровно 140 байтов.

F=lambda x,o=ord,m=map:int((int(''.join(m(lambda z:str(o(z)^o(x[-x.find(z)])^o(x[o(z)%len(x)])),x)))^(sum(m(int,m(o,x))))^o(x[-1]))%(2**24))

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

Рубин, 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.

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);
    }
}

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)

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;
}

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 дают лучший результат из всех, которые я искал до сих пор.

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"

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

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

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

Вот несколько аналогичных конструкций, которые являются вполне «начальными» и делают возможной оптимизацию дополнительных параметров. Чёрт, сложно получить ниже 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)

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

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

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, которая по-прежнему является рекордсменом.