Tantangan fungsi hash Tweetable

73

Dalam Anda akan menulis fungsi hash dalam 140 byte 1 atau kurang dari kode sumber. Fungsi hash harus mengambil string ASCII sebagai input, dan mengembalikan integer 24-bit unsigned ([0, 2 24 -1]) sebagai output.

Fungsi hash Anda akan dievaluasi untuk setiap kata dalam kamus Inggris-Inggris 2 yang besar ini . Skor Anda adalah jumlah kata yang berbagi nilai hash dengan kata lain (tabrakan).

Skor terendah menang, dasi rusak oleh poster pertama.

Kasus cobaan

Sebelum mengirim, silakan uji skrip penilaian Anda pada input berikut:

duplicate
duplicate
duplicate
duplicate

Jika memberikan skor selain dari 4, itu buggy.


Aturan klarifikasi:

  1. Fungsi hash Anda harus dijalankan pada string tunggal, bukan seluruh array. Selain itu, fungsi hash Anda mungkin tidak melakukan I / O selain String input dan integer output.
  2. Fungsi hash bawaan atau fungsionalitas serupa (mis. Enkripsi untuk perebutan byte) tidak diizinkan.
  3. Fungsi hash Anda harus deterministik.
  4. Berlawanan dengan kebanyakan kontes lain yang mengoptimalkan secara khusus untuk input penilaian diperbolehkan.

1 Saya sadar Twitter membatasi karakter alih-alih byte, tetapi untuk kesederhanaan kita akan menggunakan byte sebagai batas untuk tantangan ini.
2 Dimodifikasi dari wbritish-huge Debian , menghilangkan kata-kata non-ASCII.

orlp
sumber
11
Llanfairpwllgwyngyllgogerychwyrndrobwllllantysiliogogogoch's? Apa yang ...?
Luis Mendo
8
@DonMuesli en.wikipedia.org/wiki/Llanfairpwllgwyngyll (fakta yang menyenangkan: kata itu juga ada dalam kamus kompresi bawaan Jelly)
Martin Ender
8
Saya pikir Anda harus melarang kamus built-in.
Dennis
4
Untuk referensi: Mengambil 24 MSB dari SHA-512 akan mencapai skor 6816.
Dennis
10
Beberapa perhitungan back-of-the-envelope: Dengan D=340275kata-kata dan R=2^24output hash, hash acak memiliki D^2/(2*R) = 3450pasangan bertabrakan yang diharapkan , beberapa di antaranya tumpang tindih. Ada D^3/(6*R^2) = 23tiga kali lipat bertabrakan yang diharapkan dan jumlah tabrakan yang lebih besar yang dapat diabaikan, yang berarti tiga kali lipat ini cenderung terpisah. Ini memberikan 6829kata-kata yang diharapkan yang memiliki nilai hash, ~ 70tiga kali lipat dan sisanya berpasangan. Deviasi standar diperkirakan 118, jadi mendapatkan <6200dengan hash acak kira-kira acara 5 sigma.
xnor

Jawaban:

11

Baiklah saya akan belajar bahasa golf.

CJam, 140 byte, 3314 kata bertabrakan

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

Menentukan blok (fungsi anonim). Untuk mengujinya, Anda dapat menambahkan qN%%N*Nuntuk mengambil daftar kata yang dipisahkan baris baru di stdin dan menulis daftar hash yang dipisahkan baris baru di stdout. Kode Python Setara:

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 byte, 3535 3396 kata bertabrakan

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

Menentukan fungsi bernama y. Untuk mengujinya, Anda dapat menambahkan jmyd.zuntuk mengambil daftar kata yang dipisahkan baris baru di stdin dan menulis daftar hash yang dipisahkan baris baru di stdout. Kode Python Setara:

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

Batas teoritis

Seberapa baik yang bisa kita harapkan? Berikut adalah plot x, jumlah kata bertabrakan, vs y, entropi dalam byte yang diperlukan untuk mendapatkan paling banyak x kata bertabrakan. Misalnya, titik (2835, 140) memberi tahu kita bahwa fungsi acak paling banyak 2835 kata bertabrakan dengan probabilitas 1/256 ** 140, jadi sangat tidak mungkin bahwa kita akan dapat melakukan jauh lebih baik daripada dengan 140 byte kode.

grafik

Anders Kaseorg
sumber
Analisis batas teoretis yang bagus. Untuk mengalahkan batasan teoretis itu, seseorang mungkin harus menggunakan bahasa dengan fungsi bawaan yang dioptimalkan untuk kamus dalam pertanyaan (yang akan curang). Jika bahasa memiliki hash kriptografi bawaan, batas dapat diubah menjadi metode yang lebih atau kurang konstruktif untuk menemukan solusi optimal. Pertimbangkan ini: $ h (w || c)% 2 ^ {24} $ di mana $ c $ adalah konstanta byte byte. Dalam model oracle acak yang bisa ditunjukkan mendekati optimal dengan probabilitas tinggi. Tentu saja dengan memaksa $ c $ tidak akan layak.
kasperd
Bagaimana Anda menghitung rumus untuk grafik? Sangat menarik!
NikoNyrh
@NikoNyrh Pemrograman dinamis. Mari ( w , c , h ) mewakili negara dengan w kata-kata, yang c yang bertabrakan dengan h hash yang berbeda, dan sisanya w - c semua memiliki hash yang berbeda. Jika kita menambahkan kata acak, status menjadi ( w + 1, c , h ) dengan probabilitas 1 - ( h + w - c ) / 2 ^ 24, atau ( w + 1, c + 1, h ) dengan probabilitas h / 2 ^ 24, atau ( w + 1, c+ 2, h + 1) dengan probabilitas ( w - c ) / 2 ^ 24. Kemudian entropi terakhir yang digambarkan dengan kata-kata bertabrakan x adalah basis log 1/256 dari jumlah probabilitas di negara bagian (340275, c , h ) dengan cx .
Anders Kaseorg
Saya tidak percaya tidak ada yang bertanya bagaimana Anda menemukan fungsi hash? Saya akan sangat tertarik untuk tahu.
Anush
22

Python, 5333 4991

Saya percaya ini adalah pesaing pertama yang mencetak skor secara signifikan lebih baik daripada oracle acak.

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
sumber
1
Sihir! def H(s):n=int(s.encode('hex'),16);return n%...menghemat 5 byte, kalau-kalau Anda bisa menggunakannya entah bagaimana ...
Dennis
3
@ Dennis Saya bisa menggunakan 5 byte untuk membuat string konstan 5 byte lebih lama. Tapi saya harus mulai membangun string konstan dari awal jika saya mengubah panjangnya. Dan saya tidak yakin 5 byte itu akan memberi saya cukup perbaikan sehingga layak untuk memulai membangun string. Saya sudah menghabiskan berjam-jam waktu CPU mengoptimalkan string konstan.
kasperd
@ Dennis Saya kira beberapa byte ekstra akan memberi saya kebebasan untuk menggunakan beberapa karakter dalam pelarian konstan yang perlu. Dengan cara itu saya berpotensi menggunakan beberapa byte tambahan tanpa harus membangun string lagi.
kasperd
7
Jika Anda ingin byte lain 2**24 == 8**8,.
Anders Kaseorg
20

Python 2, 140 byte, 4266 kata bertabrakan

Saya tidak benar-benar ingin memulai dengan byte yang tidak dapat dicetak karena tweetability mereka yang tidak jelas, tetapi saya tidak memulainya. :-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 byte yang dapat dicetak, 4662 4471 4362 bertabrakan kata-kata

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

Terinspirasi oleh bentuk solusi kasperd, jelas — tetapi dengan tambahan penting dari transformasi affine pada ruang modulus, dan parameter yang sama sekali berbeda.

Anders Kaseorg
sumber
+1 Saya tidak menyerah tanpa perlawanan. Tapi saya pikir saya harus berhenti mengoptimalkan solusi saya saat ini dan menemukan pendekatan lain, karena saya tidak akan mengalahkan Anda jika saya terus menggunakan pendekatan saya saat ini untuk mengoptimalkan parameter. Saya akan kembali dengan mengedit solusi saya setelah saya mengalahkan milik Anda ....
kasperd
@kasperd: Luar biasa, bawa. :-P
Anders Kaseorg
1
@AndersKaseorg Bagaimana Anda menemukan string?
ASCII
@AndersKaseorg Saya berhasil mempercepat pencarian parameter saya. Dan saya menghilangkan hambatan yang menyebabkan pencarian saya macet pada solusi suboptimal. Tapi saya masih tidak bisa membuatnya lebih baik daripada 4885. Setelah beberapa merenungkan mengapa saya tidak bisa membuat lebih jauh, saya tiba-tiba menyadari apa yang salah dengan solusi saya dan bagaimana itu bisa diperbaiki. Sekarang transformasi affine dalam solusi Anda sangat masuk akal bagi saya. Saya pikir satu-satunya cara saya dapat mengejar ketinggalan adalah dengan menggunakan transformasi affine sendiri.
kasperd
1
@kasperd: Bagus sekali. Saat mencari string yang lebih baik n%(8**8-ord('…'[n%70]))tanpa perubahan parameter lainnya, saya hanya berhasil mencapai 4995, jadi sepertinya pengoptimal Anda yang baru berhasil menangkap saya. Sekarang ini semakin menarik!
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*+}

Pendekatan ini membagi domain dan codomain menjadi 110 set terpisah, dan mendefinisikan fungsi hash yang sedikit berbeda untuk setiap pasangan.

Penilaian / Verifikasi

$ 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

Port berikut ke Python dapat digunakan dengan cuplikan skor resmi:

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
sumber
1
Saya telah mengirim kode saya ke Python untuk verifikasi yang mudah.
Dennis
Apakah hdalam port Python sesuai dengan built-in CJam?
kasperd
Iya. Ini adalah CJam b(konversi basis).
Dennis
Apakah proses penilaian Anda dalam bash?
GamrCorps
@ GarrCorps Ya, itu Bash.
Dennis
11

Python, 6446 6372


Solusi ini menghasilkan jumlah tumbukan yang lebih rendah daripada semua entri sebelumnya, dan hanya membutuhkan 44 dari 140 byte yang diizinkan untuk kode:

H=lambda s:int(s.encode('hex'),16)%16727401
kasperd
sumber
2
@ mbomb007 pengajuan orlp sendiri tidak %(2**24-1), jadi saya pikir mungkin baik untuk meminta klarifikasi
Sp3000
12
@ mbomb007 Tantangannya mengatakan tidak ada hal seperti itu. Dikatakan fungsi harus mengambil string ASCII sebagai input dan output integer dalam kisaran itu. Terlepas dari input mana yang Anda berikan fungsi saya, output akan berada dalam kisaran itu. Definisi matematis dari fungsi kata tidak mengharuskannya untuk menghasilkan setiap output yang diizinkan. Jika itu yang Anda inginkan istilah matematika yang akan Anda gunakan adalah fungsi surjective. Tetapi kata surjective tidak digunakan dalam persyaratan.
kasperd
@ mbomb007: Tidak ada persyaratan bahwa fungsi hash bersifat surjective. Sebagai contoh, banyak fungsi hash berbasis alamat memori hanya dapat menghasilkan kelipatan dari beberapa daya kecil 2 karena penyelarasan memori, termasuk hash objek default di versi Python yang lebih lama. Banyak fungsi hash bahkan memiliki domain lebih kecil dari codomain, jadi mereka tidak bisa bersifat surjektif.
user2357112
3
@ mbomb007 - Bahkan, mengingat ada jauh lebih banyak jumlah nilai dari [0, 2**24-1]dari ada kata-kata dalam bahasa Inggris, itu akan menjadi matematis tidak mungkin untuk membuat hash mana setiap nilai tunggal dalam kisaran yang mungkin.
Darrel Hoffman
7

CJam, 6273

{49f^245b16777213%}

XOR setiap karakter dengan 49 , kurangi string yang dihasilkan melalui x, y y 245x + y , dan ambil modulo residu 16.777.213 (prime 24-bit terbesar).

Mencetak gol

$ 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
sumber
Saya menerapkan ulang algoritma dalam python dari deskripsi Anda. Saya dapat mengonfirmasi bahwa skor Anda cocok dengan perhitungan skor resmi.
kasperd
7

JavaScript (ES6), 6389

Fungsi hash (105 byte):

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

Fungsi penilaian (NodeJS) (170 byte):

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)

Panggil sebagai node hash.js dictionary.txt, di mana hash.jsskrip, dictionary.txtadalah file teks kamus (tanpa baris akhir akhir), dan Fdidefinisikan sebagai fungsi hashing.

Terima kasih Neil untuk mencukur 9 byte dari fungsi hashing!

Mwr247
sumber
Mengapa penugasan ke a? Juga, bukannya ((...)>>>0)%(1<<24)Anda mungkin bisa menggunakan (...)<<8>>>8.
Neil
@Neil Karena alfabet, dan saya membosankan = P Juga, matematika bitwise bagus! Itu menyelamatkan 7 byte =)
Mwr247
Untung ini bukan kode golf, kalau tidak aku harus memberimu variabel yang tidak digunakan ijuga.
Neil
@Neil Crap> _ <Saya menggunakannya saat menguji beberapa ide hashing alternatif dan lupa untuk menghapus XD Ya, untungnya ini bukan golf, meskipun semua sama, saya akan senang jika saya bisa mengompres fungsi hash dan scoring ke dalam 140 byte yang sama, jadi setiap bit membantu;)
Mwr247
1
@ Sp3000 Gah, saya mengerti maksud Anda. Milik saya tidak menghitung yang ada di sana pada awalnya ketika tabrakan ditemukan. Saya akan memperbaikinya.
Mwr247
5

Mathematica, 6473

Langkah selanjutnya ... alih-alih menjumlahkan kode karakter, kami memperlakukannya sebagai digit angka dasar-151, sebelum mengambilnya modulo 2 24 .

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

Berikut ini skrip pendek untuk menentukan jumlah tabrakan:

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

Saya baru saja mencoba semua pangkalan secara sistematis sejak saat itu 1, dan sejauh ini pangkalan 151 menghasilkan tabrakan paling sedikit. Saya akan mencoba beberapa lagi untuk menurunkan skor sedikit lebih jauh, tetapi pengujiannya agak lambat.

Martin Ender
sumber
5

Javascript (ES5), 6765

Ini adalah CRC24 yang dicukur hingga 140 Bytes. Bisa bermain golf lebih banyak tetapi ingin mendapatkan jawaban saya :)

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 di 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
sumber
Selamat Datang di Programming Puzzles & Code Golf!
Alex A.
... Dan terima kasih atas sambutan hangat @AlexA.!
binarymax
5

Python, 340053

Skor mengerikan dari algoritma yang mengerikan, jawaban ini ada lebih untuk memberikan skrip Python kecil yang menampilkan skor.

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

Untuk mencetak gol:

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
sumber
1
Mungkin bermanfaat untuk memiliki kode penilaian yang menyatakan bahwa nilai kembali dari fungsi hash adalah bilangan bulat dalam rentang yang diizinkan.
kasperd
4

Python, 6390 6376 6359

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

Dapat dianggap sebagai modifikasi sepele untuk jawaban Martin Büttner .

Khusus ASCII
sumber
3
@ mbomb007 Itu tidak benar. Jika fungsi Anda selalu menghasilkan 4, itu masih menghasilkan dalam kisaran [0, 2**24-1]. Satu-satunya hal yang tidak diperbolehkan adalah mengeluarkan nomor apa pun yang tidak di dalam rentang itu, misalnya -1atau 2**24.
orlp
3

Python, 9310


Ya, bukan yang terbaik, tapi setidaknya itu adalah sesuatu. Seperti yang kami katakan di crypto, jangan pernah menulis fungsi hash Anda sendiri .

Panjangnya persis 140 byte, juga.

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))
Tuan Umum
sumber
2

Matlab, 30.828 8620 6848

Ini membangun hash dengan menetapkan bilangan prima untuk setiap kombo karakter / posisi ascii dan menghitung produk mereka untuk setiap kata modulo, bilangan prima terbesar yang lebih kecil dari 2 ^ 24. Perhatikan bahwa untuk pengujian saya memindahkan panggilan ke bilangan prima di luar ke tester langsung sebelum loop sementara dan meneruskannya ke fungsi hash, karena mempercepatnya dengan faktor sekitar 1000, tetapi versi ini berfungsi, dan mandiri. Mungkin macet dengan kata-kata yang lebih panjang dari sekitar 40 karakter.

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

Penguji:

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
Pelihat Godric
sumber
Jika Anda ingin menghemat ruang dalam program Anda, Anda tidak perlu mengonversi char Anda menjadi doubleeksplisit. Anda juga bisa menggunakan numeldaripada length. Tidak yakin apa yang akan Anda lakukan dengan semua byte ekstra itu!
Suever
1

Ruby, 9309 tabrakan, 107 byte

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 

Bukan pesaing yang baik, tetapi saya ingin menjelajahi ide yang berbeda dari entri lain.

Tetapkan n primes pertama ke posisi n pertama dari string, kemudian jumlahkan semua prima [i] ** (kode ascii dari string [i]), lalu mod 2 ** 24-1.

jose_castro_arnaud
sumber
1

Java 8, 7054 6467

Ini terinspirasi oleh (tetapi tidak disalin dari) fungsi java.lang.String.hashCode bawaan, jadi silakan larang sesuai dengan aturan # 2.

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

Untuk mencetak gol:

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
sumber
@muddyfish, bisakah Anda melihat versi saat ini? Saya pikir ive menyumbang 3-cara-tabrakan dan saya masih mendapatkan hasil yang sama.
Bewusstsein
Ini tidak memperhitungkan tabrakan tiga arah. Jika Anda mengganti hashesdengan Map<Integer, Integer> hashes = new HashMap<>()dan kemudian menghitung jumlah kata untuk setiap hash, Anda dapat menjelaskannya dengan benar.
Peter Taylor
Skor Anda masih terlihat salah. Saya pikir untuk menghitung skor yang benar, Anda harus menampilkan numHash + numCollisions. (Yang saya kira akan menempatkan Anda dekat dengan perkiraan 6832 saya untuk ramalan acak.)
kasperd
Ubah porsi penilaian untuk ini: pastebin.com/nLeg4qut
TheNumberOne
ya, perbaiki penilaian dan sepertinya nilai yang jauh lebih masuk akal sekarang, ty
Bewusstsein
1

Python, 6995 6862 6732

Hanya fungsi RSA sederhana. Cukup lemah, tetapi mengalahkan beberapa jawaban.

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)
Biru
sumber
1

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

Saya menerapkan algoritma genetik yang naif untuk array koefisien saya. Saya akan memperbarui kode ini karena menemukan yang lebih baik. :)

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

Fungsi tes:

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;
}
halus
sumber
1

C #, 6251 6335

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

Konstanta 533 dan 733 889 dan 155 memberikan skor terbaik dari semua yang saya cari sejauh ini.

bmm6o
sumber
1

tcl

88 byte, 6448/3233 tabrakan

Saya melihat orang-orang telah menghitung jumlah kata yang bertabrakan, atau jumlah kata yang ditempatkan dalam ember kosong. Saya memberikan kedua hitungan - yang pertama sesuai dengan spesifikasi masalah, dan yang kedua adalah apa yang dilaporkan lebih banyak poster.

# 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
sumber
2
Di mana Anda melihat jawaban menggunakan metode yang salah untuk menghitung skor? Sudah banyak, tetapi semuanya sudah diperbaiki atau dihapus tahun lalu. Saya melihat empat jawaban tersisa dengan skor kurang dari 6000 karena keempat jawaban itu sebenarnya telah dioptimalkan untuk mendapatkan skor yang rendah.
kasperd
1
Sejauh yang saya tahu, kode Anda proc H w {incr h;lmap c [split $w {}] {set h [expr (2551*$h+[scan $c %c])%2**24]};set h}... benar?
Erik the Outgolfer
@EriktheOutgolfer: Ya, itu
sergiol
1
I second @kasperd: Dapatkah Anda menunjukkan jawaban apa yang tidak memperhitungkan tabrakan sesuai dengan spesifikasi pertanyaan? Apakah Anda benar-benar mencoba menjalankannya?
sergiol
1

Python 3, 89 byte, 6534 tabrakan hash

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

Semua angka ajaib besar yang Anda lihat di sini adalah konstanta fudge.

Magenta
sumber
1

JavaScript, 121 byte, 3268 3250 3244 6354 (3185) tabrakan

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}

Parameter (13, 7809064, 380886, 2, 266324) adalah dengan coba-coba.

Masih dapat dioptimalkan menurut saya, dan masih ada ruang untuk menambahkan parameter tambahan, bekerja untuk pengoptimalan lebih lanjut ...

Verifikasi

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 - Mengubah parameter ke-3 dari 380713 menjadi 380560.

3250> 3244 - Mengubah parameter ke-3 dari 380560 menjadi 380886.

3244> 6354 - Mengubah parameter ke-2 dari 7809143 menjadi 7809064, dan menemukan saya telah menggunakan metode perhitungan yang salah; P

Shieru Asakoto
sumber
1

Berikut adalah beberapa konstruksi serupa, yang cukup "seedable" dan memungkinkan optimasi parameter tambahan. Sial sulit mendapatkan lebih rendah dari 6k! Dengan asumsi skor memiliki rata-rata 6829 dan std dari 118 saya juga menghitung kemungkinan mendapatkan skor rendah seperti itu secara acak.

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 (sesuatu yang berbeda)

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

Ini adalah fungsi hash ad-hoc asli saya, ia memiliki empat parameter yang bisa diubah.

NikoNyrh
sumber
Trik untuk skor rendah adalah konstanta string di mana setiap karakter dapat dioptimalkan secara mandiri tanpa merusak optimasi yang telah Anda lakukan untuk karakter lain.
kasperd
Ya, saya mencoba mengoptimalkan hanya untuk string yang lebih pendek terlebih dahulu, karena menambahkan lebih banyak karakter ke string "entropi" tidak memengaruhi mereka (setelah pengganda rdiperbaiki). Tapi tetap saja algoritma pencarian saya pada dasarnya brute force, dan saya tidak yakin apakah pilihan awal dari pengali ritu penting atau tidak.
NikoNyrh
Mungkin hanya mengalikan nilai ASCII tidak membawa cukup entropi ke gim. Banyak algoritma yang mendapat skor bagus tampaknya memiliki bentuk f(n) % (8^8 - g(n)).
NikoNyrh
Ada satu jawaban yang menjelaskan bagaimana ia mendapat serendah 3677. Skor yang bahkan lebih rendah daripada yang memiliki sedikit penjelasan.
kasperd
0

Ruby, 6473 tabrakan, 129 byte

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

Variabel @p diisi dengan semua bilangan prima di bawah 999.

Ini mengubah nilai ascii menjadi bilangan prima dan menjadikan modulo produk mereka prima besar. Faktor fudge dari 179 berkaitan dengan fakta bahwa algoritma asli digunakan untuk menemukan anagram, di mana semua kata yang disusun ulang dari huruf yang sama mendapatkan hash yang sama. Dengan menambahkan faktor dalam loop, itu membuat anagram memiliki kode yang berbeda.

Saya bisa menghapus ** 0,5 (uji sqrt untuk prime) dengan mengorbankan kinerja yang lebih buruk untuk mempersingkat kode. Saya bahkan bisa membuat nomor utama finder dieksekusi dalam loop untuk menghapus sembilan karakter lagi, meninggalkan 115 byte.

Untuk menguji, yang berikut ini mencoba untuk menemukan nilai terbaik untuk faktor fudge di kisaran 1 hingga 300. Ini mengasumsikan bahwa kata file di dalam direktori / 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
sumber
1
Skor tersebut terlihat mencurigakan. Anda yakin menghitung semua kata yang bertabrakan? Beberapa jawaban sebelumnya secara keliru hanya menghitung satu kata untuk setiap nilai hash yang bertabrakan.
kasperd
Kamu mungkin benar. Saya harus mempertimbangkan bagaimana saya menghitung dan melihat apakah itu sama dengan definisi Anda. Saya menghitung berapa banyak kata yang ada dan mengurangi berapa banyak kode unik yang dihasilkan. Jika kata A dan B mendapatkan kode hash yang sama, apakah itu satu atau dua tabrakan? Saya menghitungnya sebagai satu.
Paul Chernoch
1
Saya tidak mendefinisikan fungsi penilaian. Saya baru saja menyalinnya dari contoh jawaban yang diposting oleh pengguna yang sama yang memposting tantangan. Sebagian besar jawaban memiliki skor berkisar antara 6273 dan 6848. Ada beberapa jawaban yang masing-masing membuat kesalahan yang sama dalam perhitungan skor yang mengarah ke perhitungan skor kira-kira setengah dari yang seharusnya. (Persis setengah skor yang benar jika tidak ada kasus tiga kata bertabrakan.)
kasperd
1
Ya, saya melakukan kesalahan yang sama. Saya akan mengubah jawaban saya nanti. Harus naik bus.
Paul Chernoch
Memperbaiki skor.
Paul Chernoch
0

tcl

# 91 byte, 6508 tabrakan

91 byte, 6502 tabrakan

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

Komputer masih melakukan pencarian untuk mengevaluasi jika ada nilai yang menyebabkan tabrakan kurang dari basis 147 875, yang masih merupakan perekam.

sergiol
sumber