This class is a symbol table implementation that guarantees that strings used as identifiers are unique references. Multiple calls to addSymbol will always return the same string reference.

The symbol table performs the same task as String.intern() with the following differences:

A new string object does not need to be created in order to retrieve a unique reference. Symbols can be added by using a series of characters in a character array.
Users of the symbol table can provide their own symbol hashing implementation. For example, a simple string hashing algorithm may fail to produce a balanced set of hashcodes for symbols that are mostly unique. Strings with similar leading characters are especially prone to this poor hashing behavior.

Nested and Inner Type Summary

Modifier and Type	Class and Description
protected static class	SymbolTable.Entry This class is a symbol table entry.

Field Summary

Modifier and Type	Field and Description
protected SymbolTable.Entry[]	fBuckets Buckets.
protected final int	fCollisionThreshold A new hash function is selected and the table is rehashed when the number of keys in the bucket exceeds this threshold.
protected transient int	fCount The total number of entries in the hash table.
protected int[]	fHashMultipliers Array of randomly selected hash function multipliers or `null` if the default String.hashCode() function should be used.
protected float	fLoadFactor The load factor for the SymbolTable.
protected int	fTableSize actual table size
protected int	fThreshold The table is rehashed when its size exceeds this threshold.
protected static final int	MAX_HASH_COLLISIONS Maximum hash collisions per bucket for a table with load factor == 1.
protected static final int	MULTIPLIERS_MASK
protected static final int	MULTIPLIERS_SIZE
protected static final int	TABLE_SIZE Default table size.

Constructor Summary

Access	Constructor and Description
public	SymbolTable(int the initial capacity of the SymbolTable. initialCapacity, float the load factor of the SymbolTable. loadFactor) Constructs a new, empty SymbolTable with the specified initial capacity and the specified load factor.
public	SymbolTable(int the initial capacity of the hashtable. initialCapacity) Constructs a new, empty SymbolTable with the specified initial capacity and default load factor, which is `0.75`.
public	SymbolTable() Constructs a new, empty SymbolTable with a default initial capacity (101) and load factor, which is `0.75`.

Method Summary

Modifier and Type	Method and Description
public String	addSymbol(String The new symbol. symbol) Adds the specified symbol to the symbol table and returns a reference to the unique symbol.
public String	addSymbol(char[] The buffer containing the new symbol. buffer, int The offset into the buffer of the new symbol. offset, int The length of the new symbol in the buffer. length) Adds the specified symbol to the symbol table and returns a reference to the unique symbol.
private String	addSymbol0(String symbol, int bucket, int collisionCount)
private String	addSymbol0(char[] buffer, int offset, int length, int bucket, int collisionCount)
public boolean	containsSymbol(String The symbol to look for. symbol) Returns true if the symbol table already contains the specified symbol.
public boolean	containsSymbol(char[] The buffer containing the symbol to look for. buffer, int The offset into the buffer. offset, int The length of the symbol in the buffer. length) Returns true if the symbol table already contains the specified symbol.
public int	hash(String The symbol to hash. symbol) Returns a hashcode value for the specified symbol.
public int	hash(char[] The character buffer containing the symbol. buffer, int The offset into the character buffer of the start of the symbol. offset, int The length of the symbol. length) Returns a hashcode value for the specified symbol information.
private int	hash0(String symbol)
private int	hash0(char[] buffer, int offset, int length)
protected void	rebalance() Randomly selects a new hash function and reorganizes this SymbolTable in order to more evenly distribute its entries across the table.
protected void	rehash() Increases the capacity of and internally reorganizes this SymbolTable, in order to accommodate and access its entries more efficiently.
private void	rehashCommon(final int newCapacity)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

fBuckets	back to summary
protected SymbolTable.Entry[] fBuckets Buckets.

fCollisionThreshold	back to summary
protected final int fCollisionThreshold A new hash function is selected and the table is rehashed when the number of keys in the bucket exceeds this threshold.

fCount	back to summary
protected transient int fCount The total number of entries in the hash table.

fHashMultipliers	back to summary
protected int[] fHashMultipliers Array of randomly selected hash function multipliers or `null` if the default String.hashCode() function should be used.

fLoadFactor	back to summary
protected float fLoadFactor The load factor for the SymbolTable.

fTableSize	back to summary
protected int fTableSize actual table size

fThreshold	back to summary
protected int fThreshold The table is rehashed when its size exceeds this threshold. (The value of this field is (int)(capacity * loadFactor).)

MAX_HASH_COLLISIONS	back to summary
protected static final int MAX_HASH_COLLISIONS Maximum hash collisions per bucket for a table with load factor == 1.

MULTIPLIERS_MASK	back to summary
protected static final int MULTIPLIERS_MASK

MULTIPLIERS_SIZE	back to summary
protected static final int MULTIPLIERS_SIZE

TABLE_SIZE	back to summary
protected static final int TABLE_SIZE Default table size.

Constructor Detail

SymbolTable	back to summary
public SymbolTable(int initialCapacity, float loadFactor) Constructs a new, empty SymbolTable with the specified initial capacity and the specified load factor. Parameters initialCapacity:int the initial capacity of the SymbolTable. loadFactor:float the load factor of the SymbolTable. Exceptions IllegalArgumentException: if the initial capacity is less than zero, or if the load factor is nonpositive.

SymbolTable

back to summary

public SymbolTable(int initialCapacity, float loadFactor)

Constructs a new, empty SymbolTable with the specified initial capacity and the specified load factor.

Parameters

initialCapacity:int: the initial capacity of the SymbolTable.
loadFactor:float: the load factor of the SymbolTable.

Exceptions

IllegalArgumentException:: if the initial capacity is less than zero, or if the load factor is nonpositive.

SymbolTable back to summary

SymbolTable	back to summary
public SymbolTable(int initialCapacity) Constructs a new, empty SymbolTable with the specified initial capacity and default load factor, which is `0.75`. Parameters initialCapacity:int the initial capacity of the hashtable. Exceptions IllegalArgumentException: if the initial capacity is less than zero.

public SymbolTable(int initialCapacity)

Constructs a new, empty SymbolTable with the specified initial capacity and default load factor, which is 0.75.

Parameters

initialCapacity:int: the initial capacity of the hashtable.

Exceptions

IllegalArgumentException:: if the initial capacity is less than zero.

SymbolTable	back to summary
public SymbolTable() Constructs a new, empty SymbolTable with a default initial capacity (101) and load factor, which is `0.75`.

Method Detail

addSymbol	back to summary
public String addSymbol(String symbol) Adds the specified symbol to the symbol table and returns a reference to the unique symbol. If the symbol already exists, the previous symbol reference is returned instead, in order guarantee that symbol references remain unique. Parameters symbol:String The new symbol.

addSymbol

back to summary

public String addSymbol(String symbol)

Adds the specified symbol to the symbol table and returns a reference to the unique symbol. If the symbol already exists, the previous symbol reference is returned instead, in order guarantee that symbol references remain unique.

Parameters

symbol:String: The new symbol.

addSymbol	back to summary
public String addSymbol(char[] buffer, int offset, int length) Adds the specified symbol to the symbol table and returns a reference to the unique symbol. If the symbol already exists, the previous symbol reference is returned instead, in order guarantee that symbol references remain unique. Parameters buffer:char[] The buffer containing the new symbol. offset:int The offset into the buffer of the new symbol. length:int The length of the new symbol in the buffer.

addSymbol

back to summary

public String addSymbol(char[] buffer, int offset, int length)

Parameters

buffer:char[]: The buffer containing the new symbol.
offset:int: The offset into the buffer of the new symbol.
length:int: The length of the new symbol in the buffer.

addSymbol0	back to summary
private String addSymbol0(String symbol, int bucket, int collisionCount)

addSymbol0	back to summary
private String addSymbol0(char[] buffer, int offset, int length, int bucket, int collisionCount)

containsSymbol	back to summary
public boolean containsSymbol(String symbol) Returns true if the symbol table already contains the specified symbol. Parameters symbol:String The symbol to look for.

containsSymbol

back to summary

public boolean containsSymbol(String symbol)

Returns true if the symbol table already contains the specified symbol.

Parameters

symbol:String: The symbol to look for.

containsSymbol	back to summary
public boolean containsSymbol(char[] buffer, int offset, int length) Returns true if the symbol table already contains the specified symbol. Parameters buffer:char[] The buffer containing the symbol to look for. offset:int The offset into the buffer. length:int The length of the symbol in the buffer.

containsSymbol

back to summary

public boolean containsSymbol(char[] buffer, int offset, int length)

Returns true if the symbol table already contains the specified symbol.

Parameters

buffer:char[]: The buffer containing the symbol to look for.
offset:int: The offset into the buffer.
length:int: The length of the symbol in the buffer.

hash back to summary

hash	back to summary
public int hash(String symbol) Returns a hashcode value for the specified symbol. The value returned by this method must be identical to the value returned by the `hash(char[],int,int)` method when called with the character array that comprises the symbol string. Parameters symbol:String The symbol to hash.

public int hash(String symbol)

Returns a hashcode value for the specified symbol. The value returned by this method must be identical to the value returned by the hash(char[],int,int) method when called with the character array that comprises the symbol string.

Parameters

symbol:String: The symbol to hash.

hash back to summary

hash	back to summary
public int hash(char[] buffer, int offset, int length) Returns a hashcode value for the specified symbol information. The value returned by this method must be identical to the value returned by the `hash(String)` method when called with the string object created from the symbol information. Parameters buffer:char[] The character buffer containing the symbol. offset:int The offset into the character buffer of the start of the symbol. length:int The length of the symbol.

public int hash(char[] buffer, int offset, int length)

Returns a hashcode value for the specified symbol information. The value returned by this method must be identical to the value returned by the hash(String) method when called with the string object created from the symbol information.

Parameters

buffer:char[]: The character buffer containing the symbol.
offset:int: The offset into the character buffer of the start of the symbol.
length:int: The length of the symbol.

hash0	back to summary
private int hash0(String symbol)

hash0	back to summary
private int hash0(char[] buffer, int offset, int length)

rebalance	back to summary
protected void rebalance() Randomly selects a new hash function and reorganizes this SymbolTable in order to more evenly distribute its entries across the table. This method is called automatically when the number keys in one of the SymbolTable's buckets exceeds the given collision threshold.

rehash	back to summary
protected void rehash() Increases the capacity of and internally reorganizes this SymbolTable, in order to accommodate and access its entries more efficiently. This method is called automatically when the number of keys in the SymbolTable exceeds this hashtable's capacity and load factor.

rehashCommon	back to summary
private void rehashCommon(final int newCapacity)

com.sun.org.apache.xerces.internal.util back to summary

protected final Class SymbolTable.Entry

Class Inheritance

extends Object

java.lang.Object
com.sun.org.apache.xerces.internal.util.SymbolTable.Entry

This class is a symbol table entry. Each entry acts as a node in a linked list.

Field Summary

Modifier and Type	Field and Description
public final char[]	characters Symbol characters.
public SymbolTable.Entry	next The next entry.
public final String	symbol Symbol.

Constructor Summary

Access	Constructor and Description
public	Entry(String symbol, SymbolTable.Entry next) Constructs a new entry from the specified symbol and next entry reference.
public	Entry(char[] ch, int offset, int length, SymbolTable.Entry next) Constructs a new entry from the specified symbol information and next entry reference.

Method Summary

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

characters	back to summary
public final char[] characters Symbol characters. This information is duplicated here for comparison performance.

next	back to summary
public SymbolTable.Entry next The next entry.

symbol	back to summary
public final String symbol Symbol.

Constructor Detail

Entry	back to summary
public Entry(String symbol, SymbolTable.Entry next) Constructs a new entry from the specified symbol and next entry reference.

Entry	back to summary
public Entry(char[] ch, int offset, int length, SymbolTable.Entry next) Constructs a new entry from the specified symbol information and next entry reference.

public Class SymbolTable

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

protected final Class SymbolTable.Entry

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail