Bộ sưu tập có chỉ mục và truy cập băm

Question

Tôi cần một lớp thu thập có cả hai: chỉ mục nhanh và truy cập băm. Bây giờ tôi có ArrayList. Đô thị này có acces chỉ số tốt, nhưng phương pháp contains của mình là không thực hiện. HashSet có thực hiện tốt contains nhưng không có acces được lập chỉ mục. Bộ sưu tập nào có cả hai? Có lẽ một cái gì đó từ Apache? Hoặc tôi có nên tạo lớp bộ sưu tập của riêng mình có cả hai: ArrayList cho các chỉ mục acces và HashSet cho kiểm tra contains?

Chỉ cần làm rõ: tôi cần cả hai get(int index) và contains(Object o)

Answer 1

Nếu bạn đang đi qua chỉ số từ đầu đến cuối, tôi nghĩ rằng điều này có thể đáp ứng nhu cầu của bạn: LinkedHashSet

Nếu bạn cần truy cập ngẫu nhiên thông qua chỉ mục, cũng như truy cập băm, nếu không ai khác có đề xuất tốt hơn, tôi đoán bạn có thể tạo bộ sưu tập của riêng bạn làm cả hai.

Answer 2

Nếu hiệu suất truy cập được lập chỉ mục không phải là một vấn đề các trận đấu gần nhất là LinkedHashSet mà API nói rằng nó là

bảng Hash và liên kết thực hiện danh sách các giao diện Set, với trật tự lặp dự đoán được.

ít nhất tôi không nghĩ rằng hiệu suất sẽ kém hơn hiệu suất của LinkedListPerformance. Nếu không, tôi không thể thấy không thay thế nhưng giải pháp ArrayList + HashTable của bạn

Answer 3

Làm như thế này; sử dụng sự kết hợp của Hash kỹ thuật cũng như danh sách để có được tốt nhất của cả hai thế giới :)

class DataStructure<Integer>{ 
    Hash<Integer,Integer> hash = new HashMap<Integer, Integer>(); 
    List<Integer> list = new ArrayList<Integer>(); 

    public void add(Integer i){ 
     hash.add(i,i); 
     list.add(i); 
    } 
    public Integer get(int index){ 
     return list.get(index); 
    } 
    ... 
} //used Integers to make it simpler 

Vì vậy, đối tượng; bạn giữ trong HashMap/HashSet cũng như ArrayList.

Vì vậy, nếu bạn muốn sử dụng

contains method : call hashed contains method. 

get an object with index: use array to return the value 

Chỉ cần chắc chắn rằng bạn có cả những bộ sưu tập đồng bộ. Và chăm sóc cập nhật/xóa trong cả hai cấu trúc dữ liệu.

Answer 4

Tôi không biết thời gian tra cứu chính xác, nhưng có thể bạn có thể sử dụng một số triển khai của Map interface. Bạn có thể lưu trữ các đối tượng của mình với map.put(objectHash, obj).

Sau đó, bạn có thể xác minh rằng bạn có một đối tượng nhất định với:

boolean contained = map.containsValue(obj); 

Và bạn có thể sử dụng băm để tra cứu một đối tượng trong bản đồ:

MyObject object = map.get(objectHash); 

Mặc dù, sự sụp đổ chỉ là rằng bạn sẽ cần phải biết băm của bạn về cuộc gọi tra cứu này có thể không có khả năng trong quá trình triển khai của bạn.