* In the underlying implementation, this hashtable increases in size to adapt * to key/value pairs being added (the underlying size of the hashtable is * invisible to the programmer). In the underlying implementation, this * hashtable never decreases in size. As a hashtable increases in size, * it takes at most four times as much memory as it would take * to store the hashtable's keys and values in perfectly-sized arrays. * Underlying size expansions are implemented such that the operation of * expanding in size is amortized over the contstant time complexity needed to * insert new elements.
* An instance of this class is serializable; however, serialized instances of
* this class should not be stored in a persistent manner because the
* serialization implemented in this class makes no attempt at handling
* class versioning. For an instance of this class to be properly
* serialized, all object values stored in that instance must be
* serializable.
*/
public final class IntTHash
* Insertions into the hashtable are performed in [amortized] time
* complexity O(1).
* @exception IllegalArgumentException if key is negative.
* @exception NullPointerException if value is null.
*/
public final T put(final int key, final T value) {
if (key < 0) {
throw new IllegalArgumentException("key is negative");
}
if (value == null) {
throw new IllegalArgumentException("value is null");
}
if (key != m_prevKey) {
int incr = 0;
for (m_prevInx = key % m_keys.length;
(m_keys[m_prevInx] >= 0) && (m_keys[m_prevInx] != key);
m_prevInx = (m_prevInx + incr) % m_keys.length)
if (incr == 0) {
incr = 1 + (key % (m_keys.length - 1));
}
m_prevKey = key;
}
final T returnVal = m_vals.get(m_prevInx);
if (returnVal == null) {
if (m_elements == m_thresholdSize) {
incrSize();
return put(key, value);
}
m_elements++;
}
m_vals.set(m_prevInx, value);
m_keys[m_prevInx] = key;
return returnVal;
}
/**
* Returns the value bound to the specified key or null if no value is
* currently bound to the specified key.
* Searches in this hashtable are performed in [amortized] time
* complexity O(1).
* @exception IllegalArgumentException if key is negative.
*/
public final T get(final int key) {
if (key < 0) {
throw new IllegalArgumentException("key is negative");
}
if (key != m_prevKey) {
int incr = 0;
for (m_prevInx = key % m_keys.length;
(m_keys[m_prevInx] >= 0) && (m_keys[m_prevInx] != key);
m_prevInx = (m_prevInx + incr) % m_keys.length)
if (incr == 0) {
incr = 1 + (key % (m_keys.length - 1));
}
m_prevKey = key;
}
return m_vals.get(m_prevInx);
}
/**
* Returns an enumeration of keys in this hashtable, ordered
* arbitrarily.
* The returned enumeration becomes invalid as soon as put(int, Object)
* is called on this hashtable; calling methods on an invalid
* enumeration will cause undefined behavior in the enumerator.
* The returned enumerator has absolutely no effect on the underlying
* hashtable.
* This method returns in constant time. The returned enumerator
* returns successive keys in [amortized] time complexity O(1).
*/
public final IntEnumerator keys() {
final int numElements = m_elements;
return new IntEnumerator() {
int elements = numElements;
int index = -1;
public final int numRemaining() {
return elements;
}
public final int nextInt() {
while (m_keys[++index] < 0)
;
elements--;
return m_keys[index];
}
};
}
/**
* Returns an iteration of values in this hashtable, ordered
* arbitrarily.
* The returned iteration becomes invalid as soon as put(int, Object)
* is called on this hashtable; calling methods on an invalid
* iteration will cause undefined behavior in the iterator.
* The returned iterator has absolutely no effect on the underlying
* hashtable (the remove() operation on the returned iterator is not
* supported).
* This method returns in constant time. The returned iterator
* returns successive values in [amortized] time complexity O(1).
* NOTE: The order of values returned corresponds to the order of keys
* returned by the enumeration from keys() - that is, the nth
* key returned by keys() is the key into the nth value
* returned by values().
*/
public final Iterator values() {
final int numElements = m_elements;
return new Iterator() {
int elements = numElements;
int index = -1;
public final boolean hasNext() {
return elements == 0;
}
public final Object next() {
try {
while (m_vals.get(++index) == null)
;
elements--;
return m_vals.get(index);
} catch (ArrayIndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
public final void remove() {
throw new UnsupportedOperationException();
}
};
}
private final void incrSize() {
final int newSize;
try {
int primesInx = 0;
while (m_keys.length != PRIMES[primesInx++])
;
newSize = PRIMES[primesInx];
} catch (ArrayIndexOutOfBoundsException e) {
throw new IllegalStateException("too many elements in this hashtable");
}
final int[] newKeys = new int[newSize];
final List