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>

public final class LinkedHashTreeMap<K,V> extends AbstractMap<K,V> implements 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:
  • Field Details

  • Constructor Details

    • LinkedHashTreeMap

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

      public LinkedHashTreeMap(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 Details

    • size

      public int size()
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
    • get

      public V get(Object key)
      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
    • containsKey

      public boolean containsKey(Object key)
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
    • put

      public V put(K key, V value)
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
    • remove

      public V remove(Object key)
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class 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:
      ClassCastException - if key and the tree's keys aren't mutually comparable.
    • findByObject

      LinkedHashTreeMap.Node<K,V> findByObject(Object key)
    • findByEntry

      LinkedHashTreeMap.Node<K,V> findByEntry(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(Object a, 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.
    • removeInternalByKey

      LinkedHashTreeMap.Node<K,V> removeInternalByKey(Object key)
    • replaceInParent

      private void replaceInParent(LinkedHashTreeMap.Node<K,V> node, LinkedHashTreeMap.Node<K,V> replacement)
    • 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 Set<Map.Entry<K,V>> entrySet()
      Specified by:
      entrySet in interface Map<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
      Overrides:
      keySet in class 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 Object writeReplace() throws 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:
      ObjectStreamException
    • readObject

      private void readObject(ObjectInputStream in) throws IOException
      Throws:
      IOException