it-swarm-id.com

Algoritma hashing mana yang terbaik untuk keunikan dan kecepatan?

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

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

1444
Earlz

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

Saya menggunakan tiga set kunci yang berbeda:

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

Saya menguji:

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 :

Apakah tabrakan benar-benar terjadi?

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

Tabrakan FNV-1

  • creamwove bertabrakan dengan quists

FNV-1a tabrakan

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

Tabrakan Murmur2

  • 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 saat memetakan tabel secara linear:

Enter image description here

Atau sebagai Peta Hilbert ( XKCD selalu relevan ):

Enter image description here

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

[~ # ~] sdbm [~ # ~] :

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

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

Enter image description here

Bahkan, Murmur2 tampaknya memiliki keacakan yang lebih baik dengan Numbers daripada FNV-1a:

Enter image description here

Ketika saya melihat FNV-1a "number" map, I think Saya melihat pola vertikal yang halus. Dengan Murmur saya tidak melihat pola sama sekali. Bagaimana menurutmu?


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

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

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

Dan kemudian 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.

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_basis dan FNV_prime tergantung 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 corpus Kata Bahasa Inggris:

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 daripada FN-1, hanya 20% lebih buruk.

Saya pikir takeaway yang lebih penting adalah bahwa ada dua kelas algoritma dalam hal tabrakan:

  • tabrakan langka : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • tabrakan yang 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: Kehilangan

Pembaruan

Berbisik? Tentu, kenapa tidak


Pembaruan

@whatshisname bertanya-tanya bagaimana kinerja CRC32 , menambah angka pada tabel.

CRC32 adalah 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 de facto algoritma hash-table hashing saya. Tapi sekarang saya beralih ke Murmur2:

  • Lebih cepat
  • Lebih baik pengacakan dari semua kelas input

Dan saya benar-benar, sungguh berharap ada yang salah dengan algoritma SuperFastHash yang saya temukan ; terlalu buruk untuk 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 Murmur lebih cepat daripada 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.


Pembaruan

GUID dirancang untuk menjadi unik, bukan acak

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

Bahkan Versi 4 GUID algoritma tidak dijamin tidak dapat diprediksi, karena algoritma tidak menentukan kualitas generator angka acak. Artikel Wikipedia untuk GUID berisi penelitian utama yang menyarankan bahwa GUID 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 masukkan "GUID acak" dalam tanda kutip, karena ini adalah varian "acak" dari GUID. Deskripsi yang lebih akurat adalah Type 4 UUID. Tapi 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

2530
Ian Boyd

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 pembangunan fungsi hash dan tabel hash, Anda dapat menjamin, untuk dataset yang diberikan, bahwa tidak akan ada tabrakan.

61
Damien

Di Sini adalah daftar fungsi hash, tetapi versi singkatnya adalah:

Jika Anda hanya ingin memiliki fungsi hash yang baik, dan tidak bisa menunggu, djb2 adalah 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;
}
34
Dean Harding

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 kode 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.

29
Vipin Parakkat

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.

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 SSE 4.2s CRC instruksi, 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 ke kerentanan tabrakan dari 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 Ian Boyds answer . Ini menunjukkan bahwa CityHash memiliki beberapa masalah dalam kasus sudut.

Sumber yang digunakan untuk plot:

21
Sahib

Algoritma SHA (termasuk SHA-256) adalah dirancang 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)
18
yfeldblum

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

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

  1. Fungsi hash kriptografis idealnya harus tidak bisa dibedakan dari acak ;
  2. Tetapi dengan fungsi hash non-kriptografis, diinginkan bagi mereka untuk berinteraksi secara baik dengan kemungkinan input .

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

Kami benar-benar dapat menunjukkan ini dengan data dalam jawaban Ian Boyd dan sedikit matematika: the masalah Ulang Tahun . Rumus untuk jumlah yang diharapkan dari pasangan yang bertabrakan jika Anda memilih n bilangan bulat secara acak dari set [1, d] apakah 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 nomor 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 dengan nol tabrakan!

Jadi yang kita lihat di sini adalah bahwa hash yang diuji Ian berinteraksi menguntungkan dengan dataset angka berurutan — yaitu, mereka menyebarkan input yang sangat berbeda lebih luas dari fungsi hash kriptografi yang ideal. (Catatan: ini berarti 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 keduanya 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 pos . Ini adalah penggunaan di mana penghindaran tabrakan pada Kemungkinan input menang atas perilaku seperti 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 berisik , yang kemungkinan merupakan sejumlah kecil bit flips;
  • Hash Crypto dirancang untuk menangkap modifikasi yang dibuat oleh penyerang jahat , yang diberikan sumber daya komputasi terbatas tetapi secara cerdik banyak kepintaran.

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

15
sacundim

Gunakan SipHash . Ia memiliki banyak properti 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.

10
Demi

Itu tergantung pada data yang Anda hashing. Beberapa hashing bekerja lebih baik dengan data spesifik 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. :)

9
user712092

Java menggunakan ini algoritma multiply-and-add sederhana:

Kode hash untuk objek String dihitung sebagai

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

menggunakan aritmatika int, di mana s[i] adalah karakter i -th dari string, n adalah panjang dari 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.

6
biziclop

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;
}
4
user17754