Từ điển <,> Kích thước, mã GetHashCode và số nguyên tố?

Question

Tôi đã đọc khá nhiều về chủ đề thú vị này (IMO). nhưng tôi không hoàn toàn hiểu được một điều:

điển kích thước được tăng công suất của nó (đôi đến số nguyên tố gần) cho một số nguyên tố (khi tái phân bổ): vì:

int index = hashCode % [Dictionary Capacity]; 

• Vì vậy, chúng tôi có thể thấy rằng số nguyên tố được sử dụng tại đây cho [Dictionary Capacity] vì số GreatestCommonFactor của chúng tôi là 1. và điều này giúp để tránh va chạm.

Ngoài

Tôi đã nhìn thấy nhiều mẫu thực hiện GetHashCode():

Đây là một mẫu từ Jon Skeet:

public override int GetHashCode() 
{ 
    unchecked 
    { 
     int hash = 17; 
     // Suitable nullity checks etc, of course :) 
     hash = hash * 23 + field1.GetHashCode(); 
     hash = hash * 23 + field2.GetHashCode(); 
     hash = hash * 23 + field3.GetHashCode(); 
     return hash; 
    } 
} 

Tôi không hiểu:

Questi trên

Có số nguyên tố được sử dụng cả trong: Dictionary capacity và trong thế hệ của getHashCode?

Bởi vì trong đoạn mã trên, có một cơ hội tốt mà giá trị trả về sẽ không là một số nguyên tố [hãy sửa lại cho tôi nếu tôi sai] vì

• nhân bằng cách 23
• bổ sung giá trị GetHashCode() cho mỗi trường.

Ví dụ: (11,17,173 là số nguyên tố)

 int hash = 17; 
     hash = hash * 23 + 11; //402 
     hash = hash * 23 + 17; //9263 
     hash = hash * 23 + 173 //213222 
     return hash; 

213222 không là số nguyên tố.

Cũng không có bất kỳ quy tắc toán học mà nhà nước:

(not a prime number) + (prime number) = (prime number)

cũng không

(not a prime number) * (prime number) = (prime number)

cũng không

(not a prime number) * (not a prime number) = (prime number)

Vì vậy, những gì tôi thiếu?

Answer 1

Không quan trọng kết quả của GetHashCode là (nó không phải là số nguyên tố), miễn là kết quả giống nhau cho hai đối tượng được coi là bằng nhau. Tuy nhiên, nó là đẹp (nhưng không bắt buộc) để có GetHashCode trả về một giá trị khác nhau cho hai đối tượng được coi là khác nhau (nhưng vẫn không nhất thiết là số nguyên tố).

Cho hai số a và b, khi bạn nhân chúng, bạn sẽ nhận được c = a * b. Thường có nhiều cặp khác nhau của a và b cho cùng một kết quả c. Ví dụ 6 * 2 = 12 và 4 * 3 = 12. Tuy nhiên, khi a là số số nguyên tố, có rất ít cặp mang lại kết quả tương tự. Điều này thuận tiện cho thuộc tính rằng mã băm phải là khác nhau cho các đối tượng khác nhau.

Trong từ điển cùng một nguyên tắc áp dụng: các đối tượng được đặt trong nhóm tùy thuộc vào hàm băm của chúng. Vì hầu hết các số nguyên không phân chia độc đáo với số nguyên tố, bạn sẽ có được sự lây lan tốt đẹp của các đối tượng trong các nhóm. Lý tưởng nhất là bạn chỉ muốn một mục trong mỗi nhóm để có hiệu suất từ ​​điển tối ưu.

---

Hơi off-topic: Cicada của (đó là một con côn trùng) use prime numbers để xác định sau bao nhiêu năm họ đi và giao phối một lần nữa. Vì chu kỳ giao phối này là số nguyên tố trong nhiều năm, cơ hội giao phối liên tục trùng với vòng đời của bất kỳ kẻ địch nào là mỏng.