Algoritma hashing mana yang terbaik untuk keunikan dan kecepatan? Penggunaan contoh (baik) termasuk kamus hash.

Saya tahu ada hal-hal seperti SHA-256 dan sejenisnya , tetapi algoritma ini dirancang untuk aman , yang biasanya berarti mereka lebih lambat daripada algoritma yang kurang unik . Saya ingin algoritma hash dirancang untuk menjadi cepat, namun tetap cukup unik untuk menghindari tabrakan.

Saya menguji beberapa algoritma yang berbeda, mengukur kecepatan dan jumlah tabrakan.

Saya menggunakan tiga set kunci yang berbeda:

• Daftar 216.553 kata bahasa Inggris (dalam huruf kecil)
• Angka "1"ke "216553"(pikirkan kode ZIP, dan bagaimana hash yang buruk mencatat msn.com )
• 216.553 GUID "acak" (yaitu tipe 4 uuid )

Untuk setiap korpus, jumlah tabrakan dan rata-rata waktu yang dihabiskan dicatat.

Saya menguji:

• DJB2
• DJB2a (varian menggunakan xorbukan +)
• FNV-1 (32-bit)
• FNV-1a (32-bit)
• SDBM
• CRC32
• Murmur2 (32-bit)
• SuperFastHash

Hasil

Setiap hasil berisi waktu hash rata-rata, dan jumlah tabrakan

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

Catatan :

• The algoritma LoseLose (di mana hash = hash + karakter) benar-benar mengerikan . Semuanya bertabrakan dalam 1.375 ember yang sama
• SuperFastHash cepat, dengan hal-hal yang terlihat sangat tersebar; demi kebaikan saya tabrakan nomor . Saya berharap orang yang mengangkutnya mendapat kesalahan; itu sangat buruk
• CRC32 cukup bagus . Lebih lambat, dan tabel pencarian 1k

Apakah tabrakan benar-benar terjadi?

Iya. Saya mulai menulis program pengujian saya untuk melihat apakah tabrakan hash benar - benar terjadi - dan bukan hanya konstruksi teoretis. Mereka memang terjadi:

FNV-1 tabrakan

• creamwove bertabrakan dengan quists

FNV-1a tabrakan

• costarring bertabrakan dengan liquid
• declinate bertabrakan dengan macallums
• altarage bertabrakan dengan zinke
• altarages bertabrakan dengan zinkes

Murmur2 tabrakan

• cataract bertabrakan dengan periti
• roquette bertabrakan dengan skivie
• shawl bertabrakan dengan stormbound
• dowlases bertabrakan dengan tramontane
• cricketings bertabrakan dengan twanger
• longans bertabrakan dengan whigs

Tabrakan DJB2

• hetairas bertabrakan dengan mentioner
• heliotropes bertabrakan dengan neurospora
• depravement bertabrakan dengan serafins
• stylist bertabrakan dengan subgenera
• joyful bertabrakan dengan synaphea
• redescribed bertabrakan dengan urites
• dram bertabrakan dengan vivency

Tabrakan DJB2a

• haggadot bertabrakan dengan loathsomenesses
• adorablenesses bertabrakan dengan rentability
• playwright bertabrakan dengan snush
• playwrighting bertabrakan dengan snushing
• treponematoses bertabrakan dengan waterbeds

Tabrakan CRC32

• codding bertabrakan dengan gnu
• exhibiters bertabrakan dengan schlager

Tabrakan SuperFastHash

• dahabiah bertabrakan dengan drapability
• encharm bertabrakan dengan enclave
• grahams bertabrakan dengan gramary
• ... memotong 79 tabrakan ...
• night bertabrakan dengan vigil
• nights bertabrakan dengan vigils
• finks bertabrakan dengan vinic

Pengacakan

Ukuran subyektif lainnya adalah seberapa besar hash didistribusikan secara acak. Memetakan HashTables yang dihasilkan menunjukkan bagaimana data didistribusikan secara merata. Semua fungsi hash menunjukkan distribusi yang baik ketika memetakan tabel secara linear:

Atau sebagai Peta Hilbert ( XKCD selalu relevan ):

Kecuali ketika hashing string angka ( "1",, "2"..., "216553") (misalnya, kode pos ), di mana pola mulai muncul di sebagian besar algoritma hashing:

SDBM :

DJB2a :

FNV-1 :

Semua kecuali FNV-1a , yang masih terlihat sangat acak bagi saya:

Bahkan, Murmur2 tampaknya memiliki keacakan yang lebih baik Numbersdaripada FNV-1a:

Ketika saya melihat FNV-1apeta "angka", saya pikir saya melihat pola vertikal yang halus. Dengan Murmur saya tidak melihat pola sama sekali. Bagaimana menurut anda?

Ekstra *dalam tabel menunjukkan seberapa buruk keacakan itu. Dengan FNV-1amenjadi yang terbaik, dan DJB2xmenjadi yang terburuk:

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

Saya awalnya menulis program ini untuk memutuskan apakah saya bahkan harus khawatir tentang tabrakan: Saya lakukan.

Dan kemudian itu berubah menjadi memastikan bahwa fungsi hash cukup acak.

Algoritma FNV-1a

Hash FNV1 hadir dalam varian yang mengembalikan hash 32, 64, 128, 256, 512 dan 1024 bit.

The algoritma FNV-1a adalah:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Di mana konstanta FNV_offset_basisdan FNV_primebergantung pada ukuran hash pengembalian yang Anda inginkan:

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

Lihat halaman FNV utama untuk detailnya.

Semua hasil saya dengan varian 32-bit.

FNV-1 lebih baik dari FNV-1a?

Tidak. FNV-1a lebih baik. Ada lebih banyak tabrakan dengan FNV-1a saat menggunakan kata Inggris corpus:

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

Sekarang bandingkan huruf kecil dan besar:

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

Dalam hal ini FNV-1a tidak "400%" lebih buruk dari FN-1, hanya 20% lebih buruk.

Saya pikir takeaway yang lebih penting adalah bahwa ada dua kelas algoritma ketika datang ke tabrakan:

• tabrakan langka : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
• tabrakan umum : SuperFastHash, Loselose

Dan kemudian ada seberapa merata hash tersebut:

• distribusi luar biasa: Murmur2, FNV-1a, SuperFastHas
• distribusi yang sangat baik: FNV-1
• distribusi yang baik: SDBM, DJB2, DJB2a
• distribusi mengerikan: Loselose

Memperbarui

Berbisik? Tentu, mengapa tidak

Memperbarui

@whatshisname bertanya-tanya bagaimana kinerja CRC32 , menambahkan nomor ke tabel.

CRC32 cukup bagus . Beberapa tabrakan, tetapi lebih lambat, dan overhead tabel pencarian 1k.

Gunting semua hal yang salah tentang distribusi CRC - salah saya

Sampai hari ini saya akan menggunakan FNV-1a sebagai algoritma hash-table hash de facto saya . Tapi sekarang saya beralih ke Murmur2:

• Lebih cepat
• Pengacakan yang lebih baik dari semua kelas input

Dan saya benar- benar berharap ada yang salah dengan SuperFastHashalgoritma yang saya temukan ; Sayang sekali menjadi sepopuler itu.

Pembaruan: Dari beranda MurmurHash3 di Google :

(1) - SuperFastHash memiliki sifat tabrakan yang sangat buruk, yang telah didokumentasikan di tempat lain.

Jadi saya kira itu bukan hanya saya.

Pembaruan: Saya menyadari mengapa Murmurlebih cepat dari yang lain. MurmurHash2 beroperasi pada empat byte sekaligus. Sebagian besar algoritma adalah byte demi byte :

for each octet in Key
   AddTheOctetToTheHash

Ini berarti bahwa ketika kunci semakin lama Murmur mendapat kesempatan untuk bersinar.

Memperbarui

GUID dirancang untuk menjadi unik, bukan acak

Sebuah posting yang tepat waktu oleh Raymond Chen menegaskan fakta bahwa GUID "acak" tidak dimaksudkan untuk digunakan untuk keacakan mereka. Mereka, atau sebagian dari mereka, tidak cocok sebagai kunci hash:

Bahkan algoritma GUID Versi 4 tidak dijamin tidak dapat diprediksi, karena algoritma tersebut tidak menentukan kualitas generator angka acak. Artikel Wikipedia untuk GUID berisi penelitian utama yang menunjukkan bahwa GUID di masa depan dan sebelumnya dapat diprediksi berdasarkan pengetahuan tentang keadaan generator nomor acak, karena generator tersebut tidak kuat secara kriptografis.

Keacakan tidak sama dengan menghindari tabrakan; itulah sebabnya akan menjadi kesalahan untuk mencoba menemukan algoritma "hashing" Anda sendiri dengan mengambil beberapa bagian dari panduan "acak":

int HashKeyFromGuid(Guid type4uuid)
{
   //A "4" is put somewhere in the GUID.
   //I can't remember exactly where, but it doesn't matter for
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);
}

Catatan : Sekali lagi, saya memberi tanda "GUID acak" dalam tanda kutip, karena ini adalah varian "acak" dari GUID. Deskripsi yang lebih akurat adalah Type 4 UUID. Tetapi tidak ada yang tahu apa tipe 4, atau tipe 1, 3 dan 5. Jadi, lebih mudah untuk memanggil mereka GUID "acak".

Semua Kata Bahasa Inggris mencerminkan

• https://web.archive.org/web/20070221060514/http://www.sitopreferito.it/html/all_english_words.html
• https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8/view?usp=sharing

Jika Anda ingin membuat peta hash dari kamus yang tidak berubah, Anda mungkin ingin mempertimbangkan hashing sempurna https://en.wikipedia.org/wiki/Perfect_hash_function - selama konstruksi fungsi hash dan tabel hash, Anda dapat menjamin, untuk dataset yang diberikan, bahwa tidak akan ada tabrakan.

Berikut adalah daftar fungsi hash, tetapi versi singkatnya adalah:

Jika Anda hanya ingin memiliki fungsi hash yang baik, dan tidak bisa menunggu, djb2adalah salah satu fungsi hash string terbaik yang saya tahu. Ini memiliki distribusi dan kecepatan yang sangat baik pada berbagai set kunci dan ukuran tabel

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

CityHash oleh Google adalah algoritma yang Anda cari. Ini tidak baik untuk kriptografi tetapi bagus untuk menghasilkan hash yang unik.

Baca blog untuk lebih jelasnya dan kodenya tersedia di sini .

CityHash ditulis dalam C ++. Ada juga port C polos .

Tentang dukungan 32-bit:

Semua fungsi CityHash disetel untuk prosesor 64-bit. Yang mengatakan, mereka akan berjalan (kecuali yang baru yang menggunakan SSE4.2) dalam kode 32-bit. Mereka tidak akan terlalu cepat. Anda mungkin ingin menggunakan murmur atau sesuatu yang lain dalam kode 32-bit.

Saya telah merencanakan perbandingan kecepatan pendek dari berbagai algoritma hashing ketika hashing file.

Plot individual hanya sedikit berbeda dalam metode membaca dan dapat diabaikan di sini, karena semua file disimpan dalam tmpfs. Karena itu patokan itu tidak terikat IO jika Anda bertanya-tanya.

• Skala linear
• Skala logaritmik

Algoritma meliputi: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Kesimpulan:

• Fungsi hash non-kriptografis seperti Murmur3, Cityhash dan Spooky cukup dekat satu sama lain. Orang harus mencatat bahwa Cityhash mungkin lebih cepat pada CPU dengan CRCinstruksi SSE 4.2s , yang tidak dimiliki CPU saya. SpookyHash dalam kasus saya selalu sedikit sebelum CityHash.
• MD5 tampaknya merupakan tradeoff yang baik ketika menggunakan fungsi hash kriptografi, meskipun SHA256 mungkin lebih aman untuk kerentanan tabrakan MD5 dan SHA1.
• Kompleksitas semua algoritma bersifat linier - yang benar-benar tidak mengejutkan karena mereka bekerja secara searah. (Saya ingin melihat apakah metode membaca membuat perbedaan, jadi Anda bisa membandingkan nilai paling kanan).
• SHA256 lebih lambat dari SHA512.
• Saya tidak menyelidiki keacakan fungsi hash. Tapi di sini adalah perbandingan yang bagus dari fungsi hash yang hilang dalam jawaban Ian Boyds . Ini menunjukkan bahwa CityHash memiliki beberapa masalah dalam kasus sudut.

Sumber yang digunakan untuk plot:

• https://github.com/sahib/rmlint/tree/gh-pages/plots (maaf untuk kode jelek)

Algoritma SHA (termasuk SHA-256) dirancang untuk menjadi cepat .

Bahkan, kecepatan mereka terkadang bisa menjadi masalah. Secara khusus, teknik umum untuk menyimpan token yang diturunkan kata sandi adalah dengan menjalankan algoritma hash standar cepat 10.000 kali (menyimpan hash hash hash hash hash dari ... password).

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

Keluaran:

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

Saya tahu ada hal-hal seperti SHA-256 dan sejenisnya, tetapi algoritma ini dirancang untuk aman , yang biasanya berarti mereka lebih lambat daripada algoritma yang kurang unik .

Asumsi bahwa fungsi hash kriptografis lebih unik adalah salah, dan pada kenyataannya itu dapat ditunjukkan untuk sering mundur dalam praktik. Sebenarnya:

1. Fungsi hash kriptografi idealnya tidak dapat dibedakan dari acak ;
2. Tetapi dengan fungsi hash non-kriptografis, diinginkan bagi mereka untuk berinteraksi secara menguntungkan dengan input yang mungkin .

Yang berarti bahwa fungsi hash non-kriptografi mungkin memiliki lebih sedikit tabrakan daripada fungsi kriptografis untuk set data "baik" —set data yang dirancang untuknya.

Kami benar-benar dapat menunjukkan ini dengan data dalam jawaban Ian Boyd dan sedikit matematika: masalah Ulang Tahun . Rumus untuk jumlah pasangan bertabrakan yang diharapkan jika Anda memilih nbilangan bulat secara acak dari himpunan [1, d]adalah ini (diambil dari Wikipedia):

n - d + d * ((d - 1) / d)^n

Memasukkan n= 216.553 dan d= 2 ^ 32 kita mendapatkan sekitar 5,5 tabrakan yang diharapkan . Tes Ian sebagian besar menunjukkan hasil di sekitar lingkungan itu, tetapi dengan satu pengecualian dramatis: sebagian besar fungsi mendapat nol tabrakan dalam tes angka berturut-turut. Probabilitas memilih 216.553 angka 32-bit secara acak dan mendapatkan nol tabrakan adalah sekitar 0,43%. Dan itu hanya untuk satu fungsi — di sini kita memiliki lima keluarga fungsi hash yang berbeda tanpa tabrakan!

Jadi apa yang kita lihat di sini adalah bahwa hash yang diuji Ian berinteraksi baik dengan dataset angka berurutan — yaitu, mereka menyebar input yang berbeda minimal lebih luas daripada fungsi hash kriptografi ideal. (Catatan: ini berarti bahwa penilaian grafis Ian bahwa FNV-1a dan MurmurHash2 "terlihat acak" baginya dalam kumpulan data angka dapat disangkal dari datanya sendiri. Nol tabrakan pada kumpulan data ukuran itu, untuk kedua fungsi hash, sangat nonrandom!)

Ini bukan kejutan karena ini adalah perilaku yang diinginkan untuk banyak penggunaan fungsi hash. Sebagai contoh, kunci tabel hash seringkali sangat mirip; Jawaban Ian menyebutkan masalah yang pernah dialami MSN dengan tabel hash kode ZIP . Ini adalah penggunaan di mana penghindaran tabrakan pada input yang mungkin menang lebih dari perilaku acak.

Perbandingan instruktif lain di sini adalah kontras dalam tujuan desain antara CRC dan fungsi hash kriptografis:

• CRC dirancang untuk menangkap kesalahan yang dihasilkan dari saluran komunikasi yang berisik , yang kemungkinan merupakan sejumlah kecil kesalahan ;
• Hash Crypto dirancang untuk menangkap modifikasi yang dibuat oleh penyerang jahat , yang diberi sumber daya komputasi terbatas tetapi secara cerdik banyak kepintaran.

Jadi untuk CRC sekali lagi baik untuk memiliki lebih sedikit tabrakan daripada acak dalam input minimal yang berbeda. Dengan hash crypto, ini tidak-tidak!

Gunakan SipHash . Ini memiliki banyak sifat yang diinginkan:

• Cepat. Implementasi yang dioptimalkan memakan waktu sekitar 1 siklus per byte.

• Aman. SipHash adalah PRF yang kuat (fungsi pseudorandom). Ini berarti bahwa ia tidak dapat dibedakan dari fungsi acak (kecuali Anda tahu kunci rahasia 128-bit). Karenanya:

  • Tidak perlu khawatir tentang probe tabel hash Anda menjadi waktu linier karena tabrakan. Dengan SipHash, Anda tahu bahwa Anda akan mendapatkan kinerja kasus rata-rata, terlepas dari input.

  • Kekebalan terhadap serangan penolakan layanan berbasis hash.

  • Anda dapat menggunakan SipHash (terutama versi dengan output 128-bit) sebagai MAC (Message Authentication Code). Jika Anda menerima pesan dan tag SipHash, dan tag itu sama dengan yang dari menjalankan SipHash dengan kunci rahasia Anda, maka Anda tahu bahwa siapa pun yang membuat hash juga memiliki kunci rahasia Anda, dan bahwa baik pesan maupun hash telah diubah sejak itu.

Itu tergantung pada data yang Anda hashing. Beberapa hashing berfungsi lebih baik dengan data tertentu seperti teks. Beberapa algoritma hashing secara khusus dirancang agar baik untuk data tertentu.

Paul Hsieh pernah membuat hash cepat . Dia mencantumkan kode sumber dan penjelasannya. Tapi itu sudah dipukuli. :)

Java menggunakan ini sederhana multiply-dan-menambahkan algoritma:

Kode hash untuk objek String dihitung sebagai

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

menggunakan int aritmatika, di mana s[i]adalah saya karakter -th string, nadalah panjang string, dan ^menunjukkan eksponensial. (Nilai hash dari string kosong adalah nol.)

Mungkin ada yang jauh lebih baik di luar sana tetapi ini cukup luas dan tampaknya merupakan pertukaran yang baik antara kecepatan dan keunikan.

Pertama-tama, mengapa Anda perlu menerapkan hashing Anda sendiri? Untuk sebagian besar tugas, Anda harus mendapatkan hasil yang baik dengan struktur data dari perpustakaan standar, dengan asumsi ada implementasi yang tersedia (kecuali Anda hanya melakukan ini untuk pendidikan Anda sendiri).

Sejauh algoritma hashing aktual berjalan, favorit pribadi saya adalah FNV. 1

Berikut ini contoh implementasi versi 32-bit di C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}