Hashtable


1   /*
2    * Copyright 2001-2004 The Apache Software Foundation.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *     http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  /*
17   * $Id: Hashtable.java,v 1.4 2004/02/16 22:55:54 minchau Exp $
18   */
19  
20  package org.apache.xalan.xsltc.runtime;
21  
22  import java.util.Enumeration  ;
23  
24  /**
25   * IMPORTANT NOTE:
26   * This code was taken from Sun's Java1.1 JDK java.util.HashTable.java
27   * All "synchronized" keywords and some methods we do not need have been 
28   * all been removed.
29   */
30  
31  /**
32   * Object that wraps entries in the hash-table
33   * @author Morten Jorgensen
34   */
35  class HashtableEntry {
36      int hash;
37      Object   key;
38      Object   value;
39      HashtableEntry next;
40  
41      protected Object   clone() {
42      HashtableEntry entry = new HashtableEntry();
43      entry.hash = hash;
44      entry.key = key;
45      entry.value = value;
46      entry.next = (next != null) ? (HashtableEntry)next.clone() : null;
47      return entry;
48      }
49  }
50  
51  /**
52   * The main hash-table implementation
53   */
54  public class Hashtable {
55  
56      private transient HashtableEntry table[]; // hash-table entries
57      private transient int count;              // number of entries
58      private int threshold;                    // current size of hash-tabke
59      private float loadFactor;                 // load factor
60  
61      /**
62       * Constructs a new, empty hashtable with the specified initial 
63       * capacity and the specified load factor. 
64       */
65      public Hashtable(int initialCapacity, float loadFactor) {
66      if (initialCapacity <= 0) initialCapacity = 11;
67      if (loadFactor <= 0.0) loadFactor = 0.75f;
68      this.loadFactor = loadFactor;
69      table = new HashtableEntry[initialCapacity];
70      threshold = (int)(initialCapacity * loadFactor);
71      }
72  
73      /**
74       * Constructs a new, empty hashtable with the specified initial capacity
75       * and default load factor.
76       */
77      public Hashtable(int initialCapacity) {
78      this(initialCapacity, 0.75f);
79      }
80  
81      /**
82       * Constructs a new, empty hashtable with a default capacity and load
83       * factor. 
84       */
85      public Hashtable() {
86      this(101, 0.75f);
87      }
88  
89      /**
90       * Returns the number of keys in this hashtable.
91       */
92      public int size() {
93      return count;
94      }
95  
96      /**
97       * Tests if this hashtable maps no keys to values.
98       */
99      public boolean isEmpty() {
100     return count == 0;
101     }
102 
103     /**
104      * Returns an enumeration of the keys in this hashtable.
105      */
106     public Enumeration   keys() {
107     return new HashtableEnumerator(table, true);
108     }
109 
110     /**
111      * Returns an enumeration of the values in this hashtable.
112      * Use the Enumeration methods on the returned object to fetch the elements
113      * sequentially.
114      */
115     public Enumeration   elements() {
116     return new HashtableEnumerator(table, false);
117     }
118 
119     /**
120      * Tests if some key maps into the specified value in this hashtable.
121      * This operation is more expensive than the <code>containsKey</code>
122      * method.
123      */
124     public boolean contains(Object   value) {
125 
126     if (value == null) throw new NullPointerException  ();
127 
128     int i;
129     HashtableEntry e;
130     HashtableEntry tab[] = table;
131 
132     for (i = tab.length ; i-- > 0 ;) {
133         for (e = tab[i] ; e != null ; e = e.next) {
134         if (e.value.equals(value)) {
135             return true;
136         }
137         }
138     }
139     return false;
140     }
141 
142     /**
143      * Tests if the specified object is a key in this hashtable.
144      */
145     public boolean containsKey(Object   key) {
146     HashtableEntry e;
147     HashtableEntry tab[] = table;
148     int hash = key.hashCode();
149     int index = (hash & 0x7FFFFFFF) % tab.length;
150 
151     for (e = tab[index] ; e != null ; e = e.next)
152         if ((e.hash == hash) && e.key.equals(key))
153         return true;
154 
155     return false;
156     }
157 
158     /**
159      * Returns the value to which the specified key is mapped in this hashtable.
160      */
161     public Object   get(Object   key) {
162     HashtableEntry e;
163     HashtableEntry tab[] = table;
164     int hash = key.hashCode();
165     int index = (hash & 0x7FFFFFFF) % tab.length;
166 
167     for (e = tab[index] ; e != null ; e = e.next) 
168         if ((e.hash == hash) && e.key.equals(key)) 
169         return e.value;
170 
171     return null;
172     }
173 
174     /**
175      * Rehashes the contents of the hashtable into a hashtable with a 
176      * larger capacity. This method is called automatically when the 
177      * number of keys in the hashtable exceeds this hashtable's capacity 
178      * and load factor. 
179      */
180     protected void rehash() {
181     HashtableEntry e, old;
182     int i, index;
183     int oldCapacity = table.length;
184     HashtableEntry oldTable[] = table;
185 
186     int newCapacity = oldCapacity * 2 + 1;
187     HashtableEntry newTable[] = new HashtableEntry[newCapacity];
188 
189     threshold = (int)(newCapacity * loadFactor);
190     table = newTable;
191 
192     for (i = oldCapacity ; i-- > 0 ;) {
193         for (old = oldTable[i] ; old != null ; ) {
194         e = old;
195         old = old.next;
196         index = (e.hash & 0x7FFFFFFF) % newCapacity;
197         e.next = newTable[index];
198         newTable[index] = e;
199         }
200     }
201     }
202 
203     /**
204      * Maps the specified <code>key</code> to the specified 
205      * <code>value</code> in this hashtable. Neither the key nor the 
206      * value can be <code>null</code>. 
207      * <p>
208      * The value can be retrieved by calling the <code>get</code> method 
209      * with a key that is equal to the original key. 
210      */
211     public Object   put(Object   key, Object   value) {
212     // Make sure the value is not null
213     if (value == null) throw new NullPointerException  ();
214 
215     // Makes sure the key is not already in the hashtable.
216     HashtableEntry e;
217     HashtableEntry tab[] = table;
218     int hash = key.hashCode();
219     int index = (hash & 0x7FFFFFFF) % tab.length;
220 
221     for (e = tab[index] ; e != null ; e = e.next) {
222         if ((e.hash == hash) && e.key.equals(key)) {
223         Object   old = e.value;
224         e.value = value;
225         return old;
226         }
227     }
228 
229     // Rehash the table if the threshold is exceeded
230     if (count >= threshold) {
231         rehash();
232         return put(key, value);
233     } 
234 
235     // Creates the new entry.
236     e = new HashtableEntry();
237     e.hash = hash;
238     e.key = key;
239     e.value = value;
240     e.next = tab[index];
241     tab[index] = e;
242     count++;
243     return null;
244     }
245 
246     /**
247      * Removes the key (and its corresponding value) from this 
248      * hashtable. This method does nothing if the key is not in the hashtable.
249      */
250     public Object   remove(Object   key) {
251     HashtableEntry e, prev;
252     HashtableEntry tab[] = table;
253     int hash = key.hashCode();
254     int index = (hash & 0x7FFFFFFF) % tab.length;
255     for (e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
256         if ((e.hash == hash) && e.key.equals(key)) {
257         if (prev != null)
258             prev.next = e.next;
259         else
260             tab[index] = e.next;
261         count--;
262         return e.value;
263         }
264     }
265     return null;
266     }
267 
268     /**
269      * Clears this hashtable so that it contains no keys. 
270      */
271     public void clear() {
272     HashtableEntry tab[] = table;
273     for (int index = tab.length; --index >= 0; )
274         tab[index] = null;
275     count = 0;
276     }
277 
278     /**
279      * Returns a rather long string representation of this hashtable.
280      * Handy for debugging - leave it here!!!
281      */
282     public String   toString() {
283     int i;
284     int max = size() - 1;
285     StringBuffer   buf = new StringBuffer  ();
286     Enumeration   k = keys();
287     Enumeration   e = elements();
288     buf.append("{");
289 
290     for (i = 0; i <= max; i++) {
291         String   s1 = k.nextElement().toString();
292         String   s2 = e.nextElement().toString();
293         buf.append(s1 + "=" + s2);
294         if (i < max) buf.append(", ");
295     }
296     buf.append("}");
297     return buf.toString();
298     }
299 
300     /**
301      * A hashtable enumerator class.  This class should remain opaque 
302      * to the client. It will use the Enumeration interface.
303      */
304     class HashtableEnumerator implements Enumeration   {
305     boolean keys;
306     int index;
307     HashtableEntry table[];
308     HashtableEntry entry;
309 
310     HashtableEnumerator(HashtableEntry table[], boolean keys) {
311         this.table = table;
312         this.keys = keys;
313         this.index = table.length;
314     }
315     
316     public boolean hasMoreElements() {
317         if (entry != null) {
318         return true;
319         }
320         while (index-- > 0) {
321         if ((entry = table[index]) != null) {
322             return true;
323         }
324         }
325         return false;
326     }
327 
328     public Object   nextElement() {
329         if (entry == null) {
330         while ((index-- > 0) && ((entry = table[index]) == null));
331         }
332         if (entry != null) {
333         HashtableEntry e = entry;
334         entry = e.next;
335         return keys ? e.key : e.value;
336         }
337         return null;
338     }
339     }
340 
341 }
342
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags