E
- the type of the values in this mappublic class PatriciaTrie<E> extends AbstractPatriciaTrie<java.lang.String,E>
A PATRICIA Trie
is a compressed
Trie
. Instead of storing
all data at the edges of the Trie
(and having empty internal nodes), PATRICIA stores data in every node.
This allows for very efficient traversal, insert, delete, predecessor,
successor, prefix, range, and AbstractPatriciaTrie.select(Object)
operations. All operations are performed at worst in O(K) time, where K
is the number of bits in the largest item in the tree. In practice,
operations actually take O(A(K)) time, where A(K) is the average number of
bits of all items in the tree.
Most importantly, PATRICIA requires very few comparisons to keys while doing any operation. While performing a lookup, each comparison (at most K of them, described above) will perform a single bit comparison against the given key, instead of comparing the entire key to another key.
The Trie
can return operations in
lexicographical order using the 'prefixMap', 'submap', or 'iterator' methods.
The Trie
can also
scan for items that are 'bitwise' (using an XOR metric) by the 'select' method.
Bitwise closeness is determined by the KeyAnalyzer
returning true or
false for a bit being set or not in a given key.
This PATRICIA Trie
supports both variable
length & fixed length keys. Some methods, such as AbstractPatriciaTrie.prefixMap(Object)
are suited only to variable length keys.
AbstractPatriciaTrie.TrieEntry<K,V>, AbstractPatriciaTrie.TrieIterator<E>
AbstractBitwiseTrie.BasicEntry<K,V>
Modifier and Type | Field and Description |
---|---|
private static long |
serialVersionUID |
modCount
Constructor and Description |
---|
PatriciaTrie() |
PatriciaTrie(java.util.Map<? extends java.lang.String,? extends E> m) |
addEntry, ceilingEntry, clear, comparator, containsKey, decrementSize, entrySet, firstEntry, firstKey, floorEntry, followLeft, followRight, get, getEntry, getNearestEntryForKey, headMap, higherEntry, incrementSize, isValidUplink, keySet, lastEntry, lastKey, lowerEntry, mapIterator, nextEntry, nextEntryImpl, nextEntryInSubtree, nextKey, prefixMap, previousEntry, previousKey, put, remove, removeEntry, select, selectKey, selectValue, size, subMap, subtree, tailMap, values
bitIndex, bitsPerElement, castKey, compare, compareKeys, getKeyAnalyzer, isBitSet, lengthInBits, toString
clone, containsValue, equals, hashCode, isEmpty, putAll
finalize, getClass, notify, notifyAll, wait, wait, wait
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, isEmpty, merge, putAll, putIfAbsent, remove, replace, replace, replaceAll
containsValue, isEmpty
private static final long serialVersionUID
public PatriciaTrie()
public PatriciaTrie(java.util.Map<? extends java.lang.String,? extends E> m)