oscript.util
Class OpenHashSymbolTable

java.lang.Object
  extended byoscript.util.OpenHashSymbolTable
All Implemented Interfaces:
java.io.Externalizable, java.io.Serializable, SymbolTable

public class OpenHashSymbolTable
extends java.lang.Object
implements SymbolTable, java.io.Externalizable

A symbol table implementation based on a open hash map, using double hashing as a strategy to avoid collisions. Double hasing uses two hash functions to compute an index into the table:

    Idx(i,k) := H1(k) + i * H2(k)
 
where for a given key k, i is incremented from 0 until an unused table slot is found.

Threading note: this class is not synchronized, but is designed to save to read from multiple threads, while write from a single thread context (at a time).

Version:
1.0
Author:
Rob Clark (rob@ti.com)
See Also:
Serialized Form

Field Summary
 
Fields inherited from interface oscript.util.SymbolTable
MIN_SYMBOL_ID
 
Constructor Summary
OpenHashSymbolTable()
          Class Constructor.
OpenHashSymbolTable(int capacity, float load)
          Class Constructor.
 
Method Summary
 int create(int id)
          Get the index that the specified symbol maps to, and create a new one if a mapping does not already exist.
 int get(int id)
          Get the index that the specified symbol maps to.
 float getLoad()
           
static java.lang.String getStats()
           
 void readExternal(java.io.ObjectInput in)
           
 int size()
          The number of mappings that exist in this table.
 java.util.Iterator symbols()
          Return an iteration of the keys (symbols) into this table.
 void writeExternal(java.io.ObjectOutput out)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

OpenHashSymbolTable

public OpenHashSymbolTable()
Class Constructor.


OpenHashSymbolTable

public OpenHashSymbolTable(int capacity,
                           float load)
Class Constructor.

Parameters:
capacity - the initial capacity
load - the loading factor
Method Detail

getLoad

public float getLoad()

get

public final int get(int id)
Get the index that the specified symbol maps to.

Specified by:
get in interface SymbolTable
Parameters:
id - the id of the symbol to get a mapping for
Returns:
an index, or -1 if no mapping exists for the specified symbol

create

public int create(int id)
Get the index that the specified symbol maps to, and create a new one if a mapping does not already exist. If a new mapping is created, it's value is the next successive array index, ie. the the previous array index plus one. The first mapping created has the value zero.

Specified by:
create in interface SymbolTable
Parameters:
id - the id of the symbol to get a mapping for
Returns:
an index

getStats

public static final java.lang.String getStats()

size

public int size()
The number of mappings that exist in this table.

Specified by:
size in interface SymbolTable
Returns:
the number of mappings in the table

symbols

public java.util.Iterator symbols()
Return an iteration of the keys (symbols) into this table. To conform to the Iterator interface, each symbol is wrapped (boxed) in a Integer.

Specified by:
symbols in interface SymbolTable
Returns:
an iteration of symbols that are keys into this table

readExternal

public void readExternal(java.io.ObjectInput in)
                  throws java.io.IOException
Specified by:
readExternal in interface java.io.Externalizable
Throws:
java.io.IOException

writeExternal

public void writeExternal(java.io.ObjectOutput out)
                   throws java.io.IOException
Specified by:
writeExternal in interface java.io.Externalizable
Throws:
java.io.IOException