LinkedHashMappublic class LinkedHashMap extends HashMap | LinkedHashMap is a variant of HashMap. Its entries are kept in a
doubly-linked list. The iteration order is, by default, the order in which
keys were inserted. Reinserting an already existing key doesn't change the
order. A key is existing if a call to {@code containsKey} would return true.
If the three argument constructor is used, and {@code order} is specified as
{@code true}, the iteration will be in the order that entries were accessed.
The access order gets affected by put(), get(), putAll() operations, but not
by operations on the collection views.
Null elements are allowed, and all the optional map operations are supported.
Note: The implementation of {@code LinkedHashMap} is not synchronized.
If one thread of several threads accessing an instance modifies the map
structurally, access to the map needs to be synchronized. For
insertion-ordered instances a structural modification is an operation that
removes or adds an entry. Access-ordered instances also are structurally
modified by put(), get() and putAll() since these methods change the order of
the entries. Changes in the value of an entry are not structural changes.
The Iterator that can be created by calling the {@code iterator} method
throws a {@code ConcurrentModificationException} if the map is structurally
changed while an iterator is used to iterate over the elements. Only the
{@code remove} method that is provided by the iterator allows for removal of
elements during iteration. It is not possible to guarantee that this
mechanism works in all cases of unsynchronized concurrent modification. It
should only be used for debugging purposes. |
| Fields Summary |
|---|
| private static final long | serialVersionUID | | private final boolean | accessOrder | | private transient LinkedHashMapEntry | head | | private transient LinkedHashMapEntry | tail |
| Constructors Summary |
|---|
public LinkedHashMap()Constructs a new empty {@code LinkedHashMap} instance.
super();
accessOrder = false;
head = null;
| public LinkedHashMap(int s)Constructs a new {@code LinkedHashMap} instance with the specified
capacity.
super(s);
accessOrder = false;
head = null;
| public LinkedHashMap(int s, float lf)Constructs a new {@code LinkedHashMap} instance with the specified
capacity and load factor.
super(s, lf);
accessOrder = false;
head = null;
tail = null;
| public LinkedHashMap(int s, float lf, boolean order)Constructs a new {@code LinkedHashMap} instance with the specified
capacity, load factor and a flag specifying the ordering behavior.
super(s, lf);
accessOrder = order;
head = null;
tail = null;
| public LinkedHashMap(Map m)Constructs a new {@code LinkedHashMap} instance containing the mappings
from the specified map. The order of the elements is preserved.
accessOrder = false;
head = null;
tail = null;
putAll(m);
|
| Methods Summary |
|---|
| public void | clear()Removes all elements from this map, leaving it empty.
internalClear();
| | Entry | createEntry(K key, int index, V value)
LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, value);
m.next = elementData[index];
elementData[index] = m;
linkEntry(m);
return m;
| | Entry | createHashedEntry(K key, int index, int hash)
LinkedHashMapEntry<K, V> m = new LinkedHashMapEntry<K, V>(key, hash);
m.next = elementData[index];
elementData[index] = m;
linkEntry(m);
return m;
| | public java.util.Set | entrySet()Returns a set containing all of the mappings in this map. Each mapping is
an instance of {@link Map.Entry}. As the set is backed by this map,
changes in one will be reflected in the other.
return new LinkedHashMapEntrySet<K, V>(this);
| | public V | get(java.lang.Object key)Returns the value of the mapping with the specified key.
LinkedHashMapEntry<K, V> m;
if (key == null) {
m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
} else {
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % elementData.length;
m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
}
if (m == null) {
return null;
}
if (accessOrder && tail != m) {
// BEGIN android-added
modCount++;
// END android-added
LinkedHashMapEntry<K, V> p = m.chainBackward;
LinkedHashMapEntry<K, V> n = m.chainForward;
n.chainBackward = p;
if (p != null) {
p.chainForward = n;
} else {
head = n;
}
m.chainForward = null;
m.chainBackward = tail;
tail.chainForward = m;
tail = m;
}
return m.value;
| | void | internalClear()
super.internalClear();
head = tail = null;
| | public java.util.Set | keySet()Returns a set of the keys contained in this map. The set is backed by
this map so changes to one are reflected by the other. The set does not
support adding.
if (keySet == null) {
keySet = new AbstractSet<K>() {
@Override
public boolean contains(Object object) {
return containsKey(object);
}
@Override
public int size() {
return LinkedHashMap.this.size();
}
@Override
public void clear() {
LinkedHashMap.this.clear();
}
@Override
public boolean remove(Object key) {
if (containsKey(key)) {
LinkedHashMap.this.remove(key);
return true;
}
return false;
}
@Override
public Iterator<K> iterator() {
return new LinkedHashIterator<K,K,V>(new MapEntry.Type<K,K,V>() {
public K get(MapEntry<K,V> entry) {
return entry.key;
}
}, LinkedHashMap.this);
}
};
}
return keySet;
| | void | linkEntry(java.util.LinkedHashMap$LinkedHashMapEntry m)
if (tail == m) {
return;
}
if (head == null) {
// Check if the map is empty
head = tail = m;
return;
}
// we need to link the new entry into either the head or tail
// of the chain depending on if the LinkedHashMap is accessOrder or not
LinkedHashMapEntry<K, V> p = m.chainBackward;
LinkedHashMapEntry<K, V> n = m.chainForward;
if (p == null) {
if (n != null) {
// The entry must be the head but not the tail
if (accessOrder) {
head = n;
n.chainBackward = null;
m.chainBackward = tail;
m.chainForward = null;
tail.chainForward = m;
tail = m;
}
} else {
// This is a new entry
m.chainBackward = tail;
m.chainForward = null;
tail.chainForward = m;
tail = m;
}
return;
}
if (n == null) {
// The entry must be the tail so we can't get here
return;
}
// The entry is neither the head nor tail
if (accessOrder) {
p.chainForward = n;
n.chainBackward = p;
m.chainForward = null;
m.chainBackward = tail;
tail.chainForward = m;
tail = m;
}
| | Entry[] | newElementArray(int s)
return new LinkedHashMapEntry[s];
| | public V | put(K key, V value)Maps the specified key to the specified value.
V result = putImpl(key,value);
if (removeEldestEntry(head)) {
remove(head.key);
}
return result;
| | V | putImpl(K key, V value)
LinkedHashMapEntry<K, V> m;
if (elementCount == 0){
head = tail = null;
}
if (key == null) {
m = (LinkedHashMapEntry<K, V>)findNullKeyEntry();
if (m == null) {
modCount++;
// Check if we need to remove the oldest entry
// The check includes accessOrder since an accessOrder LinkedHashMap
// does not record
// the oldest member in 'head'.
if (++elementCount > threshold) {
rehash();
}
m = (LinkedHashMapEntry<K, V>) createHashedEntry(null, 0, 0);
} else {
linkEntry(m);
}
} else {
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % elementData.length;
m = (LinkedHashMapEntry<K, V>)findNonNullKeyEntry(key, index, hash);
if (m == null) {
modCount++;
if (++elementCount > threshold) {
rehash();
index = (hash & 0x7FFFFFFF) % elementData.length;
}
m = (LinkedHashMapEntry<K, V>) createHashedEntry(key, index, hash);
} else {
linkEntry(m);
}
}
V result = m.value;
m.value = value;
return result;
| | public V | remove(java.lang.Object key)Removes the mapping with the specified key from this map.
LinkedHashMapEntry<K, V> m = (LinkedHashMapEntry<K, V>) removeEntry(key);
if (m == null) {
return null;
}
LinkedHashMapEntry<K, V> p = m.chainBackward;
LinkedHashMapEntry<K, V> n = m.chainForward;
if (p != null) {
p.chainForward = n;
} else {
head = n;
}
if (n != null) {
n.chainBackward = p;
} else {
tail = p;
}
return m.value;
| | protected boolean | removeEldestEntry(java.util.Map$Entry eldest)This method is queried from the put and putAll methods to check if the
eldest member of the map should be deleted before adding the new member.
If this map was created with accessOrder = true, then the result of
removeEldestEntry is assumed to be false.
return false;
| | public java.util.Collection | values()Returns a collection of the values contained in this map. The collection
is backed by this map so changes to one are reflected by the other. The
collection supports remove, removeAll, retainAll and clear operations,
and it does not support add or addAll operations.
This method returns a collection which is the subclass of
AbstractCollection. The iterator method of this subclass returns a
"wrapper object" over the iterator of map's entrySet(). The size method
wraps the map's size method and the contains method wraps the map's
containsValue method.
The collection is created when this method is called for the first time
and returned in response to all subsequent calls. This method may return
different collections when multiple concurrent calls occur, since no
synchronization is performed.
if (valuesCollection == null) {
valuesCollection = new AbstractCollection<V>() {
@Override
public boolean contains(Object object) {
return containsValue(object);
}
@Override
public int size() {
return LinkedHashMap.this.size();
}
@Override
public void clear() {
LinkedHashMap.this.clear();
}
@Override
public Iterator<V> iterator() {
return new LinkedHashIterator<V,K,V>(new MapEntry.Type<V,K,V>() {
public V get(MapEntry<K,V> entry) {
return entry.value;
}
}, LinkedHashMap.this);
}
};
}
return valuesCollection;
|
|
