Làm thế nào để tính toán tỷ lệ cược của một vụ va chạm trong thuật toán băm?

Question

Giả sử tôi có thuật toán băm, và nó đẹp và mượt mà (Tỷ lệ cược của bất kỳ giá trị băm nào cũng giống như bất kỳ giá trị nào khác).

Bây giờ nói rằng tôi biết rằng tỷ lệ cược của việc chọn 2 băm và có va chạm là (Vì lợi ích của đối số) 50000: 1.

Bây giờ, tôi chọn 100 băm. Làm cách nào để tính toán tỷ lệ cược của một vụ va chạm trong tập hợp 100 giá trị đó, với tỷ lệ cược của một vụ va chạm trong một bộ 2?

Giải pháp chung cho điều này là gì, để tôi có thể đưa ra một số lần thử băm sau khi tỷ lệ cược giảm xuống dưới ngưỡng chấp nhận được? Ví dụ. Tôi có thể nói những thứ như "Một loạt 49999 giá trị băm sáng tạo có khả năng va chạm cao".

Answer 1

Đây là generalization of the Birthday problem.

Answer 2

Điều này được gọi là the Birthday problem. Để giải quyết vấn đề này, thay vào đó hãy suy nghĩ về tỷ lệ cược là có không va chạm (gọi là p _nc).

• p _nc (1) = 1
• p _nc (2) = 1 - p _c (2)
• p _nc (3) = p _nc (2) * p _nc (2) * p _nc (2)

Answer 3

Điều đó nghe rất giống với số Birthday Paradox đối với tôi.

Bạn có thể thay thế tập hợp các ngày sinh có thể (365) bằng các băm có thể (50000) và chạy các phép tính tương tự mà chúng xuất hiện ở đó.

Nếu bạn sửa đổi kịch bản python được trình bày trong bài viết cho các giá trị của bạn:

def bp(n, d): 
    v = 1.0 
    for i in range(n): 

     v = v * (1 - float(i)/d) 
    return 1 - v 

print bp(2, 50000) 

Bạn kết thúc với tỷ lệ cược của vụ va chạm trên hai con số của 0,00002. Khoảng 265 mẫu, bạn có khoảng 50% cơ hội bị va chạm.

Answer 4

Đầu tiên tính toán xác suất mà không có một vụ va chạm:

hashes_picked = 100 
single_collision_odds = 50000 

# safe_combinations is number of ways to pick hashes that don't overlap 
safe_combinations = factorial(single_collision_odds)/factorial(single_collision_odds - hashes_picked) 

# all_combinations is total number of ways to pick hashes 
all_combinations = single_collision_odds ** hashes_picked 

collision_chance = (all_combinations - safe_combinations)/all_combinations 

Answer 5

và JS

function calculate(n,k) 
{ 

    var result =1; 
    for (var i=0; i<k; i++){ 
     result=result*n/(n-i) 
    } 
    result=(1-1/result)*100; 
    return result; 
}