Các phương pháp hay nhất về nội dung nên là chìa khóa trong cấu trúc có thể bắt buộc là

Question

Cấu trúc tìm kiếm tốt nhất là HashTable. Nó cung cấp truy cập liên tục trên mức trung bình (tuyến tính tệ nhất).
Điều này phụ thuộc vào hàm băm. Được.
Câu hỏi của tôi là như sau. Giả sử triển khai tốt một số điện thoại HashTable, ví dụ: HashMap là có một thực hành tốt nhất liên quan đến các phím được thông qua trong bản đồ? Tôi có nghĩa là nó được khuyến khích rằng chìa khóa phải là một đối tượng bất biến nhưng tôi đã tự hỏi nếu có những khuyến nghị khác.
Ví dụ về kích thước của khóa? Ví dụ trong một hashmap tốt (theo cách mô tả ở trên) nếu chúng ta sử dụng String làm khóa, sẽ không "nút cổ chai" được trong so sánh chuỗi cho equals (cố gắng tìm chìa khóa)? Vì vậy, các phím nên được giữ nhỏ? Hoặc có những đối tượng không nên được sử dụng làm khóa? Ví dụ. a URL? Trong những trường hợp như thế nào bạn có thể chọn những gì để sử dụng như một chìa khóa?

Answer 1

Bạn nên sử dụng bất kỳ khóa nào bạn muốn sử dụng để tra cứu mọi thứ trong cấu trúc dữ liệu, thường là ràng buộc theo miền cụ thể. Với điều đó đã nói, hãy nhớ rằng cả hai hashCode() và equals() sẽ được sử dụng để tìm khóa trong bảng.

hashCode() được sử dụng để tìm vị trí khóa, trong khi equals() được sử dụng để xác định xem khóa bạn đang tìm kiếm có thực sự là chìa khóa mà chúng tôi vừa tìm thấy không bằng cách sử dụng hashCode(). Ví dụ, xem xét hai khóa a và b có cùng mã băm trong bảng sử dụng separate chaining. Sau đó, một tìm kiếm cho a sẽ yêu cầu kiểm tra nếu a.equals(key) cho khả năng cả hai a và b trong bảng khi chúng tôi tìm thấy những chỉ số của danh sách có chứa a và b từ hashCode().

Answer 2

Chìa khóa thực hiện tốt nhất cho một HashMap có lẽ là một Integer, nơi hashCode() và equals() được thực hiện như:

public int hashCode() { 
    return value; 
} 

public boolean equals(Object obj) { 
    if (obj instanceof Integer) { 
     return value == ((Integer)obj).intValue(); 
    } 
    return false; 
} 

Nói rằng, mục đích của một HashMap là để ánh xạ một số đối tượng (giá trị) đối với một số người khác (Chìa khóa). Thực tế là hàm băm được sử dụng để giải quyết các đối tượng (giá trị) là cung cấp truy cập nhanh, không đổi.

khuyên rằng khóa phải là đối tượng không thay đổi nhưng tôi đã tự hỏi liệu có đề xuất nào khác không.

Đề xuất là để Ánh xạ đối tượng đến những gì bạn cần: đừng nghĩ điều gì sẽ nhanh hơn; nhưng hãy nghĩ điều gì là tốt nhất cho logic nghiệp vụ của bạn để giải quyết các đối tượng cần truy xuất.

Yêu cầu quan trọng là đối tượng khóa phải là bất biến, bởi vì nếu bạn thay đổi đối tượng khóa sau khi lưu trữ trong bản đồ thì không thể truy xuất giá trị được liên kết sau này.

Từ khóa trong HashMap là Map. Đối tượng của bạn chỉ cần bản đồ. Nếu bạn hy sinh nhiệm vụ ánh xạ tối ưu hóa khóa, bạn đang đánh bại mục đích của Bản đồ - mà không có khả năng đạt được bất kỳ tăng hiệu suất nào.

Tôi 100% đồng ý với hai ý kiến ​​đầu tiên trong câu hỏi của bạn:

những trở ngại chính là nó có được những điều mà bạn muốn dựa vào đó tra cứu trên;)
- Oli Charlesworth

Quy tắc chung là sử dụng làm khóa bất cứ điều gì bạn cần tìm kiếm.
- Louis Wasserman

Ghi hai quy tắc để tối ưu hóa:

1. Đừng.
2. (chỉ dành cho chuyên gia) chưa.

Quy tắc thứ ba là: cấu hình trước để tối ưu hóa.

Answer 3

Tôi đã tìm hiểu cách triển khai. Tôi đã có một giả định rằng hiệu quả của phương pháp hashCode() sẽ là yếu tố quan trọng.

Khi tôi xem xét HashMap() và triển khai Hashtable(), tôi nhận thấy rằng việc triển khai khá giống nhau (với một ngoại lệ). Cả hai đều đang sử dụng và lưu trữ mã băm nội bộ cho tất cả các mục nhập, vì vậy đó là điểm tốt mà hashCode() không ảnh hưởng nhiều đến hiệu suất.

Cả hai đều có một số nhóm, nơi lưu trữ các giá trị. Đó là sự cân bằng quan trọng giữa số lượng nhóm (giả sử n) và số lượng khóa trung bình trong một nhóm (nói k). Thùng được tìm thấy trong thời gian O (1), nội dung của xô được lặp lại theo kích thước O (k), nhưng chúng ta càng có nhiều thùng, bộ nhớ càng được cấp phát. Ngoài ra, nếu nhiều nhóm trống, điều đó có nghĩa là phương thức hashCode() cho lớp khóa không đủ mã băm.

Thuật toán các công trình như thế này:

Take the `hashCode()` of the Key (and make a slight bijective transformation on it) 
Find the appropriate bucket 
Loop through the content of the bucket (which is some kind of LinkedList) 
Make the comparison of the keys as follows: 
1. Compare the hashcodes 
    (it is calculated in the first step, and stored for the entry) 
2. Examine if key `==` the stored key (still no call) 
    (this step is missing from Hashtable) 
3. Compare the keys by `key.equals(storedKey)` 

Để tóm tắt:

• hashCode() được gọi một lần cho mỗi cuộc gọi (đây là điều bắt buộc, bạn không thể làm mà không có nó)
• bằng() được gọi nếu hashCode không được phát tán tốt và hai khóa xảy ra có cùng một mã băm

Thuật toán tương tự là cho get() và put() (vì trong trường hợp put() bạn có thể đặt giá trị cho khóa hiện tại). Vì vậy, điều quan trọng nhất là cách phương pháp hashCode() được triển khai. Đó là phương pháp thường được gọi nhất.

Hai chiến lược là: làm cho nó nhanh và làm cho nó có hiệu quả (phân bố tốt). Các nhà phát triển JDK đã nỗ lực để làm cho nó cả hai, nhưng nó không phải luôn luôn có thể có cả hai.

• Numeric loại là tốt
• Object (và các lớp học không overriden) là tốt (hashCode() có nguồn gốc), ngoại trừ việc bạn không thể chỉ định một riêng equals()
• String là không tốt, duyệt qua ký tự, nhưng lưu trữ sau đó (xem bình luận của tôi dưới đây)
• Bất kỳ lớp nào có hashCode được đồng bộ hóa() không tốt
• Bất kỳ lớp nào có quyền khẩu phần là không tốt
• Lớp học có bộ nhớ cache hashcode là một chút tốt hơn (phụ thuộc vào cách sử dụng)

Nhận xét về String: Để làm cho nó nhanh, trong các phiên bản đầu tiên của JDK mã chuỗi băm tính toán chỉ được thực hiện cho 32 ký tự đầu tiên. Nhưng mã băm mà nó tạo ra không được phát tán tốt, vì vậy họ quyết định đưa tất cả các ký tự vào mã băm.

Answer 4

khuyên rằng khóa phải là đối tượng không thay đổi nhưng tôi đã tự hỏi liệu có đề xuất nào khác không.

Khóa của giá trị phải là final.

Hầu hết các trường của đối tượng được sử dụng làm khóa. Nếu những thay đổi lĩnh vực sau đó bản đồ không thể tìm thấy nó:

void foo(Employee e) { 
    map.put(e.getId(), e); 
    String newId = e.getId() + "new"; 
    e.setId(newId); 
    Employee e2 = e.get(newId); 
    // e != e2 ! 
} 

Vì vậy Employee không nên có một phương pháp setId() ở tất cả, nhưng đó là khó khăn bởi vì khi bạn đang viết Employee bạn không biết những gì nó sẽ được keyed bởi .