Package com.google.gson.internal
Class LinkedHashTreeMap<K,V>
java.lang.Object
java.util.AbstractMap<K,V>
com.google.gson.internal.LinkedHashTreeMap<K,V>
- All Implemented Interfaces:
Serializable
,Map<K,
V>
A map of comparable keys to values. Unlike
TreeMap
, this class uses
insertion order for iteration order. Comparison order is only used as an
optimization for efficient insertion and removal.
This implementation was derived from Android 4.1's TreeMap and LinkedHashMap classes.
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescription(package private) static final class
Builds AVL trees of a predetermined size by accepting nodes of increasing value.(package private) static class
Walks an AVL tree in iteration order.(package private) final class
(package private) final class
private class
(package private) static final class
Nested classes/interfaces inherited from class java.util.AbstractMap
AbstractMap.SimpleEntry<K extends Object,
V extends Object>, AbstractMap.SimpleImmutableEntry<K extends Object, V extends Object> -
Field Summary
FieldsModifier and TypeFieldDescription(package private) Comparator<? super K>
private LinkedHashTreeMap<K,
V>.EntrySet (package private) final LinkedHashTreeMap.Node<K,
V> private LinkedHashTreeMap<K,
V>.KeySet (package private) int
private static final Comparator<Comparable>
(package private) int
(package private) LinkedHashTreeMap.Node<K,
V>[] (package private) int
-
Constructor Summary
ConstructorsConstructorDescriptionCreate a natural order, empty tree map whose keys must be mutually comparable and non-null.LinkedHashTreeMap
(Comparator<? super K> comparator) Create a tree map ordered bycomparator
. -
Method Summary
Modifier and TypeMethodDescriptionvoid
clear()
boolean
containsKey
(Object key) private void
(package private) static <K,
V> LinkedHashTreeMap.Node<K, V>[] doubleCapacity
(LinkedHashTreeMap.Node<K, V>[] oldTable) Returns a new array containing the same nodes asoldTable
, but with twice as many trees, each of (approximately) half the previous size.entrySet()
private boolean
(package private) LinkedHashTreeMap.Node<K,
V> Returns the node at or adjacent to the given key, creating it if requested.(package private) LinkedHashTreeMap.Node<K,
V> findByEntry
(Map.Entry<?, ?> entry) Returns this map's entry that has the same key and value asentry
, or null if this map has no such entry.(package private) LinkedHashTreeMap.Node<K,
V> findByObject
(Object key) keySet()
private void
private void
rebalance
(LinkedHashTreeMap.Node<K, V> unbalanced, boolean insert) Rebalances the tree by making any AVL rotations necessary between the newly-unbalanced node and the tree's root.(package private) void
removeInternal
(LinkedHashTreeMap.Node<K, V> node, boolean unlink) Removesnode
from this tree, rearranging the tree's structure as necessary.(package private) LinkedHashTreeMap.Node<K,
V> private void
replaceInParent
(LinkedHashTreeMap.Node<K, V> node, LinkedHashTreeMap.Node<K, V> replacement) private void
rotateLeft
(LinkedHashTreeMap.Node<K, V> root) Rotates the subtree so that its root's right child is the new root.private void
rotateRight
(LinkedHashTreeMap.Node<K, V> root) Rotates the subtree so that its root's left child is the new root.private static int
secondaryHash
(int h) Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions.int
size()
private Object
If somebody is unlucky enough to have to serialize one of these, serialize it as a LinkedHashMap so that they won't need Gson on the other side to deserialize it.Methods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, isEmpty, putAll, toString, values
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, forEach, getOrDefault, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Field Details
-
NATURAL_ORDER
-
comparator
Comparator<? super K> comparator -
table
LinkedHashTreeMap.Node<K,V>[] table -
header
-
size
int size -
modCount
int modCount -
threshold
int threshold -
entrySet
-
keySet
-
-
Constructor Details
-
LinkedHashTreeMap
public LinkedHashTreeMap()Create a natural order, empty tree map whose keys must be mutually comparable and non-null. -
LinkedHashTreeMap
Create a tree map ordered bycomparator
. This map's keys may only be null ifcomparator
permits.- Parameters:
comparator
- the comparator to order elements with, ornull
to use the natural ordering.
-
-
Method Details
-
size
public int size() -
get
-
containsKey
- Specified by:
containsKey
in interfaceMap<K,
V> - Overrides:
containsKey
in classAbstractMap<K,
V>
-
put
-
clear
public void clear() -
remove
-
find
Returns the node at or adjacent to the given key, creating it if requested.- Throws:
ClassCastException
- ifkey
and the tree's keys aren't mutually comparable.
-
findByObject
-
findByEntry
Returns this map's entry that has the same key and value asentry
, or null if this map has no such entry.This method uses the comparator for key equality rather than
equals
. If this map's comparator isn't consistent with equals (such asString.CASE_INSENSITIVE_ORDER
), thenremove()
andcontains()
will violate the collections API. -
equal
-
secondaryHash
private static int secondaryHash(int h) Applies a supplemental hash function to a given hashCode, which defends against poor quality hash functions. This is critical because HashMap uses power-of-two length hash tables, that otherwise encounter collisions for hashCodes that do not differ in lower or upper bits. -
removeInternal
Removesnode
from this tree, rearranging the tree's structure as necessary.- Parameters:
unlink
- true to also unlink this node from the iteration linked list.
-
removeInternalByKey
-
replaceInParent
private void replaceInParent(LinkedHashTreeMap.Node<K, V> node, LinkedHashTreeMap.Node<K, V> replacement) -
rebalance
Rebalances the tree by making any AVL rotations necessary between the newly-unbalanced node and the tree's root.- Parameters:
insert
- true if the node was unbalanced by an insert; false if it was by a removal.
-
rotateLeft
Rotates the subtree so that its root's right child is the new root. -
rotateRight
Rotates the subtree so that its root's left child is the new root. -
entrySet
-
keySet
-
doubleCapacity
private void doubleCapacity() -
doubleCapacity
Returns a new array containing the same nodes asoldTable
, but with twice as many trees, each of (approximately) half the previous size. -
writeReplace
If somebody is unlucky enough to have to serialize one of these, serialize it as a LinkedHashMap so that they won't need Gson on the other side to deserialize it. Using serialization defeats our DoS defence, so most apps shouldn't use it.- Throws:
ObjectStreamException
-
readObject
- Throws:
IOException
-