Modeled on {@link java.util.IdentityHashMap}, but using overridable * {@link #equals(Object, Object) equals} / {@link #hashCode(Object) hashCode} * to compare/locate elements. The API of this class is similar * in function and form to {@link java.util.Map}, but doesn't use separate keys * and values. In this API an element is a key and a value at the same time. * An element is always non-null, so the return values are unambiguous. * *
Because this is a linear-probe hash table and there are no
* {@link java.util.Map.Entry} objects involved, the underlying
* data structure is very simple and memory efficient.
* It is just a sparse array of elements with length that
* is always a power of two and larger than 3 * {@link #size()} / 2.
*
* @param By default it returns:
* By default it returns:
*
* obj.{@link Object#hashCode() hashCode()}
*
* But can be overridden in subclasses.
*
* @param obj an element of this HashArray or a lookup object
* @return a hash code value for an element or lookup object.
* @see #equals(Object, Object)
*/
protected int hashCode(Object obj) {
return obj.hashCode();
}
/**
* Indicates whether an element of this HashArray is "equal to"
* a lookup object or another element.
*
*
* element.{@link Object#equals(Object) equals(obj)}
*
* But can be overridden in subclasses.
*
* @param element an element of this HashArray
* @param obj a lookup object or another element
* @return {@code true} if an element is the same
* as a lookup object or another element;
* {@code false} otherwise.
* @see #hashCode(Object)
*/
protected boolean equals(T element, Object obj) {
return element.equals(obj);
}
/**
* Returns index for Object x.
*/
private int hash(Object x, int length) {
int h = hashCode(x);
return (h ^ (h >>> 16)) & (length - 1);
}
/**
* Circularly traverses table of size length (which is a power of 2).
*/
private static int nextKeyIndex(int i, int length) {
return (i + 1) & (length - 1);
}
/**
* @return Number of elements contained in this HashArray.
*/
public int size() {
return size;
}
/**
* @param lookupObj a non-null lookup object
* @return The element which is equal to specified {@code lookupObj}
* if it exists in this HashArray or null if it doesn't.
* (There can be at most one such element.)
* @throws NullPointerException if {@code lookupObj} is null
*/
@SuppressWarnings("unchecked")
public T get(Object lookupObj) {
if (lookupObj == null) throw new NullPointerException();
final T[] tab = table;
int i = hash(lookupObj, tab.length);
while (true) {
T element = tab[i];
if (element == null) {
return null;
}
if (equals(element, lookupObj)) {
return element;
}
i = nextKeyIndex(i, tab.length);
}
}
/**
* Adds {@code newElement} if an element equal to it is not present in
* this HashArray and returns null, or returns the existing element and
* replaces it with {@code newElement} if such element is present.
*
* @param newElement new element to put into this HashArray
* @return previous element if there was one or null if there was none
*/
public T put(T newElement) {
return put(newElement, true);
}
/**
* Adds {@code newElement} if an element equal to it is not present in
* this HashArray and returns null, or returns the existing element and
* doesn't modify HashArray if such element is present.
*
* @param newElement new element to put into this HashArray
* @return previous element if there was one or null if there was none
*/
public T putIfAbsent(T newElement) {
return put(newElement, false);
}
private T put(T newElement, boolean replace) {
if (newElement == null) throw new NullPointerException();
for (; ; ) {
final T[] tab = table;
int i = hash(newElement, tab.length);
for (
T element; (element = tab[i]) != null;
i = nextKeyIndex(i, tab.length)
) {
if (equals(element, newElement)) {
if (replace) {
tab[i] = newElement;
}
return element;
}
}
final int s = size + 1;
// Use optimized form of 3 * s / 2.
// Next capacity is 2 * current capacity.
if (s + (s >> 1) > tab.length && resize(tab.length << 1))
continue;
tab[i] = newElement;
size = s;
return null;
}
}
/**
* Resizes the table if necessary to hold given capacity.
*/
private boolean resize(int newLength) {
T[] oldTable = table;
int oldLength = oldTable.length;
if (oldLength == MAXIMUM_CAPACITY) { // can't expand any further
if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
return false;
}
if (oldLength >= newLength)
return false;
@SuppressWarnings("unchecked")
T[] newTable = (T[]) new Object[newLength];
for (int j = 0; j < oldLength; j++) {
T element = oldTable[j];
if (element != null) {
oldTable[j] = null;
int i = hash(element, newLength);
while (newTable[i] != null)
i = nextKeyIndex(i, newLength);
newTable[i] = element;
}
}
table = newTable;
return true;
}
/**
* Removes the element equal to {@code lookupObj} and
* returns it if present or returns null if not present.
*
* @param lookupObj a non-null lookup object
* @return the removed element if there was one or null if
* there was none
* @throws NullPointerException if {@code lookupObj} is null
*/
public T remove(Object lookupObj) {
if (lookupObj == null) throw new NullPointerException();
T[] tab = table;
int i = hash(lookupObj, tab.length);
while (true) {
T element = tab[i];
if (element == null) {
return null;
}
if (equals(element, lookupObj)) {
size--;
tab[i] = null;
closeDeletion(tab, i);
return element;
}
i = nextKeyIndex(i, tab.length);
}
}
/**
* Rehash all possibly-colliding elements following a
* deletion. This preserves the linear-probe
* collision properties required by get, putIfAbsent, remove.
*
* @param d the index of a newly empty deleted slot
*/
private void closeDeletion(Object[] tab, int d) {
// Adapted from Knuth Section 6.4 Algorithm R
// Look for elements to swap into newly vacated slot
// starting at index immediately following deletion,
// and continuing until a null slot is seen, indicating
// the end of a run of possibly-colliding elements.
Object element;
for (
int i = nextKeyIndex(d, tab.length); (element = tab[i]) != null;
i = nextKeyIndex(i, tab.length)
) {
// The following test triggers if the element at slot i (which
// hashes to be at slot r) should take the spot vacated by d.
// If so, we swap it in, and then continue with d now at the
// newly vacated i. This process will terminate when we hit
// the null slot at the end of this run.
// The test is messy because we are using a circular table.
int r = hash(element, tab.length);
if ((i < r && (r <= d || d <= i)) || (r <= d && d <= i)) {
tab[d] = element;
tab[i] = null;
d = i;
}
}
}
/**
* Removes all of the elements from this HashArray.
*/
public void clear() {
Arrays.fill(table, null);
size = 0;
}
}