Hàm băm rất nhanh để băm chuỗi 8-16 byte

Question

Tôi cần hàm băm chuỗi rất nhanh, phù hợp với ứng dụng web được viết bằng PHP.

Sự cố mà tôi đang cố khắc phục là gán ID cho các quyền trong hệ thống kiểm soát truy cập. Tôi đang suy nghĩ về việc sử dụng các chuỗi băm để đại diện cho các ID quyền. Bằng cách này, tôi sẽ có thể kiểm tra các quyền theo cách như sau:

if ($Auth->isAllowed($user, "blog.comment")) { 
    // Do some operation 
} 
... 

if ($Auth->isAllowed($user, "profile.avatar.change")) { 
    // Do some other operation 
} 

Bảng DB sẽ ánh xạ quyền cấp phép cho vai trò của người dùng. Để kiểm tra xem người dùng có được phép thực hiện "profile.avatar.change" chuỗi tương ứng sẽ được băm và kiểm tra đối với bảng DB hay không.

Điều này rất tiện lợi và sẽ không cần phải lo lắng về việc duy trì ID cấp phép duy nhất giữa các mô-đun khác nhau. Nhưng chức năng băm phải rất hiệu quả.

Answer 1

Đầu tiên là tại sao anh ấy không sử dụng chức năng md5 đơn giản?.

Đang cố gắng để viết băm một mình

Một trong những most frequently referred function là một đơn giản băm Bernstein chức năng cũng-xăng là Times 33 with Addition. Nó được sử dụng trong php bởi zend to make hashes for keys of associative array. Trong php, nó có thể được thực hiện như sau:

function djb2($s){ 
    $word = str_split($s); 
    $length = count($word); 

    $hashAddress = 5381; 
    for ($counter = 0; $counter < $length; $counter++){ 
     $hashAddress = (($hashAddress << 5) + $hashAddress) + $word[$counter]; 
    } 
    return $hashAddress; 
} 
echo djb2("stackoverflow"); 

Vấn đề là khi nó được thực hiện theo cách này, nó là khá chậm. Các thử nghiệm cho thấy rằng nó là ~ 3 lần chậm hơn, so với md5. Vì vậy, chúng tôi phải tìm nhanh nhất internal implementation of a hash function.

Tìm sản phẩm tốt nhất băm nội

Chỉ cần đưa tất cả algos và đo lường thời gian để băm một triệu các chuỗi.

function testing($algo, $str) { 
    $start = microtime(true); 
    for($ax = 0; $ax < 1000000; $ax++){ 
     hash($algo, $str); 
    } 

    $end = microtime(true); 
    return ($end - $start); 
} 


$algos = hash_algos(); 
$times = []; 

foreach($algos as $algo){ 
    $times[$algo] = testing($algo, "stackoverflow"); 
} 

// sort by time ASC 
asort($times); 

foreach($times as $algo => $time){ 
    echo "$algo -> " . round($time, 2)."sec\n"; 
} 

kết quả của tôi là:

fnv1a32 -> 0.29sec 
fnv132 -> 0.3sec 
crc32b -> 0.3sec 
adler32 -> 0.3sec 
crc32 -> 0.31sec 
joaat -> 0.31sec 
fnv1a64 -> 0.31sec 
fnv164 -> 0.31sec 
md4 -> 0.46sec 
md5 -> 0.54sec 
... 
md2 -> 6.32sec 

Kết quả hơi thay đổi từ thực hiện để thực hiện - 8 algos đầu tiên được xáo trộn do tốc độ gần gũi của họ và sự phụ thuộc của nó vào tải máy chủ.

Điều gì sẽ được chọn?

Bạn có thể thực hiện bất kỳ chức năng nào thuộc top 8 như trên: $hash = hash('crc32', $string);. Trên thực tế, chức năng md5 được sử dụng rộng rãi chỉ chậm hơn 1,7 lần so với các nhà lãnh đạo.

Bonus

There are another functions like SuperFastHash, không được thực hiện trong php mã, nhưng họ đang 4x nhanh hơn crc32.

Answer 2

Thời gian xử lý của hàm băm có thể được coi là không đáng kể trong hầu hết các trường hợp. Nếu bạn cần một chút băm (8 ký tự), bạn có thể chỉ cần sử dụng chức năng crc32.

<?php 
$hash = hash('crc32', 'WhatDoYouWant'); 
?> 

Bạn cũng có thể kết hợp băm với uniqid để tạo băm ngẫu nhiên.

<?php 
$hash = hash('crc32', uniqid()); 
?> 

Answer 3

Sử dụng xxHash. Nó cũng được sử dụng bởi PrestoDB. Triển khai PHP trên GitHub