Mengapa kode hash Java () di String menggunakan 31 sebagai pengganda?

480

Per dokumentasi Java, kode hash untuk Stringobjek dihitung sebagai:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

menggunakan intaritmatika, di mana s[i]adalah saya th karakter string, nadalah panjang string, dan ^menunjukkan eksponensial.

Mengapa 31 digunakan sebagai pengganda?

Saya mengerti bahwa pengganda harus merupakan bilangan prima yang relatif besar. Jadi mengapa tidak 29, atau 37, atau bahkan 97?

Jacobko
sumber
1
Bandingkan juga stackoverflow.com/questions/1835976/… - Saya pikir 31 adalah pilihan yang buruk jika Anda menulis fungsi kode hash Anda sendiri.
Hans-Peter Störr
6
Jika berusia 29, atau 37, atau bahkan 97, Anda akan bertanya 'mengapa tidak 31?'
Marquis of Lorne
2
@ EJP, penting untuk mengetahui alasan di balik pilihan no. kecuali jumlahnya adalah hasil dari trik sulap hitam.
Dushyant Sabharwal
Ada posting blog oleh @ peter-lawrey tentang hal itu di sini: vanilla-java.github.io/2018/08/12/… dan di sini: vanilla-java.github.io/2018/08/15/…
Christophe Roussy
Titik @DushyantSabharwal saya adalah bahwa hal itu bisa saja menjadi 29 atau 37 atau 97, atau 41, atau banyak nilai-nilai lain, tanpa membuat banyak perbedaan praktis. Kami menggunakan 37 pada tahun 1976.
Marquis of Lorne

Jawaban:

405

Menurut Joshua Bloch's Java Efektif (buku yang tidak cukup direkomendasikan, dan yang saya beli terima kasih untuk terus-menerus menyebutkan tentang stackoverflow):

Nilai 31 dipilih karena ini adalah prime yang aneh. Jika itu genap dan multiplikasi meluap, informasi akan hilang, karena penggandaan 2 sama dengan pergeseran. Keuntungan menggunakan prime kurang jelas, tetapi tradisional. Properti yang bagus dari 31 adalah bahwa perkalian dapat digantikan oleh pergeseran dan pengurangan untuk kinerja yang lebih baik: 31 * i == (i << 5) - i. VM modern melakukan optimasi semacam ini secara otomatis.

(dari Bab 3, Butir 9: Selalu menimpa kode hash saat Anda menimpa sama dengan, halaman 48)

matt b
sumber
346
Yah semua bilangan prima aneh, kecuali 2. Katakan saja.
Kip
38
Saya tidak berpikir Bloch mengatakan itu dipilih karena itu adalah prime yang aneh, tetapi karena itu aneh DAN karena itu prima (DAN karena itu dapat dengan mudah dioptimalkan menjadi shift / kurangi).
matt b
50
31 dipilih karena ini perdana yang aneh ??? Itu tidak masuk akal - saya katakan 31 dipilih karena memberikan distribusi terbaik - periksa computinglife.wordpress.com/2008/11/20/…
computinglife
65
Saya pikir pilihan 31 agak disayangkan. Tentu, ini mungkin menghemat beberapa siklus CPU pada mesin lama, tetapi Anda sudah memiliki tabrakan hash pada string ascii pendek seperti "@ dan #!, Atau Ca dan DB. Ini tidak terjadi jika Anda memilih, misalnya, 1327144003, atau pada setidaknya 524287 yang juga memungkinkan bitshift: 524287 * i == i << 19 - i.
Hans-Peter Störr
15
@Jason Lihat jawaban saya stackoverflow.com/questions/1835976/… . Maksud saya adalah: Anda mendapatkan lebih sedikit tabrakan jika Anda menggunakan prime yang lebih besar, dan tidak kehilangan apa-apa hari ini. Masalahnya lebih buruk jika Anda menggunakan bahasa non-Inggris dengan karakter non-ascii yang umum. Dan 31 berfungsi sebagai contoh buruk bagi banyak programmer ketika menulis fungsi kode hash mereka sendiri.
Hans-Peter Störr
80

Seperti Goodrich dan Tamassia tunjukkan, Jika Anda mengambil lebih dari 50.000 kata bahasa Inggris (dibentuk sebagai gabungan dari daftar kata yang disediakan dalam dua varian Unix), menggunakan konstanta 31, 33, 37, 39, dan 41 akan menghasilkan kurang dari 7 tabrakan dalam setiap kasus. Mengetahui hal ini, seharusnya tidak mengejutkan bahwa banyak implementasi Java memilih salah satu dari konstanta ini.

Secara kebetulan, saya tengah membaca bagian "kode hash polinomial" ketika saya melihat pertanyaan ini.

EDIT: di sini ada tautan ke ~ 10mb buku PDF yang saya maksud di atas. Lihat bagian 10.2 Tabel hash (halaman 413) dari Struktur Data dan Algoritma di Jawa

JohnZaj
sumber
6
Namun perhatikan bahwa Anda mungkin mendapatkan collision WAY lebih banyak jika Anda menggunakan rangkaian karakter internasional apa pun dengan karakter umum di luar rentang ASCII. Setidaknya, saya memeriksa ini untuk 31 dan Jerman. Jadi saya pikir pilihan 31 rusak.
Hans-Peter Störr
1
@ jJack, Tautan yang disediakan dalam jawaban Anda rusak.
SK Venkat
Kedua tautan dalam jawaban ini rusak. Juga, argumen dalam paragraf pertama agak tidak lengkap; bagaimana angka ganjil lainnya dibandingkan dengan lima yang Anda cantumkan di tolok ukur ini?
Mark Amery
58

Pada (kebanyakan) prosesor lama, mengalikannya dengan 31 bisa relatif murah. Pada ARM, misalnya, hanya satu instruksi:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

Sebagian besar prosesor lain akan membutuhkan shift dan pengurangan instruksi yang terpisah. Namun, jika pengganda Anda lambat, ini masih merupakan kemenangan. Prosesor modern cenderung memiliki pengganda cepat sehingga tidak membuat banyak perbedaan, asalkan 32 berada di sisi yang benar.

Ini bukan algoritma hash yang hebat, tapi cukup bagus dan lebih baik daripada kode 1.0 (dan jauh lebih baik daripada spesifikasi 1.0!).

Tom Hawtin - tackline
sumber
7
Cukup lucu, perkalian dengan 31 pada mesin desktop saya sebenarnya sedikit lebih lambat daripada perkalian dengan, katakanlah, 92821. Saya kira kompiler mencoba untuk "mengoptimalkan" ke dalam shift dan menambahkan juga. :-)
Hans-Peter Störr
1
Saya tidak berpikir saya pernah menggunakan ARM yang tidak sama cepatnya dengan semua nilai dalam kisaran +/- 255. Penggunaan kekuatan 2 minus satu memiliki efek yang disayangkan bahwa perubahan yang cocok ke dua nilai mengubah kode hash dengan kekuatan dua. Nilai -31 akan lebih baik, dan saya akan berpikir sesuatu seperti -83 (64 + 16 + 2 + 1) mungkin lebih baik (blender bit agak lebih baik).
supercat
@supercat Tidak yakin dengan minus. Sepertinya Anda akan kembali ke nol. / String.hashCodemendahului StrongARM yang, IIRC, memperkenalkan pengali 8-bit dan mungkin meningkat menjadi dua siklus untuk aritmatika / logika gabungan dengan operasi shift.
Tom Hawtin - tackline
1
@ TomHawtin-tackline: Menggunakan 31, hash dari empat nilai akan menjadi 29791 * a + 961 * b + 31 * c + d; menggunakan -31, itu akan menjadi -29791 * a + 961 * b - 31 * c + d. Saya tidak berpikir perbedaannya akan signifikan jika empat item independen, tetapi jika pasangan item yang berdekatan cocok, kode hash yang dihasilkan akan menjadi kontribusi dari semua item yang tidak berpasangan, ditambah beberapa kelipatan 32 (dari yang dipasangkan). Untuk string mungkin tidak terlalu penting, tetapi jika seseorang menulis metode tujuan umum untuk hashing agregasi, situasi di mana item yang berdekatan cocok akan menjadi tidak proporsional.
supercat
3
@supercat asyiknya, kode hash Map.Entrytelah diperbaiki secara spesifik key.hashCode() ^ value.hashCode()meskipun itu bukan pasangan yang tidak teratur, karena keydan valuememiliki arti yang sama sekali berbeda. Ya, itu menyiratkan bahwa Map.of(42, 42).hashCode()atau Map.of("foo", "foo", "bar", "bar").hashCode(), dll, dapat diprediksi nol. Jadi jangan gunakan peta sebagai kunci untuk peta lain ...
Holger
33

Dengan mengalikan, bit digeser ke kiri. Ini menggunakan lebih banyak ruang kode hash yang tersedia, mengurangi tabrakan.

Dengan tidak menggunakan kekuatan dua, bit yang lebih rendah, paling kanan diisi juga, untuk dicampur dengan potongan data berikutnya yang masuk ke hash.

Ekspresi n * 31setara dengan (n << 5) - n.

erickson
sumber
29

Anda dapat membaca alasan asli Bloch di bawah "Komentar" di http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622 . Dia menyelidiki kinerja fungsi hash yang berbeda sehubungan dengan "ukuran rantai rata-rata" yang dihasilkan dalam tabel hash. P(31)adalah salah satu fungsi umum selama waktu itu yang ia temukan dalam buku K&R (tetapi bahkan Kernighan dan Ritchie tidak dapat mengingat dari mana asalnya). Pada akhirnya dia pada dasarnya harus memilih satu dan jadi dia mengambil P(31)karena tampaknya berkinerja cukup baik. Meskipun P(33)tidak terlalu buruk dan perkalian dengan 33 sama cepat untuk dihitung (hanya bergeser 5 dan tambahan), ia memilih 31 karena 33 bukan yang utama:

Dari empat sisanya, saya mungkin akan memilih P (31), karena ini adalah yang termurah untuk dihitung pada mesin RISC (karena 31 adalah perbedaan dua kekuatan dua). P (33) juga murah untuk dihitung, tetapi kinerjanya sedikit lebih buruk, dan 33 adalah komposit, yang membuat saya sedikit gugup.

Jadi alasannya tidak rasional seperti banyak jawaban di sini tampaknya menyiratkan. Tetapi kita semua baik dalam memberikan alasan rasional setelah keputusan usus (dan bahkan Bloch mungkin cenderung untuk itu).

David Ongaro
sumber
2
Penelitian menyeluruh dan jawaban yang tidak memihak!
Vishal K
22

Sebenarnya, 37 akan bekerja dengan cukup baik! z: = 37 * x dapat dihitung sebagai y := x + 8 * x; z := x + 4 * y. Kedua langkah sesuai dengan satu instruksi LEA x86, jadi ini sangat cepat.

Bahkan, perkalian dengan prime 73 yang bahkan lebih besar dapat dilakukan pada kecepatan yang sama dengan pengaturan y := x + 8 * x; z := x + 8 * y.

Menggunakan 73 atau 37 (bukannya 31) mungkin lebih baik, karena mengarah ke kode yang lebih padat : Kedua instruksi LEA hanya mengambil 6 byte vs 7 byte untuk bergerak + shift + kurangi untuk perkalian dengan 31. Salah satu kemungkinan peringatan adalah bahwa 3-argumen instruksi LEA yang digunakan di sini menjadi lebih lambat pada arsitektur jembatan Sandy Intel, dengan latensi meningkat 3 siklus.

Selain itu, 73 adalah nomor favorit Sheldon Cooper.

jam
sumber
5
Apakah Anda seorang programmer pascal atau sesuatu? ada apa dengan: = barang?
Mainguy
11
@Mainguy Ini sebenarnya sintaks ALGOL dan cukup sering digunakan dalam pseudo-code.
ApproachingDarknessFish
4
tetapi dalam multiplikasi perakitan ARM hingga 31 dapat dilakukan dalam satu instruksi
phuclv
Dalam TPOP (1999) orang dapat membaca tentang Java awal (hal.57): "... Masalahnya diselesaikan dengan mengganti hash dengan satu yang setara dengan yang telah kami tunjukkan (dengan pengali 37 ) ..."
miku
19

Neil Coffey menjelaskan mengapa 31 digunakan dalam Ironing out the bias .

Pada dasarnya menggunakan 31 memberi Anda distribusi probabilitas set-bit yang lebih rata untuk fungsi hash.

Jus
sumber
12

Dari JDK-4045622 , di mana Joshua Bloch menjelaskan alasan mengapa String.hashCode()implementasi (baru) tertentu dipilih

Tabel di bawah ini merangkum kinerja berbagai fungsi hash yang dijelaskan di atas, untuk tiga set data:

1) Semua kata dan frasa dengan entri dalam Merriam-Webster 2nd Int'l Unabridged Dictionary (311.141 string, rata-rata panjang 10 karakter) Merriam-Webster.

2) Semua string di / bin / , / usr / bin / , / usr / lib / , / usr / ucb / dan / usr / openwin / bin / * (66.304 string, panjang rata-rata 21 karakter).

3) Daftar URL yang dikumpulkan oleh perayap web yang berjalan selama beberapa jam semalam (28.372 string, panjang rata-rata 49 karakter).

Metrik kinerja yang ditunjukkan dalam tabel adalah "ukuran rantai rata-rata" di atas semua elemen dalam tabel hash (yaitu, nilai yang diharapkan dari jumlah kunci yang dibandingkan untuk mencari elemen).

                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439

Melihat tabel ini, jelas bahwa semua fungsi kecuali untuk fungsi Java saat ini dan dua versi fungsi Weinberger yang rusak menawarkan kinerja yang sangat baik dan hampir tidak dapat dibedakan. Saya sangat menduga bahwa kinerja ini pada dasarnya adalah "ideal teoritis", yang adalah apa yang akan Anda dapatkan jika Anda menggunakan generator bilangan acak yang benar di tempat fungsi hash.

Saya akan mengesampingkan fungsi WAIS karena spesifikasinya berisi halaman angka acak, dan kinerjanya tidak lebih baik daripada fungsi yang jauh lebih sederhana. Salah satu dari enam fungsi yang tersisa tampak seperti pilihan yang sangat baik, tetapi kita harus memilih satu. Saya kira saya akan mengesampingkan varian Vo's dan fungsi Weinberger karena kompleksitas tambahan mereka, meskipun kecil. Dari empat sisanya, saya mungkin akan memilih P (31), karena ini adalah yang termurah untuk dihitung pada mesin RISC (karena 31 adalah perbedaan dua kekuatan dua). P (33) juga murah untuk dihitung, tetapi kinerjanya sedikit lebih buruk, dan 33 adalah komposit, yang membuat saya sedikit gugup.

Josh

Mengalir
sumber
5

Bloch tidak cukup masuk ke ini, tetapi alasan saya selalu mendengar / percaya adalah bahwa ini adalah aljabar dasar. Hash bermuara pada operasi multiplikasi dan modulus, yang berarti bahwa Anda tidak pernah ingin menggunakan angka dengan faktor-faktor umum jika Anda dapat membantu. Dengan kata lain, bilangan yang relatif prima memberikan distribusi jawaban yang merata.

Angka-angka yang menggunakan hash biasanya:

  • modulus tipe data yang Anda masukkan (2 ^ 32 atau 2 ^ 64)
  • modulus jumlah bucket di hashtable Anda (bervariasi. Di java dulu prime, sekarang 2 ^ n)
  • kalikan atau geser dengan angka ajaib dalam fungsi pencampuran Anda
  • Nilai input

Anda benar-benar hanya bisa mengendalikan beberapa dari nilai-nilai ini, jadi sedikit perhatian ekstra harus dilakukan.

Jason
sumber
4

Dalam versi terbaru JDK, 31 masih digunakan. https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html#hashCode ()

Tujuan dari hash string adalah

  • unik (Mari lihat operator ^dalam dokumen perhitungan kode hash, ini membantu unik)
  • biaya murah untuk perhitungan

31 adalah nilai maks dapat dimasukkan ke dalam register 8 bit (= 1 byte), adalah bilangan prima terbesar yang dapat dimasukkan ke dalam register 1 byte, adalah angka ganjil.

Multiply 31 adalah << 5 lalu kurangi sendiri, oleh karena itu perlu sumber daya yang murah.

Apakah Nhu Vy
sumber
3

Saya tidak yakin, tapi saya kira mereka menguji beberapa sampel bilangan prima dan menemukan bahwa 31 memberikan distribusi terbaik atas beberapa sampel dari String yang mungkin.

Dave L.
sumber
1

Ini karena 31 memiliki properti yang bagus - perkaliannya dapat diganti dengan pergeseran bitwise yang lebih cepat daripada perkalian standar:

31 * i == (i << 5) - i
yoAlex5
sumber