Module com.google.gson
Package com.google.gson.internal

Class LinkedHashTreeMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>
    public final class LinkedHashTreeMap<K,​V>
extends java.util.AbstractMap<K,​V>
implements java.io.Serializable
    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:
    Serialized Form

    • Constructor Detail

      • LinkedHashTreeMap

        public LinkedHashTreeMap()
        Create a natural order, empty tree map whose keys must be mutually comparable and non-null.

      • LinkedHashTreeMap

        public LinkedHashTreeMap​(java.util.Comparator<? super K> comparator)
        Create a tree map ordered by comparator. This map's keys may only be null if comparator permits.
        Parameters:
        comparator - the comparator to order elements with, or null to use the natural ordering.

    • Method Detail

      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>

      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>

      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>

      • put

        public V put​(K key,
             V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>

      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>

      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>

      • find

        LinkedHashTreeMap.Node<K,​V> find​(K key,
                                       boolean create)
        Returns the node at or adjacent to the given key, creating it if requested.
        Throws:
        java.lang.ClassCastException - if key and the tree's keys aren't mutually comparable.

      • findByEntry

        LinkedHashTreeMap.Node<K,​V> findByEntry​(java.util.Map.Entry<?,​?> entry)
        Returns this map's entry that has the same key and value as entry, 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 as String.CASE_INSENSITIVE_ORDER), then remove() and contains() will violate the collections API.

      • equal

        private boolean equal​(java.lang.Object a,
                      java.lang.Object b)

      • 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

        void removeInternal​(LinkedHashTreeMap.Node<K,​V> node,
                    boolean unlink)
        Removes node from this tree, rearranging the tree's structure as necessary.
        Parameters:
        unlink - true to also unlink this node from the iteration linked list.

      • rebalance

        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.
        Parameters:
        insert - true if the node was unbalanced by an insert; false if it was by a removal.

      • rotateLeft

        private void rotateLeft​(LinkedHashTreeMap.Node<K,​V> root)
        Rotates the subtree so that its root's right child is the new root.

      • rotateRight

        private void rotateRight​(LinkedHashTreeMap.Node<K,​V> root)
        Rotates the subtree so that its root's left child is the new root.

      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>

      • keySet

        public java.util.Set<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>

      • doubleCapacity

        private void doubleCapacity()

      • doubleCapacity

        static <K,​V> LinkedHashTreeMap.Node<K,​V>[] doubleCapacity​(LinkedHashTreeMap.Node<K,​V>[] oldTable)
        Returns a new array containing the same nodes as oldTable, but with twice as many trees, each of (approximately) half the previous size.

      • writeReplace

        private java.lang.Object writeReplace()
                               throws java.io.ObjectStreamException
        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:
        java.io.ObjectStreamException