SimpleHashtable


1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one or more
3    *  contributor license agreements.  See the NOTICE file distributed with
4    *  this work for additional information regarding copyright ownership.
5    *  The ASF licenses this file to You under the Apache License, Version 2.0
6    *  (the "License"); you may not use this file except in compliance with
7    *  the License.  You may obtain a copy of the License at
8    *
9    *      http://www.apache.org/licenses/LICENSE-2.0
10   *
11   *  Unless required by applicable law or agreed to in writing, software
12   *  distributed under the License is distributed on an "AS IS" BASIS,
13   *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   *  See the License for the specific language governing permissions and
15   *  limitations under the License.
16   */
17  
18  package org.apache.tomcat.util.collections;
19  
20  import java.util.Enumeration  ;
21  
22  /* **************************************** Stolen from Crimson ******************** */
23  /* From Crimson/Parser - in a perfect world we'll just have a common set of
24     utilities, and all apache project will just use those.
25  
26  */
27  
28  // can't be replaced using a Java 2 "Collections" API
29  // since this package must also run on JDK 1.1
30  
31  
32  /**
33   * This class implements a special purpose hashtable.  It works like a
34   * normal <code>java.util.Hashtable</code> except that: <OL>
35   *
36   *  <LI> Keys to "get" are strings which are known to be interned,
37   *  so that "==" is used instead of "String.equals".  (Interning
38   *  could be document-relative instead of global.)
39   *
40   *  <LI> It's not synchronized, since it's to be used only by
41   *  one thread at a time.
42   *
43   *  <LI> The keys () enumerator allocates no memory, with live
44   *  updates to the data disallowed.
45   *
46   *  <LI> It's got fewer bells and whistles:  fixed threshold and
47   *  load factor, no JDK 1.2 collection support, only keys can be
48   *  enumerated, things can't be removed, simpler inheritance; more.
49   *
50   *  </OL>
51   *
52   * <P> The overall result is that it's less expensive to use these in
53   * performance-critical locations, in terms both of CPU and memory,
54   * than <code>java.util.Hashtable</code> instances.  In this package
55   * it makes a significant difference when normalizing attributes,
56   * which is done for each start-element construct.
57   *
58   */
59  public final class SimpleHashtable implements Enumeration  
60  {
61      
62      private static org.apache.commons.logging.Log log=
63          org.apache.commons.logging.LogFactory.getLog( SimpleHashtable.class );
64      
65      // entries ...
66      private Entry       table[];
67  
68      // currently enumerated key
69      private Entry       current = null;
70      private int         currentBucket = 0;
71  
72      // number of elements in hashtable
73      private int         count;
74      private int         threshold;
75  
76      private static final float  loadFactor = 0.75f;
77  
78  
79      /**
80       * Constructs a new, empty hashtable with the specified initial 
81       * capacity.
82       *
83       * @param      initialCapacity   the initial capacity of the hashtable.
84       */
85      public SimpleHashtable(int initialCapacity) {
86      if (initialCapacity < 0)
87          throw new IllegalArgumentException  ("Illegal Capacity: "+
88                                                 initialCapacity);
89          if (initialCapacity==0)
90              initialCapacity = 1;
91      table = new Entry[initialCapacity];
92      threshold = (int)(initialCapacity * loadFactor);
93      }
94  
95      /**
96       * Constructs a new, empty hashtable with a default capacity.
97       */
98      public SimpleHashtable() {
99      this(11);
100     }
101 
102     /**
103      */
104     public void clear ()
105     {
106     count = 0;
107     currentBucket = 0;
108     current = null;
109     for (int i = 0; i < table.length; i++)
110         table [i] = null;
111     }
112 
113     /**
114      * Returns the number of keys in this hashtable.
115      *
116      * @return  the number of keys in this hashtable.
117      */
118     public int size() {
119     return count;
120     }
121 
122     /**
123      * Returns an enumeration of the keys in this hashtable.
124      *
125      * @return  an enumeration of the keys in this hashtable.
126      * @see     Enumeration
127      */
128     public Enumeration   keys() {
129     currentBucket = 0;
130     current = null;
131     hasMoreElements();
132     return this;
133     }
134 
135     /**
136      * Used to view this as an enumeration; returns true if there
137      * are more keys to be enumerated.
138      */
139     public boolean hasMoreElements ()
140     {
141     if (current != null)
142         return true;
143     while (currentBucket < table.length) {
144         current = table [currentBucket++];
145         if (current != null)
146         return true;
147     }
148     return false;
149     }
150 
151     /**
152      * Used to view this as an enumeration; returns the next key
153      * in the enumeration.
154      */
155     public Object   nextElement ()
156     {
157     Object   retval;
158 
159     if (current == null)
160         throw new IllegalStateException   ();
161     retval = current.key;
162     current = current.next;
163     // Advance to the next position ( we may call next after next,
164     // without hasMore )
165     hasMoreElements();
166     return retval;
167     }
168 
169 
170     /**
171      * Returns the value to which the specified key is mapped in this hashtable.
172      */
173     public Object   getInterned (String   key) {
174     Entry tab[] = table;
175     int hash = key.hashCode();
176     int index = (hash & 0x7FFFFFFF) % tab.length;
177     for (Entry e = tab[index] ; e != null ; e = e.next) {
178         if ((e.hash == hash) && (e.key == key))
179         return e.value;
180     }
181     return null;
182     }
183 
184     /**
185      * Returns the value to which the specified key is mapped in this
186      * hashtable ... the key isn't necessarily interned, though.
187      */
188     public Object   get(String   key) {
189     Entry tab[] = table;
190     int hash = key.hashCode();
191     int index = (hash & 0x7FFFFFFF) % tab.length;
192     for (Entry e = tab[index] ; e != null ; e = e.next) {
193         if ((e.hash == hash) && e.key.equals(key))
194         return e.value;
195     }
196     return null;
197     }
198 
199     /**
200      * Increases the capacity of and internally reorganizes this 
201      * hashtable, in order to accommodate and access its entries more 
202      * efficiently.  This method is called automatically when the 
203      * number of keys in the hashtable exceeds this hashtable's capacity 
204      * and load factor. 
205      */
206     private void rehash() {
207     int oldCapacity = table.length;
208     Entry oldMap[] = table;
209 
210     int newCapacity = oldCapacity * 2 + 1;
211     Entry newMap[] = new Entry[newCapacity];
212 
213     threshold = (int)(newCapacity * loadFactor);
214     table = newMap;
215 
216     /*
217     System.out.pr intln("rehash old=" + oldCapacity
218         + ", new=" + newCapacity
219         + ", thresh=" + threshold
220         + ", count=" + count);
221     */
222 
223     for (int i = oldCapacity ; i-- > 0 ;) {
224         for (Entry old = oldMap[i] ; old != null ; ) {
225         Entry e = old;
226         old = old.next;
227 
228         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
229         e.next = newMap[index];
230         newMap[index] = e;
231         }
232     }
233     }
234 
235     /**
236      * Maps the specified <code>key</code> to the specified 
237      * <code>value</code> in this hashtable. Neither the key nor the 
238      * value can be <code>null</code>. 
239      *
240      * <P>The value can be retrieved by calling the <code>get</code> method 
241      * with a key that is equal to the original key. 
242      */
243     public Object   put(Object   key, Object   value) {
244     // Make sure the value is not null
245     if (value == null) {
246         throw new NullPointerException  ();
247     }
248 
249     // Makes sure the key is not already in the hashtable.
250     Entry tab[] = table;
251     int hash = key.hashCode();
252     int index = (hash & 0x7FFFFFFF) % tab.length;
253     for (Entry e = tab[index] ; e != null ; e = e.next) {
254         // if ((e.hash == hash) && e.key.equals(key)) {
255         if ((e.hash == hash) && (e.key == key)) {
256         Object   old = e.value;
257         e.value = value;
258         return old;
259         }
260     }
261 
262     if (count >= threshold) {
263         // Rehash the table if the threshold is exceeded
264         rehash();
265 
266             tab = table;
267             index = (hash & 0x7FFFFFFF) % tab.length;
268     } 
269 
270     // Creates the new entry.
271     Entry e = new Entry(hash, key, value, tab[index]);
272     tab[index] = e;
273     count++;
274     return null;
275     }
276 
277     public Object   remove(Object   key) {
278     Entry tab[] = table;
279     Entry prev=null;
280     int hash = key.hashCode();
281     int index = (hash & 0x7FFFFFFF) % tab.length;
282     if( dL > 0 ) d("Idx " + index +  " " + tab[index] );
283     for (Entry e = tab[index] ; e != null ; prev=e, e = e.next) {
284         if( dL > 0 ) d("> " + prev + " " + e.next + " " + e + " " + e.key);
285         if ((e.hash == hash) && e.key.equals(key)) {
286         if( prev!=null ) {
287             prev.next=e.next;
288         } else {
289             tab[index]=e.next;
290         }
291         if( dL > 0 ) d("Removing from list " + tab[index] + " " + prev +
292                    " " + e.value);
293         count--;
294         Object   res=e.value;
295         e.value=null;
296         return res;
297         }
298     }
299     return null;
300     }
301 
302     /**
303      * Hashtable collision list.
304      */
305     private static class Entry {
306     int hash;
307     Object    key;
308     Object    value;
309     Entry   next;
310 
311     protected Entry(int hash, Object   key, Object   value, Entry next) {
312         this.hash = hash;
313         this.key = key;
314         this.value = value;
315         this.next = next;
316     }
317     }
318 
319     private static final int dL=0;
320     private void d(String   s ) {
321     if (log.isDebugEnabled())
322             log.debug( "SimpleHashtable: " + s );
323     }
324 }
325
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags