1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
6 /** Implementation of an unsynchronized hash table, with one or two
7 * keys, using Radke's quadradic residue linear probing instead of
8 * buckets to minimize object count (less allocations, faster GC).
9 * See C. Radke, Communications of the ACM, 1970, 103-105
14 /** this object is inserted as key in a slot when the
15 * corresponding value is removed -- this ensures that the
16 * probing sequence for any given key remains the same even if
17 * other keys are removed.
19 private static Object placeholder = new Object();
21 /** the number of entries with at least one non-null key */
22 private int usedslots = 0;
24 /** the number of entries with non-null values */
25 protected int size = 0;
27 /** when num_slots < loadFactor * size, rehash into a bigger table */
28 private final int loadFactor;
31 private Object[] keys1 = null;
33 /** secondary keys; null if no secondary key has ever been added */
34 private Object[] keys2 = null;
36 /** the values for the table */
37 private Object[] vals = null;
39 /** the number of entries with a non-null value */
40 public int size() { return size; }
42 /** empties the table */
46 for(int i=0; i<vals.length; i++) {
49 if (keys2 != null) keys2[i] = null;
53 /** returns all the primary keys in the table */
54 public Enumeration keys() {
55 return new HashEnum(this);
58 public Hash() { this(25, 3); }
59 public Hash(int initialcapacity, int loadFactor) {
60 // using a pseudoprime in the form 4x+3 ensures full coverage
61 initialcapacity = initialcapacity / 4;
62 initialcapacity = 4 * initialcapacity + 3;
63 keys1 = new Object[initialcapacity];
64 vals = new Object[initialcapacity];
65 this.loadFactor = loadFactor;
68 public void remove(Object k1) { remove(k1, null); }
69 public void remove(Object k1, Object k2) { put_(k1, k2, null); }
71 private void rehash() {
72 Object[] oldkeys1 = keys1;
73 Object[] oldkeys2 = keys2;
74 Object[] oldvals = vals;
75 keys1 = new Object[oldvals.length * 2];
76 keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
77 vals = new Object[oldvals.length * 2];
80 for(int i=0; i<oldvals.length; i++)
81 if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
82 put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
85 public Object get(Object k1) { return get(k1, null); }
86 public Object get(Object k1, Object k2) {
87 if (k2 != null && keys2 == null) return null;
88 int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
89 int dest = Math.abs(hash) % vals.length;
93 while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
94 Object hk1 = keys1[dest];
95 Object hk2 = keys2 == null ? null : keys2[dest];
96 if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
97 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
100 dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
107 public void put(Object k1, Object v) { put(k1, null, v); }
108 public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
109 private void put_(Object k1, Object k2, Object v) {
110 if (usedslots * loadFactor > vals.length) rehash();
111 int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
112 int dest = Math.abs(hash) % vals.length;
117 Object hk1 = keys1[dest];
118 Object hk2 = keys2 == null ? null : keys2[dest];
119 if (hk1 == null && hk2 == null) { // empty slot
120 if (v == null) return;
126 if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry
127 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
129 // we don't actually remove things from the table; rather, we insert a placeholder
138 dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
144 if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
145 if (keys2 != null) keys2[dest] = k2;
149 class HashEnum implements java.util.Enumeration {
150 private final Hash parent;
151 private int iterator = 0;
152 private int found = 0;
154 public HashEnum (Hash parent) { this.parent = parent; }
156 public boolean hasMoreElements() {
157 return found < parent.usedslots;
160 public Object nextElement() {
161 if (!hasMoreElements()) throw new java.util.NoSuchElementException();
165 o = parent.keys1[iterator++];
168 if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");