Bản đồ/ArrayList: cái nào nhanh hơn để tìm kiếm một phần tử

Question

Tôi có một bộ dữ liệu khổng lồ mà tôi đã lưu trữ vào bộ sưu tập và cần phải tìm bất kỳ bản sao nào trong đó hay không.

Kích thước dữ liệu có thể lớn hơn 1 triệu. Tôi biết tôi có thể lưu trữ nhiều phần tử hơn trong ArrayList comapre thành Map.

Câu hỏi của tôi là:

1. đang tìm kiếm chìa khóa trong một Map nhanh hơn so với tìm kiếm trong sắp xếp ArrayList?
2. đang tìm kiếm Khóa ở HashMap nhanh hơn TreeMap?
3. Chỉ về mặt không gian cần thiết để lưu trữ các yếu tố n, sẽ hiệu quả hơn giữa việc thực hiện TreeMap và HashMap?

Answer 1

1) Có. Tìm kiếm trung bình ArrayList là O (n). Hiệu suất tra cứu chính trong Bản đồ phụ thuộc vào việc triển khai cụ thể. Bạn có thể viết thực hiện Map là O (n) hoặc tệ hơn nếu bạn thực sự muốn, nhưng tất cả các triển khai trong thư viện chuẩn đều nhanh hơn O (n).

2) Có. HashMap là O (1) trung bình cho các tra cứu khóa đơn giản. TreeMap là O (log (n)).

Class HashMap<K,V>

thực hiện này cung cấp hiệu suất không đổi theo thời gian cho các hoạt động cơ bản (get và put), giả định các hàm băm phân tán các yếu tố đúng trong xô.

Class TreeMap<K,V>

thực hiện này cung cấp đảm bảo log (n) Chi phí thời gian cho các containsKey, có được, đặt và gỡ bỏ các hoạt động. Các thuật toán là sự thích nghi của những thuật toán trong Cormen, Leiserson và Rivest's Introduction to Algorithms.

3) Các yêu cầu về không gian sẽ là O (n) trong cả hai trường hợp. Tôi muốn đoán số TreeMap cần nhiều không gian hơn, nhưng chỉ bằng một yếu tố không đổi.

Answer 2

1. Tùy thuộc vào loại Map bạn đang sử dụng.
2. Một HashMap có một tra cứu trung bình hằng số thời gian (O (1)), trong khi thời gian tra cứu trung bình một 's TreeMap được dựa trên độ sâu của cây (O (log (n))), do đó a HashMap nhanh hơn.
3. Sự khác biệt có thể là tranh luận. Cả hai cấu trúc dữ liệu yêu cầu một số chi phí không đổi liên tục trong không gian phức tạp theo thiết kế (cả hai thể hiện O (n) không gian phức tạp).