Reto de función hash tweetable

73

En este , escribirá una función hash en 140 bytes 1 o menos del código fuente. La función hash debe tomar una cadena ASCII como entrada y devolver un entero sin signo de 24 bits ([0, 2 24 -1]) como salida.

Su función hash será evaluada para cada palabra en este gran diccionario de inglés británico 2 . Su puntaje es la cantidad de palabras que comparten un valor hash con otra palabra (una colisión).

El puntaje más bajo gana, lazos rotos por el primer cartel.

Caso de prueba

Antes de enviar, pruebe su secuencia de comandos de puntuación en la siguiente entrada:

duplicate
duplicate
duplicate
duplicate

Si le da un puntaje que no sea 4, tiene errores.


Reglas aclaratorias:

  1. Su función hash debe ejecutarse en una sola cadena, no en una matriz completa. Además, su función hash no puede hacer ninguna otra E / S que la cadena de entrada y el entero de salida.
  2. Las funciones hash incorporadas o una funcionalidad similar (por ejemplo, cifrado para codificar bytes) no está permitido.
  3. Su función hash debe ser determinista.
  4. Contrariamente a la mayoría de los otros concursos, se permite la optimización específica para la entrada de puntuación.

1 Sé que Twitter limita los caracteres en lugar de los bytes, pero por simplicidad usaremos bytes como límite para este desafío.
2 Modificado de wbritish-huge de Debian , eliminando cualquier palabra que no sea ASCII.

orlp
fuente
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Que...?
Luis Mendo
8
@DonMuesli en.wikipedia.org/wiki/Llanfairpwllgwyngyll (hecho curioso : esa palabra también está en el diccionario de compresión incorporado de Jelly)
Martin Ender
8
Creo que deberías rechazar los diccionarios integrados.
Dennis
44
Como referencia: Tomar 24 MSB de SHA-512 alcanzaría un puntaje de 6816.
Dennis
10
Algunos cálculos al final de la envoltura: con D=340275palabras y R=2^24salidas hash, un hash aleatorio tiene D^2/(2*R) = 3450pares de colisión esperados , algunos de los cuales se superponen. Hay un D^3/(6*R^2) = 23triple de colisión esperado y un número insignificante de colisiones más grandes, lo que significa que estos triples son probablemente disjuntos. Esto da unas 6829palabras esperadas que comparten un valor hash, ~ 70en triples y el resto en pares. La desviación estándar se estima en 118, por lo que obtener <6200un hash aleatorio es aproximadamente un evento de 5 sigma.
xnor

Respuestas:

11

Muy bien, iré a aprender un idioma de golf.

CJam, 140 bytes, 3314 palabras en colisión

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

Define un bloque (función anónima). Para probar, puede agregar qN%%N*Npara tomar la lista de palabras separadas por nueva línea en stdin y escribir una lista de hashes separados por nueva línea en stdout. Código de Python equivalente:

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 bytes, 3535 3396 palabras en colisión

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

Define una función llamada y. Para probar, puede agregar jmyd.zpara tomar la lista de palabras separadas por nueva línea en stdin y escribir una lista de hashes separados por nueva línea en stdout. Código de Python equivalente:

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

Límites teóricos

¿Qué tan bien podemos esperar hacer? Aquí hay una gráfica de x, el número de palabras en colisión, frente a y, la entropía en bytes requerida para obtener como máximo x palabras en colisión. Por ejemplo, el punto (2835, 140) nos dice que una función aleatoria obtiene como máximo 2835 palabras en colisión con probabilidad 1/256 ** 140, por lo que es extremadamente improbable que alguna vez podamos hacerlo mucho mejor que eso con 140 bytes de código

grafico

Anders Kaseorg
fuente
Buen análisis de los límites teóricos. Para superar ese límite teórico, uno probablemente tendría que usar un lenguaje con funciones integradas optimizadas para el diccionario en la pregunta (que sería hacer trampa). Si el lenguaje tiene un hash criptográfico incorporado, el límite puede convertirse en un método más o menos constructivo para encontrar una solución óptima. Considere esto: $ h (w || c)% 2 ^ {24} $ donde $ c $ es una cadena de bytes constante. En un modelo de oráculo aleatorio, se podría demostrar que se acerca al óptimo con alta probabilidad. Por supuesto, la fuerza bruta de los $ c $ no sería factible.
Kasperd
¿Cómo calculó la fórmula para el gráfico? ¡Muy interesante!
NikoNyrh
@NikoNyrh Programación dinámica. Deje ( w , c , h ) representar un estado con w palabras, de las cuales c están colisionando con h hashes distintos, y el resto w - c tienen hashes distintos. Si agregamos una palabra aleatoria, el estado se convierte en ( w + 1, c , h ) con probabilidad 1 - ( h + w - c ) / 2 ^ 24, o ( w + 1, c + 1, h ) con probabilidad h / 2 ^ 24, o ( w + 1, c+ 2, h + 1) con probabilidad ( w - c ) / 2 ^ 24. Entonces, la entropía final graficada con x palabras en colisión es la base logarítmica 1/256 de la suma de probabilidades en los estados (340275, c , h ) con cx .
Anders Kaseorg
No puedo creer que nadie haya preguntado cómo se te ocurrió la función hash. Estaría muy interesado en saberlo.
Anush
22

Python, 5333 4991

Creo que este es el primer contendiente en obtener una puntuación significativamente mejor que un oráculo aleatorio.

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
fuente
1
¡Brujería! def H(s):n=int(s.encode('hex'),16);return n%...ahorra 5 bytes, en caso de que pueda usarlos de alguna manera ...
Dennis
3
@Dennis Podría haber usado 5 bytes para hacer que la cadena sea constante 5 bytes más. Pero tendría que comenzar de nuevo construyendo la cadena constante desde cero si cambio la longitud. Y no estoy seguro de que esos 5 bytes me den una mejora suficiente que valga la pena comenzar a construir la cadena. Ya he pasado horas de tiempo de CPU optimizando la constante de cadena.
kasperd 01 de
@Dennis Supongo que unos pocos bytes adicionales me darían la libertad de usar algunos caracteres en la constante necesidad de escapar. De esa manera, podría usar algunos bytes adicionales sin tener que construir la cadena nuevamente.
Kasperd 01 de
77
Si quieres otro byte, 2**24 == 8**8.
Anders Kaseorg
20

Python 2, 140 bytes, 4266 palabras en colisión

Realmente no quería comenzar con la cuestión de los bytes no imprimibles debido a su capacidad de ajuste clara, pero bueno, no lo comencé. :-PAGS

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 bytes imprimibles, 4662 4471 4362 palabras en colisión

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

Inspirado por la forma de la solución de kasperd, obviamente, pero con la importante adición de una transformación afín en el espacio del módulo y parámetros completamente diferentes.

Anders Kaseorg
fuente
+1 No me rendiré sin pelear. Pero creo que tengo que dejar de optimizar mi solución actual y encontrar otro enfoque, porque no voy a vencerlo si sigo usando mi enfoque actual para optimizar los parámetros. Volveré con una edición de mi solución una vez que haya vencido a la tuya ...
kasperd 02 de
@kasperd: Genial, tráelo. :-P
Anders Kaseorg
1
@AndersKaseorg ¿Cómo encuentras la cadena?
Solo ASCII
@AndersKaseorg Logré acelerar mi búsqueda de parámetros mucho. Y eliminé un obstáculo que causaba que mi búsqueda se atascara en soluciones subóptimas. Pero todavía no podía hacerlo mejor que 4885. Después de reflexionar sobre por qué no podía seguir adelante, de repente me di cuenta de lo que estaba mal con mi solución y cómo se puede solucionar. Ahora la transformación afín en su solución tiene mucho sentido para mí. Creo que la única forma en que puedo ponerme al día es usando una transformación afín yo mismo.
Kasperd
1
@kasperd: Muy bien. Cuando busqué una cadena mejor n%(8**8-ord('…'[n%70]))sin otros cambios de parámetros, solo logré llegar a 4995, por lo que parece que su nuevo optimizador ha alcanzado el mío. ¡Ahora esto se pone más interesante!
Anders Kaseorg el
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*+}

Este enfoque divide el dominio y el codominio en 110 conjuntos disjuntos, y define una función hash ligeramente diferente para cada par.

Puntuación / Verificación

$ 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

El siguiente puerto a Python se puede usar con el fragmento de puntuación oficial:

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
fuente
1
He portado mi código a Python para una fácil verificación.
Dennis
¿ hEn ese puerto de Python corresponde a un CJam incorporado?
kasperd
Si. Es CJam b(conversión de base).
Dennis
¿Tu proceso de puntuación es bash?
GamrCorps
@GamrCorps Sí, eso es Bash.
Dennis
11

Python, 6446 6372


Esta solución logra un recuento de colisiones más bajo que todas las entradas anteriores, y solo necesita 44 de los 140 bytes permitidos para el código:

H=lambda s:int(s.encode('hex'),16)%16727401
Kasperd
fuente
2
La propia presentación de @ mbomb007 orlp sí %(2**24-1), así que creo que sería bueno pedir una aclaración
Sp3000
12
@ mbomb007 El desafío no dice tal cosa. Dice que la función debe tomar una cadena ASCII como entrada y salida de un entero en ese rango. Independientemente de la entrada que le des a mi función, la salida estará en ese rango. La definición matemática de la función de palabra no requiere que produzca todas las salidas permitidas. Si eso es lo que deseabas, el término matemático que usarías era función surjective. Pero la palabra sobrejetivo no se utilizó en los requisitos.
kasperd
@ mbomb007: No es necesario que las funciones hash sean sobreyectivas. Por ejemplo, muchas funciones de hash basadas en direcciones de memoria solo pueden producir múltiplos de una pequeña potencia de 2 debido a la alineación de la memoria, incluido el hash de objeto predeterminado en versiones anteriores de Python. Muchas funciones hash incluso tienen un dominio más pequeño que el codominio, por lo que no podrían ser sobreyectivas de todos modos.
user2357112
3
@ mbomb007 - De hecho, dado que hay muchos más valores numéricos [0, 2**24-1]que palabras en inglés, sería matemáticamente imposible hacer un hash donde todos los valores de ese rango fueran posibles.
Darrel Hoffman el
7

CJam, 6273

{49f^245b16777213%}

XOR cada carácter con 49 , reduzca la cadena resultante a través de x, y ↦ 245x + y , y tome el módulo de residuo 16,777,213 (el primo más grande de 24 bits).

Puntuación

$ 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
fuente
Reimplementé el algoritmo en Python a partir de tu descripción. Puedo confirmar que su puntaje se verifica con el cálculo oficial del puntaje.
kasperd 01 de
7

JavaScript (ES6), 6389

La función hash (105 bytes):

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 función de puntuación (NodeJS) (170 bytes):

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)

Llamar como node hash.js dictionary.txt, donde hash.jsestá el script, dictionary.txtes el archivo de texto del diccionario (sin la nueva línea final), y Fse define como la función de hashing.

¡Gracias Neil por eliminar 9 bytes de la función hash!

Mwr247
fuente
¿Por qué la asignación a un? Además, en lugar de ((...)>>>0)%(1<<24)usted, probablemente pueda usar (...)<<8>>>8.
Neil
@Neil Porque alfabeto, y yo soy aburrido = P ¡Además, algo genial! Eso ahorró 7 bytes =)
Mwr247
Lo bueno es que esto no es golf de código, de lo contrario también tendría que recurrir a la variable no utilizada i.
Neil
@Neil Crap> _ <Lo uso mientras probaba algunas ideas alternativas de hashing y olvidé eliminar XD Sí, bueno, esto no es un golf, aunque de todos modos, me encantaría poder comprimir las funciones de hash y puntuación en los mismos 140 bytes, por lo que cada bit ayuda;)
Mwr247
1
@ Sp3000 Gah, veo a qué te refieres. El mío no cuenta los que están allí inicialmente cuando se encuentra la colisión. Lo arreglaré
Mwr247
5

Mathematica, 6473

El siguiente paso ... en lugar de sumar los códigos de caracteres, los tratamos como los dígitos de un número base-151, antes de tomarlos módulo 2 24 .

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

Aquí hay un breve guión para determinar la cantidad de colisiones:

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

Acabo de probar todas las bases sistemáticamente desde ahora 1, y hasta ahora la base 151 produjo la menor cantidad de colisiones. Intentaré un poco más para bajar un poco más el puntaje, pero la prueba es un poco lenta.

Martin Ender
fuente
5

Javascript (ES5), 6765

Esto es CRC24 reducido a 140 Bytes. Podría jugar más golf pero quería obtener mi respuesta :)

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}

Validator en 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
fuente
¡Bienvenido a Programming Puzzles & Code Golf!
Alex A.
... Y gracias por la cálida bienvenida @AlexA.!
binarymax
5

Python, 340053

Una puntuación terrible de un algoritmo terrible, esta respuesta existe más para dar un pequeño script de Python que muestra la puntuación.

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

Para anotar:

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
fuente
1
Podría ser útil que el código de puntuación afirme que el valor de retorno de la función hash es un número entero en el rango permitido.
Kasperd
4

Python, 6390 6376 6359

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

Puede considerarse una modificación trivial a la respuesta de Martin Büttner .

Solo ASCII
fuente
3
@ mbomb007 Eso no es cierto. Si su función siempre emite 4, todavía se emite en el rango [0, 2**24-1]. Lo único que no está permitido es emitir cualquier número que no esté dentro de ese rango, por ejemplo, -1o 2**24.
orlp
3

Python, 9310


Sí, no el mejor, pero al menos es algo. Como decimos en criptografía, nunca escriba su propia función hash .

Esto es exactamente 140 bytes de largo, también.

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))
Señor público
fuente
2

Matlab, 30828 8620 6848

Construye el hash asignando un número primo a cada combo de carácter / posición ascii y calculando su producto para cada módulo de palabra, el primo más grande menor que 2 ^ 24. Tenga en cuenta que para las pruebas, moví la llamada a primos fuera del probador directamente antes del bucle while y la pasé a la función hash, porque la aceleró en aproximadamente un factor de 1000, pero esta versión funciona y es autónoma. Puede bloquearse con palabras de más de 40 caracteres.

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

Ensayador:

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
Vidente de Godric
fuente
Si desea ahorrar espacio en su programa, no tiene que convertir su char a doubleexplícitamente. También podría usar en numellugar de length. ¡Sin embargo, no estoy seguro de qué haría con todos esos bytes adicionales!
Suever
1

Ruby, 9309 colisiones, 107 bytes

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 

No es un buen contendiente, pero quería explorar una idea diferente de otras entradas.

Asigne los primeros n primos a las primeras n posiciones de la cadena, luego sume todos los primos [i] ** (código ascii de la cadena [i]), luego mod 2 ** 24-1.

jose_castro_arnaud
fuente
1

Java 8, 7054 6467

Esto está inspirado (pero no copiado) de la función incorporada java.lang.String.hashCode, así que siéntase libre de rechazar de acuerdo con la regla # 2.

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

Para anotar:

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
fuente
@muddyfish, ¿podrías consultar la versión actual? Creo que he tenido en cuenta las colisiones de 3 vías y todavía estoy obteniendo el mismo resultado.
Bewusstsein
Esto no tiene en cuenta las colisiones a tres bandas. Si reemplaza hashescon Map<Integer, Integer> hashes = new HashMap<>()y luego cuenta el número de palabras para cada hash, puede explicarlas correctamente.
Peter Taylor
Su puntuación aún parece incorrecta. Creo que para calcular una puntuación correcta, debe generar numHashes + numCollisions. (Lo que supongo que te
acercará
Modifique las porciones de calificación a esto: pastebin.com/nLeg4qut
TheNumberOne
sí, arreglé la calificación y ahora parece un valor mucho más razonable, ty
Bewusstsein
1

Python, 6995 6862 6732

Solo una simple función RSA. Bastante cojo, pero supera algunas respuestas.

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)
Azul
fuente
1

C ++: 7112 6694 6483 6479 6412 6339 colisiones, 90 bytes

Implementé un algoritmo genético ingenuo para mi matriz de coeficientes. Actualizaré este código a medida que encuentre mejores. :)

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

Función de prueba:

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;
}
mullido
fuente
1

C #, 6251 6335

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

Las constantes 533 y 733 889 y 155 dan la mejor puntuación de todas las que he buscado hasta ahora.

bmm6o
fuente
1

tcl

88 bytes, 6448/3233 colisiones

Veo que la gente ha estado contando el número de palabras que colisionan o el número de palabras colocadas en cubos no vacíos. Doy ambos recuentos: el primero está de acuerdo con la especificación del problema, y ​​el segundo es lo que más pósters han estado informando.

# 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
fuente
2
¿Dónde ve las respuestas usando el método incorrecto para calcular la puntuación? Ha habido muchas, pero todas fueron corregidas o eliminadas hace años. Veo cuatro respuestas restantes con puntajes inferiores a 6000 porque esas cuatro respuestas en realidad se han optimizado para tener puntajes tan bajos.
kasperd
1
Por lo que puedo decir, su código es proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... ¿verdad?
Erik the Outgolfer
@EriktheOutgolfer: Sí, lo es
sergiol
1
Segundo @kasperd: ¿Puedes señalar qué respuestas no están contabilizando las colisiones de acuerdo con la especificación de la pregunta? ¿Realmente intentaste ejecutarlos?
sergiol
1

Python 3, 89 bytes, 6534 colisiones hash

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

Todos los grandes números mágicos que ves aquí son constantes falsas.

Magenta
fuente
1

JavaScript, 121 bytes, 3268 3250 3244 6354 (3185) colisiones

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}

Los parámetros (13, 7809064, 380886, 2, 266324) son por prueba y error.

Todavía optimizable, creo, y todavía hay espacio para agregar parámetros adicionales, trabajando para una mayor optimización ...

Verificación

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: se modificó el tercer parámetro de 380713 a 380560.

3250> 3244: se modificó el tercer parámetro de 380560 a 380886.

3244> 6354 - Cambié el segundo parámetro de 7809143 a 7809064, y descubrí que he usado el método de cálculo incorrecto; P

Shieru Asakoto
fuente
1

Aquí hay algunas construcciones similares, que son bastante "visibles" y hacen posible la optimización de parámetros incrementales. ¡Maldición, es difícil bajar de 6k! Suponiendo que el puntaje tiene una media de 6829 y un estándar de 118, también calculé la probabilidad de obtener puntajes tan bajos al azar.

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 (algo diferente)

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

Esta fue mi función hash ad-hoc original, tiene cuatro parámetros ajustables.

NikoNyrh
fuente
El truco para obtener una puntuación baja es una constante de cadena en la que cada personaje se puede optimizar de forma independiente sin arruinar la optimización que ha realizado para los otros personajes.
kasperd el
Sí, primero intenté optimizar solo las cadenas más cortas, ya que agregar más caracteres a la cadena de "entropía" no afecta a esos (una vez que se repara el multiplicador de r). Pero aún así, mi algoritmo de búsqueda es esencialmente fuerza bruta, y no estoy seguro de si la elección inicial del multiplicador de res importante o no.
NikoNyrh
Quizás la simple multiplicación de los valores ASCII no traiga suficiente entropía al juego. Muchos algoritmos de puntuación bien parecen tener la forma f(n) % (8^8 - g(n)).
NikoNyrh
Hay una respuesta que explica cómo llegó tan bajo como 3677. Los que obtuvieron puntajes aún más bajos tienen poca explicación.
kasperd
0

Ruby, 6473 colisiones, 129 bytes

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 se llena con todos los números primos por debajo de 999.

Esto convierte los valores ascii en números primos y toma su módulo de producto como un primo grande. El factor de fudge de 179 trata con el hecho de que el algoritmo original era para usar en la búsqueda de anagramas, donde todas las palabras que son reordenamientos de las mismas letras obtienen el mismo hash. Al agregar el factor en el bucle, hace que los anagramas tengan códigos distintos.

Podría eliminar ** 0.5 (prueba sqrt para prime) a expensas de un peor rendimiento para acortar el código. Incluso podría hacer que el buscador de números primos se ejecute en el bucle para eliminar nueve caracteres más, dejando 115 bytes.

Para probar, lo siguiente intenta encontrar el mejor valor para el factor de fudge en el rango de 1 a 300. Se supone que el archivo de palabras está en el directorio / 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
fuente
1
El puntaje parece sospechoso. ¿Estás seguro de que estás contando todas las palabras que chocan? Varias respuestas anteriores contaron por error solo una palabra por cada valor hash en colisión.
kasperd 01 de
Puede que tengas razón. Debo considerar cómo conté y ver si es lo mismo que su definición. Estoy contando cuántas palabras hay y restando cuántos códigos hash únicos se generaron. Si las palabras A y B obtienen el mismo código hash, ¿es esa una colisión o dos? Lo cuento como uno.
Paul Chernoch
1
No definí la función de puntuación. Acabo de copiarlo de la respuesta de ejemplo publicada por el mismo usuario que publicó el desafío. La mayoría de las respuestas tienen puntajes que oscilan entre 6273 y 6848. Ha habido múltiples respuestas, cada una de las cuales cometió el mismo error en el cálculo del puntaje, lo que llevó a calcular un puntaje de aproximadamente la mitad de lo que debería haber sido. (Exactamente la mitad del puntaje correcto si no hay casos de tres palabras en colisión.)
kasperd
1
Sí, cometí el mismo error. Enmendaré mi respuesta más tarde. Tengo que tomar un autobús.
Paul Chernoch 01 de
Se arregló la puntuación.
Paul Chernoch
0

tcl

# 91 bytes, 6508 colisiones

91 bytes, 6502 colisiones

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

La computadora todavía está realizando una búsqueda para evaluar si hay un valor que causa menos colisiones que la base 147 875, que sigue siendo el registrador.

sergiol
fuente