1 // Copyright 2000-2005 the Contributors, as shown in the revision logs.
2 // Licensed under the Apache Public Source License 2.0 ("the License").
3 // You may not use this file except in compliance with the License.
9 /** Implementation of an unsynchronized hash table, with one or two
10 * keys, using Radke's quadradic residue linear probing instead of
11 * buckets to minimize object count (less allocations, faster GC).
12 * See C. Radke, Communications of the ACM, 1970, 103-105
16 public class Hash implements java.io.Serializable {
18 public static final long serialVersionUID = 8177551301264350283L;
20 /** this object is inserted as key in a slot when the
21 * corresponding value is removed -- this ensures that the
22 * probing sequence for any given key remains the same even if
23 * other keys are removed.
25 // FIXME: this should have been static except that that makes it nonserializable
26 private Object placeholder = new java.io.Serializable() { };
28 /** the number of entries with at least one non-null key */
29 private int usedslots = 0;
31 /** the number of entries with non-null values */
32 protected int size = 0;
34 /** when num_slots < loadFactor * size, rehash into a bigger table */
35 private final int loadFactor;
38 private Object[] keys1 = null;
40 /** secondary keys; null if no secondary key has ever been added */
41 private Object[] keys2 = null;
43 /** the values for the table */
44 private Object[] vals = null;
46 /** the number of entries with a non-null value */
47 public int size() { return size; }
49 public Object[] dumpkeys() {
50 return dumpkeys(new Object[size]);
52 public Object[] dumpkeys(Object[] ret) {
54 for(int i=0; i<keys1.length; i++)
60 public Object[] vals() {
61 Object[] ret = new Object[size()];
63 for(int i=0; i<vals.length; i++)
64 if (vals[i] != null && vals[i] != placeholder)
69 /** empties the table */
73 for(int i=0; i<vals.length; i++) {
76 if (keys2 != null) keys2[i] = null;
80 /** returns all the primary keys in the table */
81 public java.util.Enumeration enumerateKeys() { return new HashEnum(); }
83 public Hash() { this(25, 3); }
84 public Hash(int initialcapacity, int loadFactor) {
85 // using a pseudoprime in the form 4x+3 ensures full coverage
86 initialcapacity = initialcapacity / 4;
87 initialcapacity = 4 * initialcapacity + 3;
88 keys1 = new Object[initialcapacity];
89 vals = new Object[initialcapacity];
90 this.loadFactor = loadFactor;
93 public void remove(Object k1) { remove(k1, null); }
94 public void remove(Object k1, Object k2) { put_(k1, k2, null); }
96 private void rehash() {
97 Object[] oldkeys1 = keys1;
98 Object[] oldkeys2 = keys2;
99 Object[] oldvals = vals;
100 keys1 = new Object[oldvals.length * 2];
101 keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
102 vals = new Object[oldvals.length * 2];
105 for(int i=0; i<oldvals.length; i++)
106 if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
107 put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
110 public Object get(Object k1) { return get(k1, null); }
111 public Object get(Object k1, Object k2) {
112 if (k2 != null && keys2 == null) return null;
113 int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
114 int dest = Math.abs(hash) % vals.length;
118 while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
119 Object hk1 = keys1[dest];
120 Object hk2 = keys2 == null ? null : keys2[dest];
121 if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
122 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
125 dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
132 public void put(Object k1, Object v) { put(k1, null, v); }
133 public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
134 private void put_(Object k1, Object k2, Object v) {
135 if (usedslots * loadFactor > vals.length) rehash();
136 int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
137 int dest = Math.abs(hash) % vals.length;
142 Object hk1 = keys1[dest];
143 Object hk2 = keys2 == null ? null : keys2[dest];
144 if (hk1 == null && hk2 == null) { // empty slot
145 if (v == null) return;
151 if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) && // replacing former entry
152 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
154 // we don't actually remove things from the table; rather, we insert a placeholder
163 dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
169 if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
170 if (keys2 != null) keys2[dest] = k2;
174 private class HashEnum implements java.util.Enumeration {
175 private int iterator = 0;
176 private int found = 0;
178 public boolean hasMoreElements() {
179 return found < usedslots;
182 public Object nextElement() {
183 if (!hasMoreElements()) throw new java.util.NoSuchElementException();
186 while (o == null) o = keys1[iterator++];
187 if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");