Class SmallSortedMap<K extends Comparable<K>, V>

java.lang.Object
java.util.AbstractMap<K,V>
com.google.protobuf.SmallSortedMap<K,V>
All Implemented Interfaces:
Map<K,V>
class SmallSortedMap<K extends Comparable<K>, V> extends AbstractMap<K,V>
A custom map implementation from FieldDescriptor to Object optimized to minimize the number of memory allocations for instances with a small number of mappings. The implementation stores the first k mappings in an array for a configurable value of k, allowing direct access to the corresponding Entrys without the need to create an Iterator. The remaining entries are stored in an overflow map. Iteration over the entries in the map should be done as follows: 
for (int i = 0; i < fieldMap.getNumArrayEntries(); i++) {
  process(fieldMap.getArrayEntryAt(i));
}
for (Map.Entry<K, V> entry : fieldMap.getOverflowEntries()) {
  process(entry);
}
The resulting iteration is in order of ascending field tag number. The object returned by entrySet() adheres to the same contract but is less efficient as it necessarily involves creating an object for iteration.

The tradeoff for this memory efficiency is that the worst case running time of the put() operation is O(k + lg n), which happens when entries are added in descending order. k should be chosen such that it covers enough common cases without adversely affecting larger maps. In practice, the worst case scenario does not happen for extensions because extension fields are serialized and deserialized in order of ascending tag number, but the worst case scenario can happen for DynamicMessages.

The running time for all other operations is similar to that of TreeMap.

Instances are not thread-safe until makeImmutable() is called, after which any modifying operation will result in an UnsupportedOperationException.

  • Field Details

    • DEFAULT_FIELD_MAP_ARRAY_SIZE

      static final int DEFAULT_FIELD_MAP_ARRAY_SIZE
      See Also:

    • entries

      private Object[] entries

    • entriesSize

      private int entriesSize

    • overflowEntries

      private Map<K extends Comparable<K>, V> overflowEntries

    • isImmutable

      private boolean isImmutable

    • lazyEntrySet

      private volatile SmallSortedMap<K extends Comparable<K>, V>.EntrySet lazyEntrySet

    • overflowEntriesDescending

      private Map<K extends Comparable<K>, V> overflowEntriesDescending

  • Constructor Details

    • SmallSortedMap

      private SmallSortedMap()

  • Method Details