Défi de fonction de hachage tweetable

73

Dans ce vous écrivez une fonction de hachage dans 140 octets 1 ou moins de code source. La fonction de hachage doit prendre une chaîne ASCII en entrée et renvoyer un entier non signé de 24 bits ([0, 2 24 -1]) en sortie.

Votre fonction de hachage sera évaluée pour chaque mot de ce grand dictionnaire anglais britannique 2 . Votre score est la quantité de mots qui partagent une valeur de hachage avec un autre mot (une collision).

Le score le plus bas gagne, les liens brisés par la première affiche.

Cas de test

Avant de soumettre, veuillez tester votre script de scoring sur l'entrée suivante:

duplicate
duplicate
duplicate
duplicate

S'il donne un score autre que 4, c'est un buggy.


Règles de clarification:

  1. Votre fonction de hachage doit être exécutée sur une seule chaîne, pas sur un tableau entier. En outre, votre fonction de hachage ne peut effectuer aucune autre entrée / sortie que la chaîne d'entrée et le nombre entier de sortie.
  2. Les fonctions de hachage intégrées ou des fonctionnalités similaires (par exemple, le cryptage pour brouiller les octets) sont interdites.
  3. Votre fonction de hachage doit être déterministe.
  4. Contrairement à la plupart des autres concours, l’optimisation spécifique de la notation est autorisée.

1 Je sais que Twitter limite les caractères au lieu d'octets, mais pour des raisons de simplicité, nous utiliserons les octets comme limite pour ce défi.
2 Modifié à partir de la propriété wbritish-huge de Debian , supprimant les mots non-ASCII.

orlp
la source
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Qu'est-ce que ...?
Luis Mendo
8
@DonMuesli fr.wikipedia.org/wiki/Llanfairpwllgwyngyll (fait amusant: ce mot est également dans le dictionnaire de compression intégré de Jelly)
Martin Ender
8
Je pense que vous devriez interdire les dictionnaires intégrés.
Dennis
4
Pour référence: Prendre le 24 MSB de SHA-512 donnerait un score de 6816.
Dennis
10
Quelques calculs en arrière-plan: avec les D=340275mots et R=2^24les sorties de hachage, un hachage aléatoire a des D^2/(2*R) = 3450paires en collision attendues , dont certaines se chevauchent. Des D^3/(6*R^2) = 23triples en collision sont prévus et un nombre négligeable de collisions plus importantes, ce qui signifie que ces triples sont probablement disjoints. Cela donne les 6829mots attendus qui partagent une valeur de hachage, ~ 70en triples et le reste en paires. L’écart type étant estimé à 118, l’obtention <6200d’un hachage aléatoire correspond en gros à un événement de 5 sigma.
xnor

Réponses:

11

Très bien, je vais apprendre une langue de golf.

CJam, 140 octets, 3314 mots en collision

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#)%}

Définit un bloc (fonction anonyme). Pour tester, vous pouvez ajouter qN%%N*Nà prendre la liste de mots séparés par une nouvelle ligne sur stdin et écrire une liste de hachages séparés par une nouvelle ligne sur stdout. Code Python équivalent:

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 octets, 3535 3396 mots en collision

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

Définit une fonction nommée y. Pour tester, vous pouvez ajouter jmyd.zà prendre la liste de mots séparés par une nouvelle ligne sur stdin et écrire une liste de hachages séparés par une nouvelle ligne sur stdout. Code Python équivalent:

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

Limites théoriques

Comment pouvons-nous nous attendre à faire? Voici un graphique de x, le nombre de mots en collision, vs y, l’entropie en octets nécessaire pour obtenir au plus x mots en collision. Par exemple, le point (2835, 140) nous indique qu'une fonction aléatoire obtient au plus 2835 mots en collision avec une probabilité de 1/256 ** 140, il est donc extrêmement improbable que nous puissions jamais faire mieux que cela avec 140 octets de code.

graphique

Anders Kaseorg
la source
Belle analyse des limites théoriques. Pour dépasser cette limite théorique, il faudrait probablement utiliser un langage avec des fonctions intégrées optimisées pour le dictionnaire dans la question (ce serait tricher). Si le langage a un hachage cryptographique intégré, la limite peut être transformée en une méthode plus ou moins constructive pour trouver une solution optimale. Considérez ceci: $ h (w || c)% 2 ^ {24} $ où $ c $ est une constante de chaîne d’octets. Dans un modèle oracle aléatoire, on pourrait montrer que l'approche est proche de l'optimum avec une probabilité élevée. Bien sûr, forcer brutalement le $ c $ ne serait pas réalisable.
Kasperd
Comment avez-vous calculé la formule du graphique? Vraiment intéressant!
NikoNyrh
@NikoNyrh Programmation dynamique. Soit ( w , c , h ) un état avec w mots, dont c entrent en collision avec h hachages distincts, et les w - c restants ont tous des hachages distincts. Si nous ajoutons un mot aléatoire, l’état devient ( w + 1, c , h ) avec une probabilité 1 - ( h + w - c ) / 2 ^ 24, ou ( w + 1, c + 1, h ) avec une probabilité h / 2 ^ 24, ou ( w + 1, c+ 2, h + 1) avec probabilité ( w - c ) / 2 ^ 24. Ensuite, l'entropie finale représentée graphiquement par x mots en collision est la base de journal 1/256 de la somme des probabilités aux états (340275, c , h ) avec cx .
Anders Kaseorg
Je ne peux pas croire que personne ne vous ait demandé comment vous en êtes arrivé à la fonction de hachage? Je serais très intéressé de savoir.
Anush
22

Python, 5333 4991

Je crois que c’est le premier candidat à marquer significativement mieux qu’un oracle aléatoire.

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
la source
1
Sorcellerie! def H(s):n=int(s.encode('hex'),16);return n%...sauve 5 octets, au cas où vous pourriez les utiliser ...
Dennis
3
@ Dennis J'aurais pu utiliser 5 octets pour rendre la chaîne constante de 5 octets plus longue. Mais je devrais recommencer à construire la constante de chaîne à partir de zéro si je change de longueur. Et je ne suis pas sûr que ces 5 octets me donneront suffisamment d’améliorations pour que cela vaille la peine de recommencer à construire la chaîne. J'ai passé des heures de temps processeur à optimiser la constante de chaîne.
kasperd
@ Dennis Je suppose que quelques octets supplémentaires me donneraient la liberté d'utiliser certains caractères dans la constante besoin de s'échapper. De cette façon, je pourrais éventuellement utiliser quelques octets supplémentaires sans avoir à reconstruire la chaîne.
Kasperd
7
Si vous voulez un autre octet, 2**24 == 8**8.
Anders Kaseorg
20

Python 2, 140 octets, 4266 mots en collision

Je ne voulais pas vraiment commencer par les octets non imprimables étant donné leur capacité de tweet incertaine, mais bon, je ne l'ai pas démarré. :-P

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 octets imprimables, 4662 4471 4362 mots en collision

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

Inspiré par la forme de la solution de kasperd, bien sûr, mais avec l’ajout important d’une transformation affine sur l’espace module, ainsi que de paramètres totalement différents.

Anders Kaseorg
la source
+1 je n'abandonne pas sans me battre. Mais je pense que je dois arrêter d’optimiser ma solution actuelle et trouver une autre approche, car je ne vais pas vous battre si je continue à utiliser mon approche actuelle pour optimiser les paramètres. Je serai de retour avec une édition à ma solution une fois que j'ai vaincu le vôtre ....
kasperd
@ kasperd: Génial, amenez-le. :-P
Anders Kaseorg le
1
@ AndersKaseorg Comment trouvez-vous la chaîne?
ASCII seulement
@ AndersKaseorg, j'ai beaucoup accéléré la recherche de paramètres. Et j'ai enlevé un obstacle qui bloquait ma recherche sur des solutions sous-optimales. Mais je ne pouvais toujours pas faire mieux que 4885. Après avoir réfléchi à la raison pour laquelle je ne pouvais pas continuer, j’ai soudain réalisé ce qui ne va pas avec ma solution et comment la réparer. Maintenant, la transformation affine dans votre solution me semble parfaitement logique. Je pense que la seule façon de rattraper mon retard est d’utiliser moi-même une transformation affine.
Kasperd
1
@ Kasperd: Très bien. Lorsque n%(8**8-ord('…'[n%70]))je cherchais une meilleure chaîne sans autre changement de paramètre, je n'avais réussi qu'à obtenir 4995, il semble donc que votre nouvel optimiseur a rattrapé le mien. Maintenant cela devient plus intéressant!
Anders Kaseorg
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*+}

Cette approche divise le domaine et le codomaine en 110 ensembles disjoints et définit une fonction de hachage légèrement différente pour chaque paire.

Notation / Vérification

$ 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

Le port suivant vers Python peut être utilisé avec l'extrait de partition officiel:

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
Dennis
la source
1
J'ai porté mon code en Python pour une vérification facile.
Dennis
Est-ce hque dans ce port Python correspond à un CJam intégré?
Kasperd
Oui. C'est CJam b(conversion de base).
Dennis
Votre processus de notation est-il à Bash?
GamrCorps
@ GamrCorps Oui, c'est Bash.
Dennis
11

Python, 6446 6372


Cette solution génère un nombre de collisions inférieur à toutes les entrées précédentes et ne nécessite que 44 des 140 octets autorisés pour le code:

H=lambda s:int(s.encode('hex'),16)%16727401
Kasperd
la source
2
@ mbomb007 La propre soumission d'ORLP le fait %(2**24-1), alors je pense qu'il serait bon de demander une clarification
Sp3000
12
@ mbomb007 Le défi ne dit rien de tel. Il dit que la fonction doit prendre une chaîne ASCII en entrée et en sortie un entier compris dans cette plage. Quelle que soit l'entrée que vous donnez à ma fonction, la sortie sera dans cette plage. La définition mathématique du mot fonction n’exige pas qu’elle produise toutes les sorties autorisées. Si c'est ce que vous vouliez, le terme mathématique que vous utiliseriez était fonction surjective. Mais le mot surjective n'a pas été utilisé dans les exigences.
kasperd
@ mbomb007: Il n'est pas nécessaire que les fonctions de hachage soient surjectives. Par exemple, de nombreuses fonctions de hachage basées sur une adresse mémoire ne peuvent produire que des multiples d'une puissance faible de 2 en raison de l'alignement de la mémoire, y compris le hachage d'objet par défaut dans les versions antérieures de Python. Beaucoup de fonctions de hachage ont même un domaine plus petit que codomain, elles ne peuvent donc pas être surjectives de toute façon.
user2357112
3
@ mbomb007 - En fait, étant donné qu'il y a beaucoup plus de valeurs numériques [0, 2**24-1]que de mots en anglais, il serait mathématiquement impossible de créer un hachage où chaque valeur de cette plage était possible.
Darrel Hoffman
7

CJam, 6273

{49f^245b16777213%}

XOR chaque caractère avec 49 , réduisez la chaîne résultante via x, y ↦ 245x + y , et prenez le résidu modulo 16 777 213 (le plus grand nombre premier sur 24 bits).

Notation

$ 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
Dennis
la source
J'ai réimplémenté l'algorithme en python à partir de votre description. Je peux confirmer que votre score est vérifié avec le calcul officiel du score.
Kasperd
7

JavaScript (ES6), 6389

La fonction de hachage (105 octets):

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

La fonction de scoring (NodeJS) (170 octets):

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)

Call as node hash.js dictionary.txt, où hash.jsest le script, dictionary.txtest le fichier texte du dictionnaire (sans la nouvelle ligne) et Fest défini comme la fonction de hachage.

Merci Neil d'avoir réduit de 9 octets la fonction de hachage!

Mwr247
la source
Pourquoi l'attribution à un? En outre, au lieu de ((...)>>>0)%(1<<24)vous pouvez probablement utiliser (...)<<8>>>8.
Neil
@Neil Parce que l'alphabet, et je suis ennuyeux = P En outre, belle sympas au niveau des bits! Cela a sauvé 7 octets =)
Mwr247
C'est une bonne chose que ce ne soit pas du code golf, sinon je devrais aussi vous lancer pour la variable inutilisée i.
Neil
@Neil Crap> _ <J'utilise ça en testant quelques idées de hachage alternatives et j'ai oublié de retirer XD Oui, bonne chose que ce ne soit pas un golf, même si, quand même, j'adorerais si je pouvais compresser les fonctions de hachage et de notation dans les mêmes 140 octets, donc chaque bit aide;)
Mwr247
1
@ Sp3000 Gah, je vois ce que vous voulez dire. Le mien ne compte pas ceux qui sont là au départ lorsque la collision est découverte. Je vais arranger ça.
Mwr247
5

Mathematica, 6473

L'étape suivante ... au lieu de faire la somme des codes de caractères, nous les traitons comme les chiffres d'un nombre en base 151, avant de les prendre modulo 2 24 .

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

Voici un court script pour déterminer le nombre de collisions:

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

Je viens d'essayer systématiquement toutes les bases à 1partir de maintenant et jusqu'à présent, la base 151 a donné le moins de collisions. Je vais essayer quelques autres pour faire baisser un peu plus le score, mais les tests sont un peu lents.

Martin Ender
la source
5

Javascript (ES5), 6765

C'est CRC24 réduit à 140 octets. Je pourrais jouer plus au golf mais je voulais obtenir ma réponse :)

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}

Validateur dans 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
la source
Bienvenue dans Programming Puzzles & Code Golf!
Alex A.
... Et merci pour l'accueil chaleureux @AlexA.!
binarymax
5

Python, 340053

Un score terrible d'un algorithme terrible, cette réponse existe plus pour donner un petit script Python qui affiche le scoring.

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

Marquer:

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
la source
1
Il pourrait être utile que le code de scoring indique que la valeur renvoyée par la fonction de hachage est un entier compris dans la plage autorisée.
Kasperd
4

Python, 6390 6376 6359

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

Peut être considéré comme une modification triviale de la réponse de Martin Büttner .

ASCII seulement
la source
3
@ mbomb007 Ce n'est pas vrai. Si votre fonction produit toujours 4, elle émet toujours dans la plage [0, 2**24-1]. La seule chose qui n'est pas autorisée est la sortie d'un nombre non compris dans cette plage, par exemple -1ou 2**24.
orlp
3

Python, 9310


Ouais, pas le meilleur, mais au moins c'est quelque chose. Comme on dit en crypto, n'écrivez jamais votre propre fonction de hachage .

C'est aussi exactement 140 octets de long.

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))
M. Public
la source
2

Matlab, 30828 8620 6848

Il construit le hachage en attribuant un nombre premier à chaque combo caractère / position ascii et en calculant leur produit pour chaque mot modulo le plus grand nombre premier inférieur à 2 ^ 24. Notez que pour le test, j'ai déplacé l'appel directement vers le premier nombre directement dans le testeur avant la boucle while et je l'ai passé dans la fonction de hachage, car il l'a accéléré d'un facteur 1 000 environ, mais cette version fonctionne correctement et est autonome. Il peut tomber en panne avec des mots de plus de 40 caractères environ.

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

Testeur:

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
Godric Seer
la source
Si vous voulez économiser de l'espace dans votre programme, vous n'avez pas à convertir doubleexplicitement votre caractère en. Aussi, vous pouvez utiliser numelplutôt que length. Je ne sais pas ce que vous feriez avec tous ces octets supplémentaires!
Suever
1

Ruby, 9309 collisions, 107 octets

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 

Ce n'est pas un bon candidat, mais je voulais explorer une idée différente de celle des autres participants.

Attribuez les n premiers nombres premiers aux n premières positions de la chaîne, puis additionnez tous les nombres premiers [i] ** (code ascii de la chaîne [i]), puis mod 2 ** 24-1.

jose_castro_arnaud
la source
1

Java 8, 7054 6467

Ceci est inspiré par (mais pas copié à partir de) la fonction intégrée java.lang.String.hashCode, alors n'hésitez pas à refuser selon la règle n ° 2.

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

Marquer:

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
la source
@muddyfish pourriez-vous consulter la version actuelle? Je pense que ive a expliqué les collisions à 3 voies et que j'obtiens toujours le même résultat.
Bewusstsein
Cela ne représente pas les collisions à trois. Si vous remplacez hashespar Map<Integer, Integer> hashes = new HashMap<>(), puis comptez le nombre de mots pour chaque hachage, vous pouvez en rendre compte correctement.
Peter Taylor
Votre score semble toujours incorrect. Je pense que pour calculer un score correct, vous devez générer numHashes + numCollisions. (Ce qui, je suppose, vous rapprochera de mon estimation de 6832 pour un oracle aléatoire.)
kasperd
Modifiez les portions de notation en ceci: pastebin.com/nLeg4qut
TheNumberOne
oui, corrigé le classement et il semble être une valeur beaucoup plus raisonnable maintenant, ty
Bewusstsein
1

Python, 6995 6862 6732

Juste une simple fonction RSA. Assez boiteux, mais bat quelques réponses.

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)
Bleu
la source
1

C ++: 7112 6694 6483 6479 6412 6339 collisions, 90 octets

J'ai mis en œuvre un algorithme génétique naïf pour mon tableau de coefficients. Je mettrai à jour ce code car il en trouve de meilleurs. :)

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

Fonction de test:

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;
}
duveteux
la source
1

C #, 6251 6335

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

Les constantes 533 et 733 889 et 155 donnent le meilleur score parmi toutes celles que j'ai consultées jusqu'à présent.

bmm6o
la source
1

tcl

88 octets, 6448/3233 collisions

Je vois que les gens comptent soit le nombre de mots en collision, soit le nombre de mots placés dans des seaux non vides. Je donne les deux chefs d'accusation - le premier est en fonction de la spécification du problème, et le second est ce que plus d'affiches ont rapporté.

# 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"
Kevin Kenny
la source
2
Où voyez-vous les réponses en utilisant une méthode incorrecte pour calculer le score? Il y en a eu beaucoup, mais ils ont tous été corrigés ou supprimés il y a des années. Je vois quatre réponses restantes avec des scores inférieurs à 6000, car ces quatre réponses ont été optimisées pour obtenir des scores aussi faibles.
Kasperd
1
Autant que je sache, votre code est proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... non?
Erik l'Outgolfer
@EriktheOutgolfer: Oui, c'est ça
sergiol
1
Je seconde @ kasperd: Pouvez-vous indiquer quelles réponses ne rendent pas compte des collisions en fonction de la question spécifiée? Avez-vous vraiment essayé de les exécuter?
sergiol
1

Python 3, 89 octets, 6534 collisions de hachage

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

Tous les grands nombres magiques que vous voyez ici sont des constantes de fudge.

Magenta
la source
1

JavaScript, 121 octets, 3268 3250 3250 3244 6354 (3185) collisions

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}

Les paramètres (13, 7809064, 380886, 2, 266324) sont obtenus par essai et erreur.

Encore optimisable à mon avis, et il reste encore de la place pour ajouter des paramètres supplémentaires et travailler pour une optimisation plus poussée

Vérification

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 - Modification du 3ème paramètre de 380713 à 380560.

3250> 3244 - Modification du troisième paramètre de 380560 à 380886.

3244> 6354 - Modification du deuxième paramètre de 7809143 à 7809064 et constat que j'ai utilisé une méthode de calcul incorrecte; P

Shieru Asakoto
la source
1

Voici quelques constructions similaires, qui sont assez "semences" et permettent l'optimisation incrémentielle des paramètres. Zut, il est difficile de descendre en dessous de 6k! En supposant que le score a une moyenne de 6829 et une valeur standard de 118, j'ai également calculé la probabilité d'obtenir de tels scores bas par hasard.

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 (quelque chose de différent)

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

C’était ma fonction de hachage ad-hoc d’origine, elle dispose de quatre paramètres réglables.

NikoNyrh
la source
L'astuce pour obtenir un score faible est une constante de chaîne dans laquelle chaque caractère peut être optimisé indépendamment sans ruiner l'optimisation que vous avez effectuée pour les autres personnages.
Kasperd
Oui, j'ai d'abord essayé d'optimiser les chaînes les plus courtes, car l'ajout de caractères supplémentaires à la chaîne "entropie" n'affecte pas celles-ci (une fois que le multiplicateur de rest fixé). Mais mon algorithme de recherche est toujours essentiellement la force brute, et je ne suis pas sûr si le choix initial du multiplicateur de rest important ou non.
NikoNyrh
Peut-être que simplement multiplier les valeurs ASCII n'apporte pas assez d'entropie au jeu. Beaucoup d'algorithmes bien marqués semblent avoir la forme f(n) % (8^8 - g(n)).
NikoNyrh
Il y a une réponse qui explique comment il est passé aussi bas que 3677. Ceux qui obtiennent un score encore plus bas que celui-ci ont peu d'explication.
Kasperd
0

Ruby, 6473 collisions, 129 octets

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

La variable @p est remplie avec tous les nombres premiers inférieurs à 999.

Cela convertit les valeurs ascii en nombres premiers et leur produit modulo un nombre premier élevé. Le facteur de fudge de 179 tient compte du fait que l'algorithme d'origine était utilisé pour rechercher des anagrammes, où tous les mots qui sont des réarrangements des mêmes lettres ont le même hachage. En ajoutant le facteur dans la boucle, les anagrammes ont des codes distincts.

Je pourrais supprimer le ** 0.5 (test sqrt pour prime) au détriment de performances plus médiocres pour raccourcir le code. Je pourrais même faire exécuter le sélecteur de nombre premier dans la boucle pour supprimer neuf caractères supplémentaires, en laissant 115 octets.

Pour tester, les éléments suivants tentent de trouver la meilleure valeur pour le facteur de fudge dans la plage allant de 1 à 300. Supposons que le mot se trouve dans le répertoire / 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
Paul Chernoch
la source
1
Le score semble suspect. Êtes-vous sûr de compter tous les mots qui entrent en collision? Plusieurs réponses précédentes ne comptaient par erreur qu'un seul mot pour chaque valeur de hachage en collision.
Kasperd
Vous pouvez avoir raison. Je dois considérer comment j'ai compté et voir si c'est la même chose que votre définition. Je compte le nombre de mots et soustrais le nombre de codes de hachage uniques générés. Si les mots A et B ont le même hashcode, s'agit-il d'une collision ou de deux? Je le compte comme un.
Paul Chernoch
1
Je n'ai pas défini la fonction de notation. Je viens de le copier à partir de l'exemple de réponse posté par le même utilisateur qui a posté le défi. La plupart des réponses ont des scores compris entre 6273 et 6848. Il y a eu plusieurs réponses faisant chacune la même erreur dans le calcul du score, ce qui a conduit à calculer un score approximativement égal à la moitié de ce qu'il aurait dû être. (Exactement la moitié du score correct s'il n'y a pas de cas de trois mots en collision.)
kasperd
1
Oui, j'ai commis la même erreur. Je vais modifier ma réponse plus tard. Je dois attraper un bus.
Paul Chernoch
Correction de la notation.
Paul Chernoch
0

tcl

# 91 octets, 6508 collisions

91 octets, 6502 collisions

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

L’ordinateur effectue toujours une recherche pour déterminer s’il existe une valeur causant moins de collisions que la base 147 875, qui est toujours l’architecte.

sergiol
la source