src/org/xwt/util/Hash.java

   1 // Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt.util;
   3
   4 import java.util.*;
   5
   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
  10  *
  11  *  Not threadsafe.
  12  */
  13 public class Hash {
  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.
  18      */
  19     private static Object placeholder = new Object();
  20
  21     /** the number of entries with at least one non-null key */
  22     private int usedslots = 0;
  23
  24     /** the number of entries with non-null values */
  25     protected int size = 0;
  26
  27     /** when num_slots < loadFactor * size, rehash into a bigger table */
  28     private final int loadFactor;
  29
  30     /** primary keys */
  31     private Object[] keys1 = null;
  32
  33     /** secondary keys; null if no secondary key has ever been added */
  34     private Object[] keys2 = null;
  35
  36     /** the values for the table */
  37     private Object[] vals = null;
  38
  39     /** the number of entries with a non-null value */
  40     public int size() { return size; }
  41
  42     /** empties the table */
  43     public void clear() {
  44         size = 0;
  45         usedslots = 0;
  46         for(int i=0; i<vals.length; i++) {
  47             vals[i] = null;
  48             keys1[i] = null;
  49             if (keys2 != null) keys2[i] = null;
  50         }
  51     }
  52
  53     /** returns all the primary keys in the table */
  54     public Enumeration keys() { return new HashEnum(); }
  55
  56     public Hash() { this(25, 3); }
  57     public Hash(int initialcapacity, int loadFactor) {
  58         // using a pseudoprime in the form 4x+3 ensures full coverage
  59         initialcapacity = initialcapacity / 4;
  60         initialcapacity = 4 * initialcapacity + 3;
  61         keys1 = new Object[initialcapacity];
  62         vals = new Object[initialcapacity];
  63         this.loadFactor = loadFactor;
  64     }
  65
  66     public void remove(Object k1) { remove(k1, null); }
  67     public void remove(Object k1, Object k2) { put_(k1, k2, null); }
  68
  69     private void rehash() {
  70         Object[] oldkeys1 = keys1;
  71         Object[] oldkeys2 = keys2;
  72         Object[] oldvals = vals;
  73         keys1 = new Object[oldvals.length * 2];
  74         keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
  75         vals = new Object[oldvals.length * 2];
  76         size = 0;
  77         usedslots = 0;
  78         for(int i=0; i<oldvals.length; i++)
  79             if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
  80                 put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
  81     }
  82
  83     public Object get(Object k1) { return get(k1, null); }
  84     public Object get(Object k1, Object k2) {
  85         if (k2 != null && keys2 == null) return null;
  86         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
  87         int dest = Math.abs(hash) % vals.length;
  88         int odest = dest;
  89         int tries = 1;
  90         boolean plus = true;
  91         while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
  92             Object hk1 = keys1[dest];
  93             Object hk2 = keys2 == null ? null : keys2[dest];
  94             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
  95                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
  96                 return vals[dest];
  97             }
  98             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
  99             if (plus) tries++;
 100             plus = !plus;
 101         }
 102         return null;
 103     }
 104
 105     public void put(Object k1, Object v) { put(k1, null, v); }
 106     public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
 107     private void put_(Object k1, Object k2, Object v) {
 108         if (usedslots * loadFactor > vals.length) rehash();
 109         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
 110         int dest = Math.abs(hash) % vals.length;
 111         int odest = dest;
 112         boolean plus = true;
 113         int tries = 1;
 114         while (true) {
 115             Object hk1 = keys1[dest];
 116             Object hk2 = keys2 == null ? null : keys2[dest];
 117             if (hk1 == null && hk2 == null) {                                         // empty slot
 118                 if (v == null) return;
 119                 size++;
 120                 usedslots++;
 121                 break;
 122             }
 123
 124             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&       // replacing former entry
 125                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
 126
 127                 // we don't actually remove things from the table; rather, we insert a placeholder
 128                 if (v == null) {
 129                     k1 = placeholder;
 130                     k2 = null;
 131                     size--;
 132                 }
 133                 break;
 134             }
 135
 136             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 137             if (plus) tries++;
 138             plus = !plus;
 139         }
 140
 141         keys1[dest] = k1;
 142         if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
 143         if (keys2 != null) keys2[dest] = k2;
 144         vals[dest] = v;
 145     }
 146
 147     private class HashEnum implements java.util.Enumeration {
 148         private int iterator = 0;
 149         private int found = 0;
 150
 151         public HashEnum () { }
 152
 153         public boolean hasMoreElements() {
 154             return found < usedslots;
 155         }
 156
 157         public Object nextElement() {
 158             if (!hasMoreElements()) throw new java.util.NoSuchElementException();
 159
 160             Object o = null;
 161             while (o == null) o = keys1[iterator++];
 162             if (o == null) throw new IllegalStateException("Didn't find an element, when I should have.");
 163             found++;
 164
 165             return o;
 166         }
 167     }
 168 }
 169
 170