string.GetHashCode() tính độc đáo và va chạm

Question

Cho hai chuỗi khác nhau, luôn luôn là trường hợp s.GetHashCode() != s1.GetHashCode()?

Trường hợp số lượng số nguyên khác biệt nhỏ hơn số chuỗi riêng biệt?

Answer 1

số Cũng giống như một thí nghiệm tưởng tượng đơn giản: Có bao nhiêu chuỗi đang có (gợi ý: nhiều hơn 2 và do đó có bao nhiêu mã băm duy nhất có thể có được (gợi ý:. 2 See the problem?)

mã hash chỉ là yêu cầu để được bằng bất cứ khi nào Equals lợi nhuận mà cả hai đối tượng đều bình đẳng. hơn nữa, bất cứ khi nào hai mã băm là không bằng nhau, sau đó các đối tượng bản thân không thể bằng nhau. không có yêu cầu hơn nữa, nhưng họ nên được phân phối tốt bảng băm có thể hoạt động tốt. Vì vậy, về cơ bản đó là:

Lưu ý các thiếu sót của các biến thể ⇐ tương ứng. Nó không phải là một sự tương đương, chỉ là hai ý nghĩa.

Để trích dẫn documentation: chức năng

Một băm phải có các thuộc tính sau:

1. Nếu hai vật thể so sánh như bình đẳng, phương pháp GetHashCode cho từng đối tượng phải trả lại giá trị như nhau. Tuy nhiên, nếu hai đối tượng không so sánh như nhau, các phương thức GetHashCode cho hai đối tượng không phải trả về các giá trị khác nhau.

2. Phương thức GetHashCode cho đối tượng phải luôn trả lại mã băm miễn là không có sửa đổi đối tượng trạng thái xác định giá trị trả về của phương thức Equals của đối tượng. Lưu ý rằng điều này chỉ đúng đối với việc thực hiện hiện tại của một ứng dụng và rằng một mã băm khác có thể được trả về nếu ứng dụng được chạy lại.

3. Để có hiệu suất tốt nhất, hàm băm phải tạo phân phối ngẫu nhiên cho tất cả đầu vào.

Answer 2

Để thêm vào @ tuyên bố của Joey bạn yếu có thể không có hashcodes luôn là bất bình đẳng.

Có 2^32 mã băm có thể có nhưng chuỗi đầu vào vô hạn.

Va chạm băm được đảm bảo xảy ra với đủ (2^32 + 1) giá trị đầu vào.

Thực tế, các va chạm băm phổ biến hơn nhiều so với một trong những điều có thể nghĩ là do Birthday Problem. Khi tôi thực hiện toán học một thời gian trở lại cho một hệ thống sử dụng mã băm 64 bit (có giá trị băm là cách nhiều hơn giá trị băm 32 bit, không chỉ gấp đôi so với giá trị đầu vào), với 100 triệu giá trị đầu vào rất có thể là sẽ có ít nhất 1 va chạm băm. Tôi nghĩ xác suất là khoảng 1%.

Answer 3

Theo tôi biết Object.GetHashCode() không cung cấp hàm băm trên đối tượng (vì vậy tôi cho rằng xem xét của Joey không đúng trong trường hợp này), nó chỉ trả về chỉ mục duy nhất được gán cho đối tượng bằng CLR khi đối tượng được tạo và phát hành khi đối tượng là rác thu thập được.

Vì vậy, bạn không thể có một mã băm trùng lặp (trong cùng một AppDomain) trong một thời điểm cụ thể, nhưng bạn có thể có một douplicate qua thời gian (chỉ số tương tự có thể được chỉ định nhiều hơn một lần trong quá trình thực hiện ứng dụng).

Câu hỏi đặt ra cũng sẽ được thảo luận ở đây: Default implementation for Object.GetHashCode()