KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > gnu > kawa > util > GeneralHashTable


1 // Copyright (c) 2005 Per M.A. Bothner.
2
// This is free software; for terms and warranty disclaimer see COPYING.
3

4 package gnu.kawa.util;
5
6 /** A generic hash table.
7  * Supports deletions, and re-allocates the table when too big.
8  * The equivalence relation can be customized. */

9
10 public class GeneralHashTable
11 // FUTURE: implements java.util.Map
12
{
13   protected HashNode[] table;
14   protected int mask;
15   protected int num_bindings;
16
17   public GeneralHashTable ()
18   {
19     this(64);
20   }
21
22   public GeneralHashTable (int capacity)
23   {
24     int log2Size = 4;
25     while (capacity > (1 << log2Size))
26       log2Size++;
27     capacity = 1 << log2Size;
28     table = new HashNode[capacity];
29     mask = capacity - 1;
30   }
31
32   /** Allocate a new node in the hash table. */
33   protected HashNode makeEntry (Object JavaDoc key, int hash, Object JavaDoc value)
34   {
35     HashNode node = new HashNode();
36     node.key = key;
37     node.hash = hash;
38     node.value = value;
39     return node;
40   }
41
42   /** Calculate hash code of a key.
43    * You may need to override this if you override the <code>matches</code> method.
44    */

45   public int hash (Object JavaDoc key)
46   {
47     // FIXME
48
return key == null ? 0 : key.hashCode();
49   }
50
51   public int hash (HashNode node)
52   {
53     //return hash(node.getKey());
54
return node.hash;
55   }
56
57   public boolean matches (Object JavaDoc key, int hash, HashNode node)
58   {
59     return node.hash == hash && matches(node.getKey(), key);
60   }
61
62   /** Compare two keys for equivalence.
63    * Override this and the {@link #hash(Object)} method if you want
64    * a different equivalence relation.
65    */

66   public boolean matches (Object JavaDoc value1, Object JavaDoc value2)
67   {
68     // FIXME
69
return value1 == value2 || (value1 != null && value1.equals(value2));
70   }
71
72   public Object JavaDoc get (Object JavaDoc key, Object JavaDoc defaultValue)
73   {
74     int hash = hash(key);
75     int index = hash & this.mask;
76     for (HashNode node = table[index];
77      node != null; node = node.next)
78       {
79     if (matches(key, hash, node))
80       return node.getValue();
81       }
82     return defaultValue;
83   }
84
85   public HashNode getNode (Object JavaDoc key)
86   {
87     int hash = hash(key);
88     int index = hash & this.mask;
89     for (HashNode node = table[index];
90      node != null; node = node.next)
91       {
92     if (matches(key, hash, node))
93           return node;
94       }
95     return null;
96   }
97
98   public Object JavaDoc put (Object JavaDoc key, Object JavaDoc value)
99   {
100     return put(key, hash(key), value);
101   }
102
103   public Object JavaDoc put (Object JavaDoc key, int hash, Object JavaDoc value)
104   {
105     int index = hash & mask;
106     HashNode first = table[index];
107     HashNode node = first;
108     for (;;)
109       {
110     if (node == null)
111       {
112             if (++num_bindings >= table.length)
113               {
114                 rehash();
115                 index = hash & mask;
116                 first = table[index];
117               }
118             node = makeEntry(key, hash, value);
119             node.next = first;
120             table[index] = node;
121         return null;
122       }
123     else if (matches(key, hash, node))
124       {
125         return node.setValue(value);
126       }
127     node = node.next;
128       }
129   }
130
131   public Object JavaDoc remove (Object JavaDoc key)
132   {
133     int hash = hash(key);
134     int index = hash & this.mask;
135     HashNode prev = null;
136     HashNode node = table[index];
137     while (node != null)
138       {
139     HashNode next = node.next;
140     if (matches(key, hash, node))
141       {
142         if (prev == null)
143           table[index] = next;
144         else
145           prev.next = node;
146         num_bindings--;
147         return node.getValue();
148       }
149     prev = node;
150     node = next;
151       }
152     return null;
153   }
154
155   protected void rehash ()
156   {
157     HashNode[] oldTable = table;
158     int oldCapacity = oldTable.length;
159     int newCapacity = 2 * oldCapacity;
160     HashNode[] newTable = new HashNode[newCapacity];
161     int newMask = newCapacity - 1;
162     for (int i = oldCapacity; --i >= 0;)
163       {
164         HashNode chain = oldTable[i];
165         if (chain != null && chain.next != null)
166           {
167             // Reverse the old chain in place, so that after re-hashing the
168
// new chain has the same order.. This is useful for some
169
// subclasses (specifically gnu.expr.NameLookup), and it is
170
// cheap to so here where extra cache misses are unlikely.
171
HashNode prev = null;
172             do
173               {
174                 HashNode node = chain;
175                 chain = node.next;
176                 node.next = prev;
177                 prev = node;
178               }
179             while (chain != null);
180             chain = prev;
181           }
182
183     for (HashNode element = chain; element != null; )
184       {
185         HashNode next = element.next;
186         int hash = hash(element);
187         int j = hash & newMask;
188         HashNode head = newTable[j];
189         element.next = head;
190         newTable[j] = element;
191         element = next;
192       }
193       }
194     table = newTable;
195     mask = newMask;
196   }
197
198   public void clear ()
199   {
200     HashNode[] t = this.table;
201     for (int i = t.length; --i >= 0; )
202       t[i] = null;
203     num_bindings = 0;
204   }
205
206   public int size ()
207   {
208     return num_bindings;
209   }
210
211   protected static HashNode next (HashNode node)
212   {
213     return node.next;
214   }
215 }
216
Popular Tags