Cả hai danh sách hoặc mảng được băm và lập chỉ mục?

Question

Có lớp nào trong Java, có chứa một mảng các phần tử theo thứ tự và được tối ưu hóa để tìm kiếm nhanh không?

I.e. Tôi cần truy xuất các phần tử theo cả chỉ mục số (như trong Vector) và bằng hàm băm (như trong HashMap).

LinkedHashMap không phù hợp

Tôi nghĩ LinkedHashMap không phù hợp vì nó đảm bảo trật tự, nhưng không cho phép truy nhập nhanh bằng chỉ số (số vị trí). Theo mô tả, nó sẽ yêu cầu phải đi qua toàn bộ chuỗi để tìm một vị trí nhất định. Đây là những gì bất kỳ Collection có thể với iterator.

EDIT 2

Tức là cả tìm kiếm theo khóa và theo chỉ mục phải nhanh, không chỉ bằng khóa.

Answer 1

Bạn có thể sử dụng Map để truy xuất nhanh các phần tử theo băm. Theo định nghĩa, một Map là không có thứ tự và nói về các chỉ mục không có ý nghĩa nhiều. Sử dụng một LinkedHashMap có thể được sử dụng, vì nó đảm bảo rằng trật tự chèn được bảo tồn tại lặp thời gian, mặc dù truy cập vào một phần tử bằng cách chỉ số vẫn sẽ cần thêm một số chế biến, một cái gì đó như thế này:

map.entrySet().toArray()[index] // mind the casts, etc. 

Nếu thay đổi bản đồ của bạn thường xuyên, ở trên sẽ hoạt động tốt nếu bạn nhớ mảng và kiểm tra xem kích thước của bản đồ đã thay đổi chưa trước khi truy cập mục nhập theo chỉ mục, tạo một mảng mới chỉ khi một thay đổi về kích thước đã được phát hiện. Mặt khác, nếu bản đồ thay đổi thường xuyên, bạn cần phải tạo lại mảng tại mỗi lần truy cập, tạo cấu trúc dữ liệu hoạt động kém.

Answer 2

Bạn có thể thử LinkedHashSet, tôi nghĩ vậy.

Answer 3

sử dụng LinkedHashMap. Điều này sẽ cho phép bạn truy xuất các phần tử thông qua khóa. Và bạn cũng có thể lấy các phần tử trong cùng một trình tự như bạn đã lưu trong đó.

Answer 4

Tôi nghĩ rằng bạn đang tìm kiếm LinkedHashMap

Từ các tài liệu: bảng

Hash và liên kết thực hiện danh sách các giao diện bản đồ, với trật tự lặp dự đoán được. Triển khai này khác với HashMap ở chỗ nó duy trì một danh sách được liên kết kép đang chạy qua tất cả các mục nhập của nó. Danh sách liên kết này xác định thứ tự lặp lại, thường là thứ tự mà các phím được chèn vào bản đồ (thứ tự chèn). Lưu ý rằng thứ tự chèn không bị ảnh hưởng nếu khóa được chèn lại vào bản đồ. (Một khóa k được chèn lại vào bản đồ m nếu m.put (k, v) được gọi khi m.containsKey (k) trả về true ngay trước lời gọi.)