IntHashMap


1   /*
2    * Copyright 2002-2005 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  /*
18   * Note: originally released under the GNU LGPL v2.1, 
19   * but rereleased by the original author under the ASF license (above).
20   */
21  package org.apache.commons.lang;
22  
23  /**
24   * <p>A hash map that uses primitive ints for the key rather than objects.</p>
25   *
26   * <p>Note that this class is for internal optimization purposes only, and may
27   * not be supported in future releases of Jakarta Commons Lang.  Utilities of
28   * this sort may be included in future releases of Jakarta Commons Collections.</p>
29   *
30   * @author Justin Couch
31   * @author Alex Chaffee (alex@apache.org)
32   * @author Stephen Colebourne
33   * @since 2.0
34   * @version $Revision: 161243 $
35   * @see java.util.HashMap
36   */
37  class IntHashMap {
38  
39      /**
40       * The hash table data.
41       */
42      private transient Entry table[];
43  
44      /**
45       * The total number of entries in the hash table.
46       */
47      private transient int count;
48  
49      /**
50       * The table is rehashed when its size exceeds this threshold.  (The
51       * value of this field is (int)(capacity * loadFactor).)
52       *
53       * @serial
54       */
55      private int threshold;
56  
57      /**
58       * The load factor for the hashtable.
59       *
60       * @serial
61       */
62      private float loadFactor;
63  
64      /**
65       * <p>Innerclass that acts as a datastructure to create a new entry in the
66       * table.</p>
67       */
68      private static class Entry {
69          int hash;
70          int key;
71          Object   value;
72          Entry next;
73  
74          /**
75           * <p>Create a new entry with the given values.</p>
76           *
77           * @param hash The code used to hash the object with
78           * @param key The key used to enter this in the table
79           * @param value The value for this key
80           * @param next A reference to the next entry in the table
81           */
82          protected Entry(int hash, int key, Object   value, Entry next) {
83              this.hash = hash;
84              this.key = key;
85              this.value = value;
86              this.next = next;
87          }
88      }
89  
90      /**
91       * <p>Constructs a new, empty hashtable with a default capacity and load
92       * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
93       */
94      public IntHashMap() {
95          this(20, 0.75f);
96      }
97  
98      /**
99       * <p>Constructs a new, empty hashtable with the specified initial capacity
100      * and default load factor, which is <code>0.75</code>.</p>
101      *
102      * @param  initialCapacity the initial capacity of the hashtable.
103      * @throws IllegalArgumentException if the initial capacity is less
104      *   than zero.
105      */
106     public IntHashMap(int initialCapacity) {
107         this(initialCapacity, 0.75f);
108     }
109 
110     /**
111      * <p>Constructs a new, empty hashtable with the specified initial
112      * capacity and the specified load factor.</p>
113      *
114      * @param initialCapacity the initial capacity of the hashtable.
115      * @param loadFactor the load factor of the hashtable.
116      * @throws IllegalArgumentException  if the initial capacity is less
117      *             than zero, or if the load factor is nonpositive.
118      */
119     public IntHashMap(int initialCapacity, float loadFactor) {
120         super();
121         if (initialCapacity < 0) {
122             throw new IllegalArgumentException  ("Illegal Capacity: " + initialCapacity);
123         }
124         if (loadFactor <= 0) {
125             throw new IllegalArgumentException  ("Illegal Load: " + loadFactor);
126         }
127         if (initialCapacity == 0) {
128             initialCapacity = 1;
129         }
130 
131         this.loadFactor = loadFactor;
132         table = new Entry[initialCapacity];
133         threshold = (int) (initialCapacity * loadFactor);
134     }
135 
136     /**
137      * <p>Returns the number of keys in this hashtable.</p>
138      *
139      * @return  the number of keys in this hashtable.
140      */
141     public int size() {
142         return count;
143     }
144 
145     /**
146      * <p>Tests if this hashtable maps no keys to values.</p>
147      *
148      * @return  <code>true</code> if this hashtable maps no keys to values;
149      *          <code>false</code> otherwise.
150      */
151     public boolean isEmpty() {
152         return count == 0;
153     }
154 
155     /**
156      * <p>Tests if some key maps into the specified value in this hashtable.
157      * This operation is more expensive than the <code>containsKey</code>
158      * method.</p>
159      *
160      * <p>Note that this method is identical in functionality to containsValue,
161      * (which is part of the Map interface in the collections framework).</p>
162      *
163      * @param      value   a value to search for.
164      * @return     <code>true</code> if and only if some key maps to the
165      *             <code>value</code> argument in this hashtable as
166      *             determined by the <tt>equals</tt> method;
167      *             <code>false</code> otherwise.
168      * @throws  NullPointerException  if the value is <code>null</code>.
169      * @see        #containsKey(int)
170      * @see        #containsValue(Object)
171      * @see        java.util.Map
172      */
173     public boolean contains(Object   value) {
174         if (value == null) {
175             throw new NullPointerException  ();
176         }
177 
178         Entry tab[] = table;
179         for (int i = tab.length; i-- > 0;) {
180             for (Entry e = tab[i]; e != null; e = e.next) {
181                 if (e.value.equals(value)) {
182                     return true;
183                 }
184             }
185         }
186         return false;
187     }
188 
189     /**
190      * <p>Returns <code>true</code> if this HashMap maps one or more keys
191      * to this value.</p>
192      *
193      * <p>Note that this method is identical in functionality to contains
194      * (which predates the Map interface).</p>
195      *
196      * @param value value whose presence in this HashMap is to be tested.
197      * @return boolean <code>true</code> if the value is contained
198      * @see    java.util.Map
199      * @since JDK1.2
200      */
201     public boolean containsValue(Object   value) {
202         return contains(value);
203     }
204 
205     /**
206      * <p>Tests if the specified object is a key in this hashtable.</p>
207      *
208      * @param  key  possible key.
209      * @return <code>true</code> if and only if the specified object is a
210      *    key in this hashtable, as determined by the <tt>equals</tt>
211      *    method; <code>false</code> otherwise.
212      * @see #contains(Object)
213      */
214     public boolean containsKey(int key) {
215         Entry tab[] = table;
216         int hash = key;
217         int index = (hash & 0x7FFFFFFF) % tab.length;
218         for (Entry e = tab[index]; e != null; e = e.next) {
219             if (e.hash == hash) {
220                 return true;
221             }
222         }
223         return false;
224     }
225 
226     /**
227      * <p>Returns the value to which the specified key is mapped in this map.</p>
228      *
229      * @param   key   a key in the hashtable.
230      * @return  the value to which the key is mapped in this hashtable;
231      *          <code>null</code> if the key is not mapped to any value in
232      *          this hashtable.
233      * @see     #put(int, Object)
234      */
235     public Object   get(int key) {
236         Entry tab[] = table;
237         int hash = key;
238         int index = (hash & 0x7FFFFFFF) % tab.length;
239         for (Entry e = tab[index]; e != null; e = e.next) {
240             if (e.hash == hash) {
241                 return e.value;
242             }
243         }
244         return null;
245     }
246 
247     /**
248      * <p>Increases the capacity of and internally reorganizes this
249      * hashtable, in order to accommodate and access its entries more
250      * efficiently.</p>
251      *
252      * <p>This method is called automatically when the number of keys
253      * in the hashtable exceeds this hashtable's capacity and load
254      * factor.</p>
255      */
256     protected void rehash() {
257         int oldCapacity = table.length;
258         Entry oldMap[] = table;
259 
260         int newCapacity = oldCapacity * 2 + 1;
261         Entry newMap[] = new Entry[newCapacity];
262 
263         threshold = (int) (newCapacity * loadFactor);
264         table = newMap;
265 
266         for (int i = oldCapacity; i-- > 0;) {
267             for (Entry old = oldMap[i]; old != null;) {
268                 Entry e = old;
269                 old = old.next;
270 
271                 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
272                 e.next = newMap[index];
273                 newMap[index] = e;
274             }
275         }
276     }
277 
278     /**
279      * <p>Maps the specified <code>key</code> to the specified
280      * <code>value</code> in this hashtable. The key cannot be
281      * <code>null</code>. </p>
282      *
283      * <p>The value can be retrieved by calling the <code>get</code> method
284      * with a key that is equal to the original key.</p>
285      *
286      * @param key     the hashtable key.
287      * @param value   the value.
288      * @return the previous value of the specified key in this hashtable,
289      *         or <code>null</code> if it did not have one.
290      * @throws  NullPointerException  if the key is <code>null</code>.
291      * @see     #get(int)
292      */
293     public Object   put(int key, Object   value) {
294         // Makes sure the key is not already in the hashtable.
295         Entry tab[] = table;
296         int hash = key;
297         int index = (hash & 0x7FFFFFFF) % tab.length;
298         for (Entry e = tab[index]; e != null; e = e.next) {
299             if (e.hash == hash) {
300                 Object   old = e.value;
301                 e.value = value;
302                 return old;
303             }
304         }
305 
306         if (count >= threshold) {
307             // Rehash the table if the threshold is exceeded
308             rehash();
309 
310             tab = table;
311             index = (hash & 0x7FFFFFFF) % tab.length;
312         }
313 
314         // Creates the new entry.
315         Entry e = new Entry(hash, key, value, tab[index]);
316         tab[index] = e;
317         count++;
318         return null;
319     }
320 
321     /**
322      * <p>Removes the key (and its corresponding value) from this
323      * hashtable.</p>
324      *
325      * <p>This method does nothing if the key is not present in the
326      * hashtable.</p>
327      *
328      * @param   key   the key that needs to be removed.
329      * @return  the value to which the key had been mapped in this hashtable,
330      *          or <code>null</code> if the key did not have a mapping.
331      */
332     public Object   remove(int key) {
333         Entry tab[] = table;
334         int hash = key;
335         int index = (hash & 0x7FFFFFFF) % tab.length;
336         for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
337             if (e.hash == hash) {
338                 if (prev != null) {
339                     prev.next = e.next;
340                 } else {
341                     tab[index] = e.next;
342                 }
343                 count--;
344                 Object   oldValue = e.value;
345                 e.value = null;
346                 return oldValue;
347             }
348         }
349         return null;
350     }
351 
352     /**
353      * <p>Clears this hashtable so that it contains no keys.</p>
354      */
355     public synchronized void clear() {
356         Entry tab[] = table;
357         for (int index = tab.length; --index >= 0;) {
358             tab[index] = null;
359         }
360         count = 0;
361     }
362     
363 }
364
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags