Який алгоритм хешування найкращий для унікальності та швидкості?

Question

Ще

Джерело Non AMP-version Редагувати

Який алгоритм хешування найкращий для унікальності та швидкості?

Який алгоритм хешування найкращий для унікальності та швидкості? Прикладом (хорошого) використання є хеш-словники.

Я знаю, що існують такі алгоритми, як SHA-256 і подібні, але ці алгоритми розроблені для того, щоб бути безпечними, що зазвичай означає, що вони повільніші, ніж алгоритми, які є менш унікальними. Я хочу, щоб хеш-алгоритм був швидким, але залишався досить унікальним, щоб уникнути колізій.

Sazzad Hissain Khan

Edited question 22-го листопада 2019 в 8:11

Інженерія програмного забезпечення

algorithms performance security hashing unique-data

19-го лютого 2011 в 12:03

22 погляди

Dean Harding · Answer 1 · 2011-02-19T01:13:08+00:00

[Тут][1] - список хеш-функцій, але скорочена версія:

Якщо ви просто хочете мати хорошу хеш-функцію і не можете чекати, то djb2 - одна з кращих рядкових хеш-функцій, які я знаю. Вона має відмінний розподіл і швидкість на багатьох різних наборах ключів і розмірах таблиць


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

    while (c = *str++)
        hash = ((hash

yfeldblum · Answer 2 · 2011-02-19T00:21:30+00:00

Алгоритми SHA (включаючи SHA-256) розроблені для того, щоб бути швидкими.

Насправді, їх швидкість іноді може бути проблемою. Зокрема, поширеною технікою зберігання токену, отриманого за допомогою пароля, є запуск стандартного швидкого алгоритму хешування 10 000 разів (зберігання хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу хешу).

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

Вивести:

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

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

biziclop · Answer 3 · 2011-02-19T00:23:04+00:00

Java використовує цей простий алгоритм множення та додавання:

Хеш-код для об'єкту типу String обчислюється як хеш-код об'єкту String s[0]31^(n-1) + s131^(n-2) + ... + s[n-1]

з використанням арифметики типу int, де [i] - i-й символ рядка, n - довжина рядка, а ^ вказує на піднесення до степеня. (Хеш-значення порожнього рядка дорівнює нулю).

Напевно, існують набагато кращі варіанти, але цей досить поширений і, здається, є хорошим компромісом між швидкістю і унікальністю.