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 public class Hash {
  12
  13     /** this object is inserted as key in a slot when the
  14      *  corresponding value is removed -- this ensures that the
  15      *  probing sequence for any given key remains the same even if
  16      *  other keys are removed.
  17      */
  18     private static Object placeholder = new Object();
  19
  20     /** the number of entries with at least one non-null key */
  21     private int usedslots = 0;
  22
  23     /** the number of entries with non-null values */
  24     private int size = 0;
  25
  26     /** when num_slots < loadFactor * size, rehash into a bigger table */
  27     private final int loadFactor;
  28
  29     /** primary keys */
  30     private Object[] keys1 = null;
  31
  32     /** secondary keys; null if no secondary key has ever been added */
  33     private Object[] keys2 = null;
  34
  35     /** the values for the table */
  36     private Object[] vals = null;
  37
  38     /** the number of entries with a non-null value */
  39     public int size() { return size; }
  40
  41     /** empties the table */
  42     public void clear() {
  43         size = 0;
  44         usedslots = 0;
  45         for(int i=0; i<vals.length; i++) {
  46             vals[i] = null;
  47             keys1[i] = null;
  48             if (keys2 != null) keys2[i] = null;
  49         }
  50     }
  51
  52     /** returns all the primary keys in the table */
  53     public Object[] keys() {
  54         int howmany = 0;
  55         for(int i=0; i<vals.length; i++) if (keys1[i] != null) howmany++;
  56         Object[] ret = new Object[howmany];
  57         int where = 0;
  58         for(int i=0; i<vals.length; i++) if (keys1[i] != null) ret[where++] = keys1[i];
  59         return ret;
  60     }
  61
  62     public Hash() { this(25, 3); }
  63     public Hash(int initialcapacity, int loadFactor) {
  64         // using a pseudoprime in the form 4x+3 ensures full coverage
  65         initialcapacity = initialcapacity / 4;
  66         initialcapacity = 4 * initialcapacity + 3;
  67         keys1 = new Object[initialcapacity];
  68         vals = new Object[initialcapacity];
  69         this.loadFactor = loadFactor;
  70     }
  71
  72     public void remove(Object k1) { remove(k1, null); }
  73     public void remove(Object k1, Object k2) { put_(k1, k2, null); }
  74
  75     private void rehash() {
  76         Object[] oldkeys1 = keys1;
  77         Object[] oldkeys2 = keys2;
  78         Object[] oldvals = vals;
  79         keys1 = new Object[oldvals.length * 2];
  80         keys2 = oldkeys2 == null ? null : new Object[oldvals.length * 2];
  81         vals = new Object[oldvals.length * 2];
  82         size = 0;
  83         usedslots = 0;
  84         for(int i=0; i<oldvals.length; i++)
  85             if (((oldkeys1[i] != null && oldkeys1[i] != placeholder) || (oldkeys2 != null && oldkeys2[i] != null)) && oldvals[i] != null)
  86                 put_(oldkeys1[i], oldkeys2 == null ? null : oldkeys2[i], oldvals[i]);
  87     }
  88
  89     public Object get(Object k1) { return get(k1, null); }
  90     public Object get(Object k1, Object k2) {
  91         if (k2 != null && keys2 == null) return null;
  92         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
  93         int dest = Math.abs(hash) % vals.length;
  94         int odest = dest;
  95         int tries = 1;
  96         boolean plus = true;
  97         while (keys1[dest] != null || (keys2 != null && keys2[dest] != null)) {
  98             Object hk1 = keys1[dest];
  99             Object hk2 = keys2 == null ? null : keys2[dest];
 100             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&
 101                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
 102                 return vals[dest];
 103             }
 104             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 105             if (plus) tries++;
 106             plus = !plus;
 107         }
 108         return null;
 109     }
 110
 111     public void put(Object k1, Object v) { put(k1, null, v); }
 112     public void put(Object k1, Object k2, Object v) { put_(k1, k2, v); }
 113     private void put_(Object k1, Object k2, Object v) {
 114         if (usedslots * loadFactor > vals.length) rehash();
 115         int hash = (k1 == null ? 0 : k1.hashCode()) ^ (k2 == null ? 0 : k2.hashCode());
 116         int dest = Math.abs(hash) % vals.length;
 117         int odest = dest;
 118         boolean plus = true;
 119         int tries = 1;
 120         while (true) {
 121             Object hk1 = keys1[dest];
 122             Object hk2 = keys2 == null ? null : keys2[dest];
 123             if (hk1 == null && hk2 == null) {                                         // empty slot
 124                 if (v == null) return;
 125                 size++;
 126                 usedslots++;
 127                 break;
 128             }
 129
 130             if ((k1 == hk1 || (k1 != null && hk1 != null && k1.equals(hk1))) &&       // replacing former entry
 131                 (k2 == hk2 || (k2 != null && hk2 != null && k2.equals(hk2)))) {
 132
 133                 // we don't actually remove things from the table; rather, we insert a placeholder
 134                 if (v == null) {
 135                     k1 = placeholder;
 136                     k2 = null;
 137                     size--;
 138                 }
 139                 break;
 140             }
 141
 142             dest = Math.abs((odest + (plus ? 1 : -1 ) * tries * tries) % vals.length);
 143             if (plus) tries++;
 144             plus = !plus;
 145         }
 146
 147         keys1[dest] = k1;
 148         if (k2 != null && keys2 == null) keys2 = new Object[keys1.length];
 149         if (keys2 != null) keys2[dest] = k2;
 150         vals[dest] = v;
 151     }
 152
 153 }
 154
 155