All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class com.micronova.util.IXHashtable 

java.lang.Object
   |
   +----com.micronova.util.IXVector
           |
           +----com.micronova.util.IXHashtable
public abstract class IXHashtable
extends IXVector
IXHashtable implements value-type-independent double-hashing Hashtable.

Version:
1.0

Variable Index

o _codes
Contains hashcodes.
o _keys
Contains keys.
o _level
Index such that the array size is equal to primes[level].
o _maxCount
Max number of elements to be held without rehashing.
o _threshold
Threshold percentage.
o primes
prime numbers close to 2^n.

Constructor Index

o IXHashtable()
Construct an IXHashtable with 75% threshold (default).
o IXHashtable(int, int)
Construct an IHashtable with given capacity and threshold.

Method Index

o _computeLevel(int)
Returns index such that primes[index] is greater than given size.
o _get(Object, int)
Returns the index for the given key (where the corresponding value can be retrieved).
o _getHash(Object)
Computes hashcode for a given key.
o _locate(Object[], int[], Object, int, boolean)
Locates given 'key' with hashcode 'h' and returns its index in the given keys[] and codes[] arrays.
o _put(Object, int)
Puts a key with given hashcode and returns its index (where the corresponding value should be stored).
o _rehash(int, int)
Rehashes to newLength and returns an array of indices for value re-mapping.
o _remove(Object, int)
Removes a key and returns the index (from where the corresponding value must be removed).
o _setLevel(int)
Initialize to given level.

Variables

o primes 
 protected static int primes[]
prime numbers close to 2^n. IXHashtable size is always a prime number.

o _codes 
 protected int _codes[]
Contains hashcodes. Contains 0 if the slot is empty, -1 if an element is removed.

o _keys 
 protected Object _keys[]
Contains keys.

o _level 
 protected int _level
Index such that the array size is equal to primes[level]. This is incremented on rehashing.

o _maxCount 
 protected int _maxCount
Max number of elements to be held without rehashing.

o _threshold 
 protected int _threshold
Threshold percentage. 'maxCount' is set to 'length * threshold / 100'.

Constructors

o IXHashtable 
 public IXHashtable()
Construct an IXHashtable with 75% threshold (default).

o IXHashtable 
 public IXHashtable(int capacity,
                    int threshold)
Construct an IHashtable with given capacity and threshold. IHashtable constructed this way holds given 'capacity' elements without rehashing.

Methods

o _computeLevel 
 protected final int _computeLevel(int size)
Returns index such that primes[index] is greater than given size.

o _getHash 
 protected int _getHash(Object key)
Computes hashcode for a given key. Always returns a positive (non-zero) number.

o _locate 
 protected static final int _locate(Object keys[],
                                    int codes[],
                                    Object key,
                                    int h,
                                    boolean doPut)
Locates given 'key' with hashcode 'h' and returns its index in the given keys[] and codes[] arrays. If 'doPut' is true, returns the first empty slot index if given key is not found. If 'doPut' is false, returns -1 if key is not found.

o _setLevel 
 protected void _setLevel(int level)
Initialize to given level.

o _rehash 
 protected final int[] _rehash(int newLength,
                               int currentLength)
Rehashes to newLength and returns an array of indices for value re-mapping. _codes and _keys are resized and rehashed after this operation. Returns an integer array x[] of currentLength indicating that a value at index i should be moved to index x[i] after resizing if x[i] is not negative. This sets _length.

o _put 
 protected final int _put(Object key,
                          int h)
Puts a key with given hashcode and returns its index (where the corresponding value should be stored).

o _get 
 protected final int _get(Object key,
                          int h)
Returns the index for the given key (where the corresponding value can be retrieved). Returns -1 if key is not found.

o _remove 
 protected final int _remove(Object key,
                             int h)
Removes a key and returns the index (from where the corresponding value must be removed). Returns -1 if key is not found. 

All Packages  Class Hierarchy  This Package  Previous  Next  Index