For optimal performance, usage pattern should be one where matches
should be very common (especially after "warm-up"), and as with most hash-based
maps/sets, that hash codes are uniformly distributed. Also, collisions
are slightly more expensive than with HashMap or HashSet, since hash codes
are not used in resolving collisions; that is, equals() comparison is
done with all symbols in same bucket index.
Finally, rehashing is also more expensive, as hash codes are not
stored; rehashing requires all entries' hash codes to be recalculated.
Reason for not storing hash codes is reduced memory usage, hoping
for better memory locality.
Usual usage pattern is to create a single "master" instance, and either use that instance in sequential fashion, or to create derived "child" instances, which after use, are asked to return possible symbol additions to master instance. In either case benefit is that symbol table gets initialized so that further uses are more efficient, as eventually all symbols needed will already be in symbol table. At that point no more Symbol String allocations are needed, nor changes to symbol table itself.
Note that while individual SymbolTable instances are NOT thread-safe (much like generic collection classes), concurrently used "child" instances can be freely used without synchronization. However, using master table concurrently with child instances can only be done if access to master instance is read-only (i.e. no modifications done).
| Modifier and Type | Class and Description |
|---|---|
| pack-priv static class | CharsToNameCanonicalizer.
This class is a symbol table entry. |
| private static class | CharsToNameCanonicalizer.
Immutable value class used for sharing information as efficiently as possible, by only require synchronization of reference manipulation but not access to contents. |
| Modifier and Type | Field and Description |
|---|---|
| protected CharsToNameCanonicalizer. | _buckets
Overflow buckets; if primary doesn't match, lookup is done from here. |
| protected boolean | _canonicalize
Whether any canonicalization should be attempted (whether using intern or not. |
| protected final int | _factoryFeatures
Feature flags of |
| protected boolean | _hashShared
Flag that indicates whether underlying data structures for the main hash area are shared or not. |
| protected int | _indexMask
Mask used to get index from hash values; equal to
|
| protected int | _longestCollisionList
We need to keep track of the longest collision list; this is needed both to indicate problems with attacks and to allow flushing for other cases. |
| protected BitSet | _overflows
Lazily constructed structure that is used to keep track of collision buckets that have overflowed once: this is used to detect likely attempts at denial-of-service attacks that uses hash collisions. |
| protected final CharsToNameCanonicalizer | _parent
Sharing of learnt symbols is done by optional linking of symbol table instances with their parents. |
| protected final int | _seed
Seed value we use as the base to make hash codes non-static between different runs, but still stable for lifetime of a single symbol table instance. |
| protected int | _size
Current size (number of entries); needed to know if and when rehash. |
| protected int | _sizeThreshold
Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed. |
| protected final StreamReadConstraints | _streamReadConstraints
Constraints used by |
| protected String[] | _symbols
Primary matching symbols; it's expected most match occur from here. |
| protected final AtomicReference | _tableInfo
Member that is only used by the root table instance: root passes immutable state info child instances, and children may return new state if they add entries to the table. |
| private static final int | DEFAULT_T_SIZE
Default initial table size. |
| public static final int | |
| pack-priv static final int | MAX_COLL_CHAIN_LENGTH
Also: to thwart attacks based on hash collisions (which may or may not be cheap to calculate), we will need to detect "too long" collision chains. |
| pack-priv static final int | MAX_ENTRIES_FOR_REUSE
Let's only share reasonably sized symbol tables. |
| private static final int | MAX_T_SIZE
Let's not expand symbol tables past some maximum size; this should protected against OOMEs caused by large documents with unique (~= random) names. |
| Access | Constructor and Description |
|---|---|
| private | CharsToNameCanonicalizer(StreamReadConstraints src, int factoryFeatures, int seed)
Main method for constructing a root symbol table instance. |
| private | CharsToNameCanonicalizer(CharsToNameCanonicalizer parent, StreamReadConstraints src, int factoryFeatures, int seed, CharsToNameCanonicalizer.
Internal constructor used when creating child instances. |
| Modifier and Type | Method and Description |
|---|---|
| private String | |
| private String | |
| private void | _handleSpillOverflow(int bucketIndex, CharsToNameCanonicalizer.
Method called when an overflow bucket has hit the maximum expected length: this may be a case of DoS attack. |
| public int | Returns: Index value calculatedRaw hash value to use for calculating index rawHash)Helper method that takes in a "raw" hash value, shuffles it as necessary, and truncates to be used as the index. |
| protected void | |
| private static int | |
| public int | Returns: number of primary slots table has currentlyMethod for checking number of primary hash buckets this symbol table uses. |
| public int | Returns: Hash code calculatedInput buffer that contains name to decode buffer, int Pointer to the first character of the name start, int Length of String; has to be at least 1 (caller guarantees) len)Implementation of a hashing method for variable length Strings. |
| public int | |
| public int | Returns: Number of collisions in the primary hash areaMethod mostly needed by unit tests; calculates number of entries that are in collision list. |
| private void | copyArrays()
Method called when copy-on-write is needed; generally when first change is made to a derived symbol table. |
| public static CharsToNameCanonicalizer | Returns: Root instance to use for constructing new child instances
Deprecated
Since 2.16 use
createRoot(TokenStreamFactory) instead
|
| public static CharsToNameCanonicalizer | Returns: Root instance to use for constructing new child instancesSeed for hash value calculation seed)
Deprecated
Since 2.16 use
createRoot(TokenStreamFactory) instead
|
| public static CharsToNameCanonicalizer | Returns: Root instance to use for constructing new child instancesFactory that will use the root instance; used for accessing
configuration owner)Method called to create root canonicalizer for a |
| public static CharsToNameCanonicalizer | |
| public String | |
| public int | |
| public CharsToNameCanonicalizer | Returns: Actual canonicalizer instance that can be used by a parser"Factory" method; will create a new child instance of this symbol table. |
| public CharsToNameCanonicalizer | Returns: Actual canonicalizer instance that can be used by a parserConfiguration flags (ignored) flags)
Deprecated
Since 2.16 use
makeChild() instead.
|
| public int | Returns: Length of the collision chainMethod mostly needed by unit tests; calculates length of the longest collision chain. |
| public boolean | |
| private void | mergeChild(CharsToNameCanonicalizer.
Method that allows contents of child table to potentially be "merged in" with contents of this symbol table. |
| private void | rehash()
Method called when size (number of entries) of symbol table grows so big that load factor is exceeded. |
| public void | |
| public int | |
| protected void | verifyInternalConsistency()
Diagnostics method that will verify that internal data structures are consistent; not meant as user-facing method but only for test suites and possible troubleshooting. |
| _buckets | back to summary |
|---|---|
| protected CharsToNameCanonicalizer. Overflow buckets; if primary doesn't match, lookup is done from here. Note Number of buckets is half of number of symbol entries, on assumption there's less need for buckets. | |
| _canonicalize | back to summary |
|---|---|
| protected boolean _canonicalize Whether any canonicalization should be attempted (whether using intern or not. Note non-final since we may need to disable this with overflow. | |
| _factoryFeatures | back to summary |
|---|---|
| protected final int _factoryFeatures Feature flags of | |
| _hashShared | back to summary |
|---|---|
| protected boolean _hashShared Flag that indicates whether underlying data structures for the main hash area are shared or not. If they are, then they need to be handled in copy-on-write way, i.e. if they need to be modified, a copy needs to be made first; at this point it will not be shared any more, and can be modified. This flag needs to be checked both when adding new main entries, and when adding new collision list queues (i.e. creating a new collision list head entry) | |
| _indexMask | back to summary |
|---|---|
| protected int _indexMask Mask used to get index from hash values; equal to
| |
| _longestCollisionList | back to summary |
|---|---|
| protected int _longestCollisionList We need to keep track of the longest collision list; this is needed both to indicate problems with attacks and to allow flushing for other cases.
| |
| _overflows | back to summary |
|---|---|
| protected BitSet _overflows Lazily constructed structure that is used to keep track of collision buckets that have overflowed once: this is used to detect likely attempts at denial-of-service attacks that uses hash collisions.
| |
| _parent | back to summary |
|---|---|
| protected final CharsToNameCanonicalizer _parent Sharing of learnt symbols is done by optional linking of symbol
table instances with their parents. When parent linkage is
defined, and child instance is released (call to | |
| _seed | back to summary |
|---|---|
| protected final int _seed Seed value we use as the base to make hash codes non-static between different runs, but still stable for lifetime of a single symbol table instance. This is done for security reasons, to avoid potential DoS attack via hash collisions.
| |
| _size | back to summary |
|---|---|
| protected int _size Current size (number of entries); needed to know if and when rehash. | |
| _sizeThreshold | back to summary |
|---|---|
| protected int _sizeThreshold Limit that indicates maximum size this instance can hold before it needs to be expanded and rehashed. Calculated using fill factor passed in to constructor. | |
| _streamReadConstraints | back to summary |
|---|---|
| protected final StreamReadConstraints _streamReadConstraints Constraints used by
| |
| _symbols | back to summary |
|---|---|
| protected String[] _symbols Primary matching symbols; it's expected most match occur from here. | |
| _tableInfo | back to summary |
|---|---|
| protected final AtomicReference<CharsToNameCanonicalizer. Member that is only used by the root table instance: root passes immutable state info child instances, and children may return new state if they add entries to the table. Child tables do NOT use the reference. | |
| DEFAULT_T_SIZE | back to summary |
|---|---|
| private static final int DEFAULT_T_SIZE Default initial table size. Shouldn't be miniscule (as there's cost to both array realloc and rehashing), but let's keep it reasonably small. For systems that properly reuse factories it doesn't matter either way; but when recreating factories often, initial overhead may dominate. | |
| HASH_MULT | back to summary |
|---|---|
| public static final int HASH_MULT | |
| MAX_COLL_CHAIN_LENGTH | back to summary |
|---|---|
| pack-priv static final int MAX_COLL_CHAIN_LENGTH Also: to thwart attacks based on hash collisions (which may or may not be cheap to calculate), we will need to detect "too long" collision chains. Started with static value of 100 entries for the longest legal chain, but increased in Jackson 2.13 to 150 to work around specific test case. Note longest chain we have been able to produce without malicious intent has been 38 (with "com.fasterxml.jackson.core.main.TestWithTonsaSymbols"); our setting should be reasonable here.
| |
| MAX_ENTRIES_FOR_REUSE | back to summary |
|---|---|
| pack-priv static final int MAX_ENTRIES_FOR_REUSE Let's only share reasonably sized symbol tables. Max size set to 3/4 of 16k; this corresponds to 64k main hash index. This should allow for enough distinct names for almost any case. | |
| MAX_T_SIZE | back to summary |
|---|---|
| private static final int MAX_T_SIZE Let's not expand symbol tables past some maximum size; this should protected against OOMEs caused by large documents with unique (~= random) names. | |
| CharsToNameCanonicalizer | back to summary |
|---|---|
| private CharsToNameCanonicalizer(StreamReadConstraints src, int factoryFeatures, int seed) Main method for constructing a root symbol table instance. | |
| CharsToNameCanonicalizer | back to summary |
|---|---|
| private CharsToNameCanonicalizer(CharsToNameCanonicalizer parent, StreamReadConstraints src, int factoryFeatures, int seed, CharsToNameCanonicalizer. Internal constructor used when creating child instances. | |
| _addSymbol | back to summary |
|---|---|
| private String _addSymbol(char[] buffer, int start, int len, int h, int index) throws IOException | |
| _findSymbol2 | back to summary |
|---|---|
| private String _findSymbol2(char[] buffer, int start, int len, CharsToNameCanonicalizer. | |
| _handleSpillOverflow | back to summary |
|---|---|
| private void _handleSpillOverflow(int bucketIndex, CharsToNameCanonicalizer. Method called when an overflow bucket has hit the maximum expected length: this may be a case of DoS attack. Deal with it based on settings by either clearing up bucket (to avoid indefinite expansion) or throwing exception. Currently, the first overflow for any single bucket DOES NOT throw an exception, only second time (per symbol table instance) | |
| _hashToIndex | back to summary |
|---|---|
| public int _hashToIndex(int rawHash) Helper method that takes in a "raw" hash value, shuffles it as necessary, and truncates to be used as the index.
| |
| _reportTooManyCollisions | back to summary |
|---|---|
protected void _reportTooManyCollisions(int maxLen) throws StreamConstraintsException
| |
| _thresholdSize | back to summary |
|---|---|
| private static int _thresholdSize(int hashAreaSize) | |
| bucketCount | back to summary |
|---|---|
| public int bucketCount() Method for checking number of primary hash buckets this symbol table uses.
| |
| calcHash | back to summary |
|---|---|
| public int calcHash(char[] buffer, int start, int len) Implementation of a hashing method for variable length Strings. Most of the time intention is that this calculation is done by caller during parsing, not here; however, sometimes it needs to be done for parsed "String" too.
| |
| calcHash | back to summary |
|---|---|
| public int calcHash(String key) | |
| collisionCount | back to summary |
|---|---|
| public int collisionCount() Method mostly needed by unit tests; calculates number of
entries that are in collision list. Value can be at most
(
| |
| copyArrays | back to summary |
|---|---|
| private void copyArrays() Method called when copy-on-write is needed; generally when first change is made to a derived symbol table. | |
| createRoot | back to summary |
|---|---|
| public static CharsToNameCanonicalizer createRoot()
Deprecated Since 2.16 use
| |
| createRoot | back to summary |
|---|---|
| public static CharsToNameCanonicalizer createRoot(int seed)
Deprecated Since 2.16 use
| |
| createRoot | back to summary |
|---|---|
| public static CharsToNameCanonicalizer createRoot(TokenStreamFactory owner) Method called to create root canonicalizer for a
| |
| createRoot | back to summary |
|---|---|
| public static CharsToNameCanonicalizer createRoot(TokenStreamFactory owner, int seed) | |
| findSymbol | back to summary |
|---|---|
| public String findSymbol(char[] buffer, int start, int len, int h) throws IOException | |
| hashSeed | back to summary |
|---|---|
| public int hashSeed() | |
| makeChild | back to summary |
|---|---|
| public CharsToNameCanonicalizer makeChild() "Factory" method; will create a new child instance of this symbol table. It will be a copy-on-write instance, ie. it will only use read-only copy of parent's data, but when changes are needed, a copy will be created. Note It is generally not safe to both use makeChild/mergeChild, AND to use instance actively. Instead, a separate 'root' instance should be used on which only makeChild/mergeChild are called, but instance itself is not used as a symbol table.
| |
| makeChild | back to summary |
|---|---|
| public CharsToNameCanonicalizer makeChild(int flags)
Deprecated Since 2.16 use
| |
| maxCollisionLength | back to summary |
|---|---|
| public int maxCollisionLength() Method mostly needed by unit tests; calculates length of the
longest collision chain. This should typically be a low number,
but may be up to
| |
| maybeDirty | back to summary |
|---|---|
| public boolean maybeDirty() | |
| mergeChild | back to summary |
|---|---|
| private void mergeChild(CharsToNameCanonicalizer. Method that allows contents of child table to potentially be "merged in" with contents of this symbol table. Note that caller has to make sure symbol table passed in is really a child or sibling of this symbol table. | |
| rehash | back to summary |
|---|---|
| private void rehash() throws IOException Method called when size (number of entries) of symbol table grows so big that load factor is exceeded. Since size has to remain power of two, arrays will then always be doubled. Main work is really redistributing old entries into new String/Bucket entries. | |
| release | back to summary |
|---|---|
| public void release() Method called by the using code to indicate it is done with this instance. This lets instance merge accumulated changes into parent (if need be), safely and efficiently, and without calling code having to know about parent information. | |
| size | back to summary |
|---|---|
public int size()
| |
| verifyInternalConsistency | back to summary |
|---|---|
| protected void verifyInternalConsistency() Diagnostics method that will verify that internal data structures are consistent; not meant as user-facing method but only for test suites and possible troubleshooting.
| |
| Modifier and Type | Field and Description |
|---|---|
| public final int | |
| public final CharsToNameCanonicalizer. | |
| public final String |
| Access | Constructor and Description |
|---|---|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public String |
| length | back to summary |
|---|---|
| public final int length | |
| next | back to summary |
|---|---|
| public final CharsToNameCanonicalizer. | |
| symbol | back to summary |
|---|---|
| public final String symbol | |
| Bucket | back to summary |
|---|---|
| public Bucket(String s, CharsToNameCanonicalizer. | |
| has | back to summary |
|---|---|
| public String has(char[] buf, int start, int len) | |
| Modifier and Type | Field and Description |
|---|---|
| pack-priv final CharsToNameCanonicalizer. | |
| pack-priv final int | |
| pack-priv final int | |
| pack-priv final String[] |
| Access | Constructor and Description |
|---|---|
| public | TableInfo(int size, int longestCollisionList, String[] symbols, CharsToNameCanonicalizer.
|
| public |
| Modifier and Type | Method and Description |
|---|---|
| public static CharsToNameCanonicalizer. |
| buckets | back to summary |
|---|---|
| pack-priv final CharsToNameCanonicalizer. | |
| longestCollisionList | back to summary |
|---|---|
| pack-priv final int longestCollisionList | |
| size | back to summary |
|---|---|
| pack-priv final int size | |
| symbols | back to summary |
|---|---|
| pack-priv final String[] symbols | |
| TableInfo | back to summary |
|---|---|
| public TableInfo(int size, int longestCollisionList, String[] symbols, CharsToNameCanonicalizer. | |
| TableInfo | back to summary |
|---|---|
| public TableInfo(CharsToNameCanonicalizer src) | |
| createInitial | back to summary |
|---|---|
| public static CharsToNameCanonicalizer. | |