* @author adam@ibex.org, crawshaw@ibex.org
*/
public abstract class Hash implements Basket {
- private static final long serialVersionUID = 3948384093L;
+ static final long serialVersionUID = 3948384093L;
/** Used internally to record used slots. */
- protected final Object placeholder = new java.io.Serializable() {
- private static final long serialVersionUID = 1331L;
- };
+ final Object placeholder = new java.io.Serializable() { private static final long serialVersionUID = 1331L; };
/** When <tt>loadFactor * usedslots > num_slots</tt>, call
* <tt>rehash()</tt>. */
- protected final float loadFactor;
+ final float loadFactor;
/** Used to determine the number of array slots required by each
* mapping entry. */
- protected final int indexmultiple;
-
- /** Number of entries with non-null key (includes placeholder slots). */
- protected int usedslots = 0;
-
- /** Number of currently available entry slots. */
- protected int numslots = 0;
+ final int indexmultiple;
/** Number of currently active entries. */
- protected int size = 0;
+ private int size = 0;
+
+ /** Number of placeholders in entries[]. */
+ private int placeholders = 0;
/** Array of mappings.
*
* Default implementation uses <tt>indexmultiple == 1</tt>, and
* stores only the keys in <tt>entries</tt>.
*/
- protected Object[] entries = null;
+ private Object[] entries = null;
+ public Hash() { this(16, 0.75F); }
+ public Hash(int cap, float load) { this(2, cap, load); }
public Hash(int indexmultiple, int initialCapacity, float loadFactor) {
// using a pseudoprime in the form 4x+3 ensures full coverage
- initialCapacity = initialCapacity / 4;
- initialCapacity = 4 * initialCapacity + 3;
- this.numslots = initialCapacity;
+ initialCapacity = (initialCapacity / 4) * 4 + 3;
this.loadFactor = loadFactor;
this.indexmultiple = indexmultiple;
-
- entries = new Object[initialCapacity * indexmultiple];
+ this.entries = new Object[initialCapacity * indexmultiple];
}
public int size() { return size; }
- public void clear() {
- for (int i = usedslots * indexmultiple; i >= 0; i--) entries[i] = null;
- size = usedslots = 0;
- }
+ public void clear() { for (int i = 0; i<entries.length; i++) entries[i] = null; size = 0; }
public boolean containsKey(Object k) { return indexOf(k) >= 0; }
* <tt>containsKey()</tt>. For a value map, use Basket.HashMap. */
public boolean containsValue(Object k) { return containsKey(k); }
- public void remove(Object k) { remove(indexOf(k)); }
+ // UGLY
+ public Object[] dumpkeys() {
+ Object[] ret = new Object[size];
+ int pos = 0;
+ for(int i=0; i<entries.length; i+=indexmultiple)
+ if (placeholder!=entries[i] && entries[i]!=null) {
+ ret[pos++] = entries[i];
+ }
+ return ret;
+ }
+
+ public void remove(Object k) { remove(indexOf(k)); }
public void remove(int dest) {
if (dest < 0) return;
- entryRemoved(dest);
-
// instead of removing, insert a placeholder
entries[dest] = placeholder;
for (int inc=1; inc < indexmultiple; inc++) entries[dest + inc] = null;
size--;
+ placeholders++;
}
- /** Insert new entry or replace existing at given index. */
- public int put(int dest, Object k) {
- if (usedslots + 1 > numslots * loadFactor) rehash();
- if (dest >= 0) { // update existing entry
- entryUpdated(dest);
- } else { // new entry
- dest = -1 * dest - 1;
- entries[dest] = k;
- for (int inc = 1; inc < indexmultiple; inc++)
- entries[dest + inc] = null;
- entryAdded(dest);
- }
- return dest;
+ public Object get(Object key) { return get(key, 0); }
+ public Object get(Object key, int whichval) {
+ int i = indexOf(key);
+ return i >= 0 ? entries[i + 1 + whichval] : null;
}
- /** Called immediately after the addition of a new entry. */
- protected abstract void entryAdded(int dest);
-
- /** Called immediately after the update of a current entry. */
- protected abstract void entryUpdated(int dest);
+ public Object put(Object key, Object value) { return put(key, value, 0); }
+ public Object put(Object key, Object value, int whichval) {
+ if (loadFactor * (size + placeholders) > entries.length) rehash();
+ int dest = indexOf(key);
+ Object old = null;
+ if (dest < 0) {
+ dest = -1 * (dest + 1);
+ if (entries[dest] != placeholder) size++;
+ entries[dest] = key;
+ for(int i=1; i<indexmultiple; i++) entries[dest+i] = null;
+ } else {
+ old = entries[dest + 1 + whichval];
+ }
+ entries[dest + 1 + whichval] = value;
+ return old;
+ }
- /** Called immediately before the removal of an entry. */
- protected abstract void entryRemoved(int dest);
+ /*
+ public boolean containsKey(Object k) { return super.containsValue(k); }
+ public boolean containsValue(Object v) {
+ for (int i=0; i < entries.length/indexmultiple; i++)
+ if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
+ !equals(placeholder, entries[i * indexmultiple]) &&
+ v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
+ return true;
+ return false;
+ }
+ */
/** Compares two keys for equality. <tt>userKey</tt> is the key
* passed to the map, <tt>storedKey</tt> is from the map.
* <p>Uses <tt>placeholder</tt> as a placeholder object, and
* compares keys using <tt>equals(Object, Object)</tt>.</p>
*/
- protected int indexOf(Object k) {
+ private int indexOf(Object k) {
// special case null key
if (k == null) return equals(placeholder, entries[0]) ? -1 : 0;
int hash = k == null ? 0 : k.hashCode();
- final int orig = Math.abs(hash) % numslots;
+ final int orig = Math.abs(hash) % (entries.length / indexmultiple);
int dest = orig * indexmultiple;
int tries = 1;
boolean plus = true;
while (entries[dest] != null) {
if (equals(k, entries[dest])) return dest;
- dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % numslots) * indexmultiple;
+ dest = Math.abs((orig + (plus ? 1 : -1) * tries * tries) % (entries.length / indexmultiple)) * indexmultiple;
if (plus) tries++;
plus = !plus;
}
* set (removes <tt>placeholder</tt> references) and if necessary
* by increasing the size of the <tt>entries</tt> array.
*/
- protected void rehash() {
- int oldnumslots = numslots;
+ private void rehash() {
Object[] oldentries = entries;
+ entries = new Object[oldentries.length * indexmultiple];
- if (size * 2 > usedslots) numslots *= 2;
- entries = new Object[numslots * indexmultiple];
-
- for (int i=0; i < oldnumslots; i++) {
+ for (int i=0; i < (oldentries.length/indexmultiple); i++) {
int pos = i * indexmultiple;
if (pos > 0 && oldentries[pos] == null) continue;
if (oldentries[pos] == placeholder) continue;
// dont adjust any of the support entries
int dest = indexOf(oldentries[pos]);
- dest = -1 * dest - 1; size++; usedslots++; // always new entry
+ dest = -1 * dest - 1; size++; // always new entry
for (int inc=0; inc < indexmultiple; inc++)
entries[dest + inc] = oldentries[pos + inc];
}
+ placeholders = 0;
}
}
public class HashMap extends Hash implements Map {
- private static final long serialVersionUID = 2348905755L;
-
- public HashMap() { this(16, 0.75F); }
- public HashMap(int cap, float load) { super(2, cap, load); }
-
- public Object get(Object key) { int i = indexOf(key); return i >= 0 ? entries[i + 1] : null; }
- public Object put(Object key, Object value) {
- Object old = null;
- int dest = indexOf(key);
- if (dest >= 0) old = entries[(-1 * dest - 1) + 1];
- dest = put(dest, key);
- entries[dest + 1] = value;
- return old;
- }
-
- protected void entryAdded(int dest) {}
- protected void entryUpdated(int dest) {}
- protected void entryRemoved(int dest) {}
-
- public boolean containsKey(Object k) { return super.containsValue(k); }
-
- public boolean containsValue(Object v) {
- for (int i=0; i < numslots; i++)
- if ((i == 0 || entries[i * indexmultiple] != null) && // exception for null key
- !equals(placeholder, entries[i * indexmultiple]) &&
- v == null ? entries[i + 1] == null : v.equals(entries[i + 1]))
- return true;
- return false;
- }
+ public HashMap() { super(); }
+ public HashMap(int x, float y) { super(x,y); }
+ public HashMap(int x, int z, float y) { super(x,z,y); }
}
+
}
projects / org.ibex.util.git / commitdiff