it-swarm-vi.com

Thuật toán băm nào là tốt nhất cho tính độc đáo và tốc độ?

Thuật toán băm nào là tốt nhất cho tính độc đáo và tốc độ? Ví dụ (tốt) sử dụng bao gồm từ điển băm.

Tôi biết có những thứ như SHA-256 và như vậy, nhưng các thuật toán này được được thiết kế thành an toàn , điều này thường có nghĩa là chúng chậm hơn các thuật toán ít hơn unique. Tôi muốn một thuật toán băm được thiết kế nhanh, nhưng vẫn khá độc đáo để tránh va chạm.

1444
Earlz

Tôi đã thử nghiệm một số thuật toán khác nhau, đo tốc độ và số lần va chạm.

Tôi đã sử dụng ba bộ khóa khác nhau:

Đối với mỗi kho văn bản, số lần va chạm và thời gian băm trung bình được ghi lại.

Tôi đã thử nghiệm:

Các kết quả

Mỗi kết quả chứa thời gian băm trung bình và số lần va chạm

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

Ghi chú :

Do va chạm thực sự xảy ra?

Đúng. Tôi bắt đầu viết chương trình thử nghiệm của mình để xem liệu va chạm băm thực sự xảy ra - và không chỉ là một cấu trúc lý thuyết. Họ thực sự xảy ra:

Va chạm FNV-1

  • creamwove va chạm với quists

Va chạm FNV-1a

  • costarring va chạm với liquid
  • declinate va chạm với macallums
  • altarage va chạm với zinke
  • altarages va chạm với zinkes

Va chạm Murmur2

  • cataract va chạm với periti
  • roquette va chạm với skivie
  • shawl va chạm với stormbound
  • dowlases va chạm với tramontane
  • cricketings va chạm với twanger
  • longans va chạm với whigs

Va chạm DJB2

  • hetairas va chạm với mentioner
  • heliotropes va chạm với neurospora
  • depravement va chạm với serafins
  • stylist va chạm với subgenera
  • joyful va chạm với synaphea
  • redescribed va chạm với urites
  • dram va chạm với vivency

Va chạm DJB2a

  • haggadot va chạm với loathsomenesses
  • adorablenesses va chạm với rentability
  • playwright va chạm với snush
  • playwrighting va chạm với snushing
  • treponematoses va chạm với waterbeds

Va chạm CRC32

  • codding va chạm với gnu
  • exhibiters va chạm với schlager

Va chạm SuperFastHash

  • dahabiah va chạm với drapability
  • encharm va chạm với enclave
  • grahams va chạm với gramary
  • ... bắn 79 va chạm ...
  • night va chạm với vigil
  • nights va chạm với vigils
  • finks va chạm với vinic

Tính ngẫu nhiên

Biện pháp chủ quan khác là cách băm phân phối ngẫu nhiên. Ánh xạ HashTables kết quả cho thấy dữ liệu được phân phối đồng đều như thế nào. Tất cả các hàm băm hiển thị phân phối tốt khi ánh xạ bảng tuyến tính:

Enter image description here

Hoặc là một Bản đồ Hilbert ( XKCD luôn có liên quan ):

Enter image description here

Ngoại trừ khi băm chuỗi số ("1", "2", ..., "216553") (ví dụ: Mã Zip ), trong đó các mẫu bắt đầu xuất hiện trong hầu hết các thuật toán băm:

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

Enter image description here

DJB2a :

Enter image description here

FNV-1 :

Enter image description here

Tất cả ngoại trừ FNV-1a , trông vẫn khá ngẫu nhiên đối với tôi:

Enter image description here

Trên thực tế, Murmur2 dường như thậm chí còn có tính ngẫu nhiên tốt hơn với Numbers than FNV-1a:

Enter image description here

Khi tôi nhìn vào FNV-1a "số" bản đồ, tôi nghĩ Tôi thấy các mẫu dọc tinh tế. Với Murmur tôi không thấy mẫu nào cả. Bạn nghĩ gì ?


Phần phụ * trong bảng biểu thị mức độ ngẫu nhiên xấu như thế nào. Với FNV-1a là người giỏi nhất và DJB2x là tồi tệ nhất:

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

Ban đầu tôi đã viết chương trình này để quyết định xem tôi thậm chí có phải lo lắng không về va chạm: Tôi làm.

Và sau đó nó trở thành đảm bảo rằng các hàm băm là đủ ngẫu nhiên.

Thuật toán FNV-1a

Hàm băm FNV1 có các biến thể trả về giá trị băm 32, 64, 128, 256, 512 và 1024 bit.

thuật toán FNV-1a là:

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

Các hằng số FNV_offset_basisFNV_prime phụ thuộc vào kích thước băm trả về mà bạn muốn:

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

Xem trang FNV chính để biết chi tiết.

Tất cả kết quả của tôi là với biến thể 32 bit.

FNV-1 tốt hơn FNV-1a?

Số FNV-1a là xung quanh tốt hơn. Đã có nhiều va chạm với FNV-1a khi sử dụng kho từ tiếng Anh:

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

Bây giờ so sánh chữ thường và chữ hoa:

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

Trong trường hợp này FNV-1a không "400%" tệ hơn FN-1, chỉ kém hơn 20%.

Tôi nghĩ điều quan trọng hơn cả là có hai loại thuật toán khi va chạm:

  • va chạm hiếm : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • va chạm phổ biến : SuperFastHash, Loselose

Và sau đó là cách băm phân bổ đều:

  • phân phối nổi bật: Murmur2, FNV-1a, SuperFastHas
  • phân phối xuất sắc: FNV-1
  • phân phối tốt: SDBM, DJB2, DJB2a
  • phân phối khủng khiếp: Mất

Cập nhật

Thì thầm? Chắc chắn, tại sao không


Cập nhật

@whatshisname tự hỏi làm thế nào một CRC32 sẽ thực hiện, thêm số vào bảng.

CRC32 là khá tốt. Ít va chạm, nhưng chậm hơn và chi phí hoạt động của bảng tra cứu 1k.

Cắt tất cả nội dung sai về phân phối CRC - xấu của tôi


Cho đến hôm nay tôi sẽ sử dụng FNV-1a làm thuật toán băm bảng băm của tôi de facto. Nhưng bây giờ tôi đang chuyển sang Murmur2:

  • Nhanh hơn
  • Tốt hơn ngẫu nhiên hóa trong tất cả các lớp đầu vào

Và tôi thực sự, thực sự hy vọng có điều gì đó không ổn với thuật toán SuperFastHash tôi tìm thấy ; Thật tệ khi được phổ biến như nó là.

Cập nhật: Từ trang chủ MurmurHash3 trên Google :

(1) - SuperFastHash có đặc tính va chạm rất kém, đã được ghi nhận ở nơi khác.

Vì vậy, tôi đoán đó không chỉ là tôi.

Cập nhật: Tôi nhận ra lý do tại sao Murmur nhanh hơn các loại khác. MurmurHash2 hoạt động trên bốn byte cùng một lúc. Hầu hết các thuật toán là byte by byte:

for each octet in Key
   AddTheOctetToTheHash

Điều này có nghĩa là khi chìa khóa càng dài thì Murmur càng có cơ hội tỏa sáng.


Cập nhật

GUID được thiết kế là duy nhất, không ngẫu nhiên

Một bài đăng kịp thời của Raymond Chen nhắc lại thực tế rằng "ngẫu nhiên" GUID không có nghĩa là được sử dụng cho tính ngẫu nhiên của chúng. Chúng hoặc một tập hợp con của chúng, không phù hợp làm khóa băm:

Ngay cả phiên bản 4 GUID cũng không được đảm bảo là không thể đoán trước được, vì thuật toán không chỉ định chất lượng của trình tạo số ngẫu nhiên. Bài viết Wikipedia cho GUID chứa nghiên cứu chính cho thấy rằng GUID tương lai và trước đó có thể được dự đoán dựa trên kiến ​​thức về trạng thái trình tạo số ngẫu nhiên, vì trình tạo không mạnh về mặt mật mã.

Randomess không giống như tránh va chạm; đó là lý do tại sao sẽ là một sai lầm khi cố gắng phát minh ra thuật toán "băm" của riêng bạn bằng cách sử dụng một số tập hợp con của hướng dẫn "ngẫu nhiên":

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

Lưu ý : Một lần nữa, tôi đặt "GUID ngẫu nhiên" trong dấu ngoặc kép, vì đó là biến thể "ngẫu nhiên" của GUID. Một mô tả chính xác hơn sẽ là Type 4 UUID. Nhưng không ai biết loại 4, hay loại 1, 3 và 5 là gì. Vì vậy, thật dễ dàng hơn để gọi chúng là GUID "ngẫu nhiên".

Tất cả các từ tiếng Anh gương

2530
Ian Boyd

Nếu bạn muốn tạo bản đồ băm từ một từ điển không thay đổi, bạn có thể muốn xem xét băm hoàn hảo https://en.wikipedia.org/wiki/Perinf_hash_feft - trong quá trình xây dựng hàm băm và bảng băm, bạn có thể đảm bảo, đối với một tập dữ liệu nhất định, sẽ không có xung đột.

61
Damien

Ở đây là danh sách các hàm băm, nhưng phiên bản ngắn là:

Nếu bạn chỉ muốn có một hàm băm tốt và không thể chờ, djb2 là một trong những hàm băm chuỗi tốt nhất mà tôi biết. Nó có sự phân phối và tốc độ tuyệt vời trên nhiều bộ khóa và kích cỡ bảng khác nhau

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 của Google là thuật toán bạn đang tìm kiếm. Nó không tốt cho mật mã nhưng tốt cho việc tạo các giá trị băm độc đáo.

Đọc blog để biết thêm chi tiết và mã có sẵn tại đây .

CityHash được viết bằng C++. Ngoài ra còn có một cổng C đơn giản .

Hỗ trợ khoảng 32 bit :

Tất cả các chức năng CityHash được điều chỉnh cho bộ xử lý 64 bit. Điều đó nói rằng, họ sẽ chạy (ngoại trừ những cái mới sử dụng SSE4.2) trong mã 32 bit. Họ sẽ không rất nhanh mặc dù. Bạn có thể muốn sử dụng Murmur hoặc một cái gì đó khác trong mã 32 bit.

29
Vipin Parakkat

Tôi đã lên kế hoạch so sánh tốc độ ngắn của các thuật toán băm khác nhau khi băm tập tin.

Các lô riêng lẻ chỉ khác nhau một chút trong phương thức đọc và có thể bỏ qua ở đây, vì tất cả các tệp được lưu trữ trong một tmpfs. Do đó, điểm chuẩn không bị ràng buộc IO nếu bạn đang tự hỏi.

Các thuật toán bao gồm: SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}.

Kết luận:

  • Các hàm băm không mã hóa như Murmur3, Cityhash và Spooky khá gần nhau. Mọi người nên lưu ý rằng Cityhash có thể nhanh hơn trên CPU với lệnh SSE 4.2s CRC, mà CPU của tôi không có. SpookyHash trong trường hợp của tôi luôn là một bit nhỏ trước CityHash.
  • MD5 dường như là một sự đánh đổi tốt khi sử dụng các hàm băm mật mã, mặc dù SHA256 có thể an toàn hơn đối với lỗ hổng va chạm của MD5 và SHA1.
  • Độ phức tạp của tất cả các thuật toán là tuyến tính - điều này thực sự không đáng ngạc nhiên vì chúng hoạt động theo khối. (Tôi muốn xem liệu phương thức đọc có tạo ra sự khác biệt hay không, vì vậy bạn chỉ có thể so sánh các giá trị ngoài cùng bên phải).
  • SHA256 chậm hơn SHA512.
  • Tôi đã không điều tra tính ngẫu nhiên của các hàm băm. Nhưng ở đây là một so sánh tốt về các hàm băm bị thiếu trong câu trả lời của Ian Boyds . Điều này chỉ ra rằng CityHash có một số vấn đề trong các trường hợp góc.

Nguồn được sử dụng cho các ô:

21
Sahib

Các thuật toán SHA (bao gồm SHA-256) là được thiết kế thành nhanh.

Trong thực tế, tốc độ của họ đôi khi có thể là một vấn đề. Cụ thể, một kỹ thuật phổ biến để lưu trữ mã thông báo có nguồn gốc mật khẩu là chạy thuật toán băm nhanh tiêu chuẩn 10.000 lần (lưu trữ hàm băm của hàm băm của hàm băm của ... mật khẩu).

#!/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

Đầu ra:

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

Tôi biết có những thứ như SHA-256 và như vậy, nhưng các thuật toán này được được thiết kế để được bảo mật , điều này thường có nghĩa là chúng chậm hơn các thuật toán ít hơn unique.

Giả định rằng các hàm băm mật mã độc đáo hơn là sai và trên thực tế, nó có thể được chứng minh là thường lạc hậu trong thực tế. Trong sự thật:

  1. Các hàm băm mật mã lý tưởng nên là không thể phân biệt với ngẫu nhiên ;
  2. Nhưng với các hàm băm không mã hóa, họ mong muốn tương tác thuận lợi với các đầu vào có khả năng .

Điều đó có nghĩa là hàm băm không mã hóa có thể có ít va chạm hơn so với hàm mã hóa cho tập dữ liệu "tốt" được thiết kế cho .

Chúng ta thực sự có thể chứng minh điều này bằng dữ liệu trong câu trả lời của Ian Boyd và một chút toán học: Bài toán sinh nhật . Công thức cho số lượng cặp va chạm dự kiến ​​nếu bạn chọn n số nguyên ngẫu nhiên từ tập [1, d] là cái này (lấy từ Wikipedia):

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

Cắm n = 216,553 và d = 2 ^ 32 chúng tôi nhận được về 5,5 va chạm dự kiến ​​. Các thử nghiệm của Ian chủ yếu cho thấy kết quả xung quanh vùng lân cận đó, nhưng với một ngoại lệ kịch tính: hầu hết các hàm có không va chạm trong các thử nghiệm số liên tiếp. Xác suất chọn ngẫu nhiên 216.553 số 32 bit và không bị va chạm là khoảng 0,43%. Và đó chỉ là một chức năng mà ở đây chúng ta có năm họ hàm băm riêng biệt với các va chạm bằng không!

Vì vậy, những gì chúng ta thấy ở đây là các giá trị băm mà Ian đã thử nghiệm đang tương tác thuận lợi với bộ dữ liệu số liên tiếp, tức là, chúng đang phân tán đầu vào khác nhau tối thiểu rộng rãi hơn một hàm băm mật mã lý tưởng. (Lưu ý bên lề: điều này có nghĩa là đánh giá đồ họa của Ian rằng FNV-1a và MurmurHash2 "trông ngẫu nhiên" đối với anh ta trong bộ dữ liệu số có thể được bác bỏ từ dữ liệu của chính anh ta. Không va chạm vào tập dữ liệu có kích thước đó, cho cả hai hàm băm, thật đáng kinh ngạc!)

Đây không phải là một bất ngờ vì đây là một hành vi mong muốn cho nhiều sử dụng hàm băm. Ví dụ, các khóa bảng băm thường rất giống nhau; Câu trả lời của Ian đề cập đến một vấn đề MSN từng gặp phải với bảng băm mã Zip . Đây là cách sử dụng trong trường hợp tránh va chạm trên có khả năng đầu vào chiến thắng hành vi giống như ngẫu nhiên.

Một so sánh mang tính hướng dẫn khác ở đây là sự tương phản trong các mục tiêu thiết kế giữa CRC và các hàm băm mật mã:

  • CRC được thiết kế để bắt lỗi do các kênh liên lạc ồn ào , có khả năng là một số lượng nhỏ bit lật;
  • Băm tiền điện tử được thiết kế để bắt sửa đổi được thực hiện bởi những kẻ tấn công độc hại , những người được phân bổ tài nguyên tính toán hạn chế nhưng thông minh nhiều tùy ý.

Vì vậy, đối với CRC, một lần nữa tốt để có ít va chạm hơn ngẫu nhiên trong các đầu vào khác nhau tối thiểu. Với băm tiền điện tử, đây là điều không nên!

15
sacundim

Sử dụng SipHash . Nó có nhiều thuộc tính mong muốn :

  • Nhanh. Việc triển khai được tối ưu hóa mất khoảng 1 chu kỳ cho mỗi byte.

  • Bảo mật. SipHash là một PRF mạnh (chức năng giả ngẫu nhiên). Điều này có nghĩa là nó không thể phân biệt được với một hàm ngẫu nhiên (trừ khi bạn biết khóa bí mật 128 bit). Vì thế:

    • Không cần phải lo lắng về việc thăm dò bảng băm của bạn trở thành thời gian tuyến tính do va chạm. Với SipHash, bạn biết rằng bạn sẽ có hiệu suất trung bình trong trường hợp trung bình, bất kể đầu vào.

    • Miễn nhiễm với các cuộc tấn công từ chối dịch vụ dựa trên hàm băm.

    • Bạn có thể sử dụng SipHash (đặc biệt là phiên bản có đầu ra 128 bit) làm MAC (Mã xác thực thư). Nếu bạn nhận được một tin nhắn và thẻ SipHash và thẻ này giống như khi chạy SipHash bằng khóa bí mật của bạn, thì bạn biết rằng bất cứ ai tạo ra hàm băm cũng đều sở hữu khóa bí mật của bạn và cả tin nhắn cũng không phải là tin nhắn băm đã được thay đổi kể từ đó.

10
Demi

Nó phụ thuộc vào dữ liệu bạn đang băm. Một số băm hoạt động tốt hơn với dữ liệu cụ thể như văn bản. Một số thuật toán băm được đặc tả được thiết kế để tốt cho dữ liệu cụ thể.

Paul Hsieh đã từng thực hiện băm nhanh . Ông liệt kê mã nguồn và giải thích. Nhưng nó đã bị đánh rồi. :)

9
user712092

Java sử dụng this thuật toán nhân và thêm đơn giản:

Mã băm cho một đối tượng String được tính là

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

sử dụng số học int, trong đó s[i] là ký tự thứ i của chuỗi, n là độ dài của chuỗi và ^ biểu thị lũy thừa. (Giá trị băm của chuỗi rỗng bằng không.)

Có lẽ có nhiều cái tốt hơn ngoài kia nhưng điều này khá phổ biến và dường như là một sự đánh đổi tốt giữa tốc độ và tính độc đáo.

6
biziclop

Trước hết, tại sao bạn cần phải thực hiện băm của riêng mình? Đối với hầu hết các tác vụ, bạn sẽ nhận được kết quả tốt với cấu trúc dữ liệu từ thư viện chuẩn, giả sử có sẵn một triển khai (trừ khi bạn chỉ làm việc này cho giáo dục của chính mình).

Theo như các thuật toán băm thực tế, yêu thích cá nhân của tôi là FNV. 1

Đây là một ví dụ triển khai phiên bản 32 bit trong 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