Sử dụng ArrayList hoặc HashMap

Question

Xin chào, tôi có câu hỏi về việc có nên sử dụng số ArrayList hoặc HashMap hay không.

Tôi đang cố gắng xây dựng chương trình Paint. Mỗi đối tượng được vẽ sẽ được gán một đối tượng duy nhất ID.

Nếu tôi muốn có tốc độ truy xuất nhanh khi tôi nhấp vào một đối tượng, tôi có nên sử dụng arraylist hoặc hashmap không?

Trong băm chung có O (1) trong khi danh sách mảng có tốc độ truy xuất O (n).

Tuy nhiên, tôi nghĩ cho trường hợp của mình, vì khi tôi nhấp vào một đối tượng, tôi sẽ lấy ID, do đó chỉ mục của mảng và tôi có thể làm một cái gì đó như ArraylistObject.get (ithElement); , trong trường hợp này, đây cũng sẽ là một quá trình truy xuất O (1)?

bất kỳ đầu vào nào?

Cảm ơn!

Answer 1

Nếu đối tượng có ID có thể được ánh xạ từ 1 đến 1 thành mảng hơn là truy cập O (1), và trong thực tế sẽ nhanh hơn một chút so với tra cứu băm (bạn không có để tính toán băm).

Tuy nhiên, vấn đề sẽ xảy ra khi bạn xóa một đối tượng. Bạn sẽ bị bỏ lại với một lỗ hổng trong danh sách. Khi tạo các đối tượng mới, bạn có thể tiếp tục thêm vào danh sách và để nó dần dần bị phân mảnh hoặc cố gắng tìm một rãnh rảnh rỗi trong trường hợp bạn sẽ thực hiện tìm kiếm O (n) cho một khoảng trống.

Tóm lại - một hashmap có lẽ phù hợp hơn.

Answer 2

Về mặt tích cực, bạn có thể có thể ép thêm một chút hiệu suất bằng cách thực hiện ArrayLists vừa phải. Nhưng việc xóa đồ vật sẽ là một nỗi đau của hoàng gia - như Paolo và Anurag đã nói, bạn sẽ phải đặt một phần giữ chỗ trống (null?) Hoặc để sắp xếp lại một số đối tượng khác để lấp đầy khoảng trống. Điều này có thể dẫn đến lỗi hiệu suất và lỗi cũ đơn giản. Mặt khác,

HashMaps. Đơn giản để sử dụng, hiệu suất được đảm bảo (trừ khi bạn phân bổ id của bạn thực sự xấu).

Và truy xuất đối tượng theo id có thể không trở thành nút cổ chai của ứng dụng của bạn. Khi nói đi, tối ưu hóa sớm là gốc của tất cả các ác.

Answer 3

Nếu bạn có thể đảm bảo rằng các ID sẽ được trong một phạm vi số tương đối nhỏ, sau đó bạn nên sử dụng một mảng đơn giản (với kích thước preinitialized để ID tối đa), chứ không phải là một ArrayList. Điều đó đảm bảo rằng bạn không vô tình xóa các mục nhập và thay đổi mọi thứ khác để lấp đầy khoảng trống, với mọi thứ kết thúc ở một chỉ mục sai. Một mảng đơn giản cũng sẽ nhanh hơn một chút so với ArrayList.

Nếu bạn không thể bảo đảm như vậy, hãy sử dụng HashMap. Rất khó có thể nhận thấy sự khác biệt về tốc độ và sẽ dễ bảo trì hơn.