LinkedHashMap LIFO hoặc FIFO?

Question

Được liên kếtHashMap LIFO hoặc FIFO trong tự nhiên? Nếu bản đồ của tôi có dạng ->

map.put(1,"one"); 
map.put(2,"two"); 

những gì sẽ là thứ tự nếu tôi đã được lặp đi lặp lại trên bản đồ bằng keyset ??

EDIT: Tôi nghĩ rằng tôi đã thực sự nhầm lẫn hai khái niệm khác nhau.cho tôi rephrase câu hỏi.Điều gì sẽ được thứ tự mà tôi gặp phải số lượng bằng cách sử dụng entryset? Cảm ơn bạn đã chỉ ra btw.i donot có ý định loại bỏ bất kỳ mục nhập.

Answer 1

Trong bản đồ băm được liên kết, các phần tử trong danh sách liên kết kép được thêm vào cuối cùng (rõ ràng: để giữ lại thứ tự lặp), nhưng có thể bị xóa khỏi bất kỳ phần nào trong danh sách khi các phần tử bị xóa khỏi bản đồ , không chính xác để gắn nhãn danh sách sao lưu (và theo phần mở rộng: bản đồ) là LIFO hoặc FIFO, không có khái niệm về thứ tự xóa trong bản đồ và do đó không có lệnh xóa nào có thể được giả định cho danh sách sao lưu trong băm được liên kết bản đồ.

Bản đồ băm được liên kết đảm bảo là lặp lại nội dung của nó (có thể là: các phím hoặc mục nhập) sẽ xảy ra theo cùng thứ tự các phần tử được chèn vào bản đồ; từ số documentation:

Triển khai này khác với HashMap ở chỗ nó duy trì danh sách được liên kết kép 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).

EDIT:

Về chỉnh sửa cuối cùng cho câu hỏi, một LinkedHashMapđảm bảo rằng thứ tự lần lặp của keySet() sẽ là thứ tự trong đó các yếu tố được chèn vào: 1, 2 ví dụ như trong câu hỏi. Điều này không liên quan gì đến FIFO/LIFO, những khái niệm này xử lý thứ tự mà các phần tử được loại bỏ khỏi một cấu trúc dữ liệu và chúng không liên quan đến thứ tự lặp sau khi chèn các phần tử.

Answer 2

LinkedHashMap để trích dẫn từ javadocs là "Bảng băm và danh sách liên kết triển khai giao diện Bản đồ, với thứ tự lặp lại có thể dự đoán". Vì vậy, keySet sẽ trả về các khóa dựa trên thứ tự để chèn, một cách tinh tế là FIFO.

Answer 3

Theo tài liệu Java, nếu bạn lặp lại bản đồ, keyset sẽ nằm trong thứ tự chèn. Vì vậy, khóa đầu tiên bạn nhận được là khóa đầu tiên được nhập, qua các khóa hiện có. Lưu ý, việc lắp lại cặp khóa-giá trị không thay đổi vị trí khóa ban đầu.

Answer 4

Khi lệnh truy cập không được sử dụng (trường hợp tiêu chuẩn), bạn có thể coi LHM là danh sách được liên kết với/truy cập nhanh O (1) theo khóa.

Trong khía cạnh đó, đó là FIFO khi thứ tự truy cập không được sử dụng (xem c-tors). Khi thứ tự truy cập được sử dụng, thứ tự chèn không quan trọng nếu có bất kỳ hoạt động nào get() khi chúng sắp xếp lại các mục nhập. Nhìn vào số protected boolean removeEldestEntry(Map.Entry<K,V> eldest) lớn nhất = FIFO.

Về cơ bản LHM là danh sách được liên kết kép tốt gồm Map.Entry<Key, Value> với chỉ mục băm trên các khóa. Bản thân tôi không bao giờ sử dụng HashMap vanilla như trong impl hiện tại của nó.nó có rất ít lợi ích hơn LHM - dấu chân bộ nhớ thấp hơn nhưng lặp lại kinh khủng. Java8 (hoặc 9) có lẽ cuối cùng có thể sửa HashMap, hy vọng Doug Lea sẽ đẩy impl của mình.