HashMap


1   /*
2    * $Header: /home/cvs/jakarta-slide/src/share/org/apache/slide/util/HashMap.java,v 1.7 2004/07/28 09:34:29 ib Exp $
3    * $Revision: 1.7 $
4    * $Date: 2004/07/28 09:34:29 $
5    *
6    * ====================================================================
7    *
8    * Copyright 1999-2002 The Apache Software Foundation 
9    *
10   * Licensed under the Apache License, Version 2.0 (the "License");
11   * you may not use this file except in compliance with the License.
12   * You may obtain a copy of the License at
13   *
14   *     http://www.apache.org/licenses/LICENSE-2.0
15   *
16   * Unless required by applicable law or agreed to in writing, software
17   * distributed under the License is distributed on an "AS IS" BASIS,
18   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19   * See the License for the specific language governing permissions and
20   * limitations under the License.
21   *
22   */ 
23  
24  package org.apache.slide.util;
25  
26  
27  /**
28   * My implementation of a JDK 1.2 Map. I do not use synchronization,
29   * so be careful in a threaded environment. I also do not specifically
30   * "implements" java.util.Map, since support for JDK 1.1 is needed.
31   * 
32   * @version $Revision: 1.7 $ $Date: 2004/07/28 09:34:29 $
33  **/
34  public class HashMap {
35      
36      /**
37       * The default number of buckets in this Map
38      **/
39      public static final int DEFAULT_SIZE = 17;
40      
41      /**
42       * the list of names
43      **/
44      private Bucket[] table   = null;
45      
46      private int elementCount = 0;
47      
48      /**
49       * Creates a new HashMap with the default number of buckets
50      **/
51      public HashMap() {
52          this(HashMap.DEFAULT_SIZE);
53      } //-- HashMap
54  
55      /**
56       * Creates a new HashMap with the given number of buckets.
57       * @param size  the number of buckets to use, this value must
58       * be a non-zero positive integer, if not the default size will
59       * be used.
60       * <BR />
61       * <B>Note:</B>The number of buckets is not the same as the
62       * allocating space for a desired number of entries. If fact,
63       * if you know number of entries that will be in the hash, you
64       * might want to use a HashMap with a different implementation.
65       * This Map is implemented using separate chaining.
66      **/
67      public HashMap(int size) {
68          super();
69          // protect against illegal size
70          if (size <= 0) size = DEFAULT_SIZE;
71          //initialize table
72          table = new Bucket[size];
73          for (int i = 0; i < size; i++)
74              table[i] = new Bucket();
75              
76      } //-- Map
77      
78      /**
79       * Removes all entries from this Map
80      **/
81      public void clear() {
82          for (int i = 0; i < table.length; i++) {
83              table[i].size = 0;
84              table[i].entry = null;
85          }
86          elementCount = 0;
87      } //-- clear
88      
89      /**
90       * Returns true if the given object is a key contained in this Map
91       * @return true if the given object is a key contained in this Map
92      **/
93      public boolean containsKey(Object   key) {
94          if (elementCount == 0) return false;
95          else return (findEntry(key) != null);
96      } //-- containsKey
97  
98      /**
99       * Returns true if the given object is a value contained in this Map
100      *
101      * <BR />
102      * <B>Note:</B> Depending on the size of the Map, this could be a 
103      * slow operation. If you know the key an object would be associated with,
104      * contains key would be much faster, or simply do (get(key) != null).
105      *
106      * @return true if the given object is a value contained in this Map
107     **/
108     public boolean containsValue(Object   value) {
109         
110         if (elementCount == 0) return false;
111         
112         boolean nullValue = (value == null);
113         
114         for (int i = 0; i < table.length; i++) {
115             Entry entry = table[i].entry;
116             
117             while (entry != null) {                
118                 if (nullValue) {
119                     if (entry.getValue() == null) return true;
120                 }
121                 else {
122                     if (value.equals(entry.getValue())) return true;
123                 }
124                 entry = entry.next;
125             }
126         }
127         
128         return false;
129         
130     } //-- containsValue
131     
132     
133     /**
134      * Returns an interator for the entries of this Map. 
135      * Each element returned by a call to Iterator#next() is
136      * a Map.Entry.
137      * <BR />
138      * Note: This is different than a JDK 1.2 Map because
139      * I didn't want to deal with implementing Sets at this point.
140      * @return an Iterator for the entries of this Map.
141     **/
142     public Iterator entries() {
143         return new HashMapEntryIterator(table);
144     } //-- entries
145     
146     /**
147      * Returns true if the given Object is a HashMap which contains
148      * equivalent HashMap entries as this HashMap.
149      * @return true if the given Object is a HashMap, and is equivalent
150      * to this Map
151      * <BR />
152      * I will be probably make an interface for Map, to allow comparisons
153      * with different Map implemenations.
154     **/
155     public boolean equals(Object   object) {
156         
157         if (object == this) return true;
158         
159         if (object instanceof HashMap) {
160             HashMap map = (HashMap) object;
161             if (map.size() != size()) return false;
162             Iterator iter = map.entries();
163             while (iter.hasNext()) {
164                 Entry entry = (Entry)iter.next();
165                 if (!entry.equals(findEntry(entry.getKey())))
166                     return false;
167             }
168             return true;
169         }
170         return false;
171     } //-- equals
172     
173     /**
174      * Returns the value associated with the given key
175      * @return the value associated with the given key
176     **/
177     public Object   get(Object   key) {
178         Entry entry = findEntry(key);
179         if (entry != null) {
180             return entry.getValue();
181         }
182         return null;
183     } //-- get
184     
185     /**
186      * Returns the hashCode for this Map. The hash code is the
187      * sum of all the hash codes of each entry in the map
188     **/
189     public int hashCode() {
190         int value = 0;
191         for (int i = 0; i < table.length; i++) {
192             Entry entry = table[i].entry;
193             while (entry != null) {
194                 value += entry.hashCode();
195                 entry = entry.next;
196             }
197         }
198         return value;
199     } //-- hashCode
200     
201     /**
202      * Returns true if this map contains no entries
203      * @return true if this map contains no entries
204     **/
205     public boolean isEmpty() {
206         return (elementCount == 0);
207     } //-- isEmpty
208     
209     public Iterator keys() {
210         return new HashMapKeyIterator(table);
211     } //-- keys
212     
213     /**
214      * Associated the specified value with the given key in this Map
215      * @param key the object to associate with the given value
216      * @param value the object to add an association in this Map
217     **/
218     public void put(Object   key, Object   value) {
219         Entry entry = findEntry(key);
220         if (entry == null) 
221             addEntry(key, value);
222         else 
223             entry.setValue(value);
224     } //-- put
225     
226     /** 
227      * Removes the association with the given Key in the Map.
228      * @param key the object key to remove the association for
229      * @return the associated value being removed from this Map
230     **/
231     public Object   remove(Object   key) {
232         
233         if (elementCount == 0) return null;
234         
235         int hash = hashCode(key);
236         
237         Bucket bucket = table[hash % table.length];
238         
239         Entry entry = bucket.entry;
240         
241         boolean nullKey = (key == null);
242         
243         while (entry != null) {
244             
245             if (nullKey) {
246                 if (entry.getKey() == null) break; //-- found
247             }
248             else if (hash < entry.hash)
249                 return null; //-- not in list
250             else {
251                 if (entry.getKey().equals(key)) break; //-- found
252             }
253             entry = entry.next;
254         }
255         
256         Object   value = null;
257         
258         if (entry != null) {
259             
260             if (entry.prev != null)
261                 entry.prev.next = entry.next;
262             else
263                 bucket.entry = entry.next;
264                 
265             if (entry.next != null) 
266                 entry.next.prev = entry.prev;
267             
268             value = entry.getValue();
269             --bucket.size;
270             --elementCount;
271         }
272         
273         return value;
274     } //-- remove
275     
276     /**
277      * Returns the number of associations in the Map
278      * @return the number of associations in the Map
279     **/
280     public int size() {
281         return elementCount;
282     } //-- size
283     
284     //-------------------/
285     //- Private Methods -/
286     //-------------------/
287     
288     private int hashCode(Object   key) {
289         int hash = (key == null) ? 0 : key.hashCode();
290         if (hash < 0) hash = -hash;
291         return hash;
292     } //-- hashCode(Object)
293     
294     /**
295      * Creates a new Entry for the given mapping and adds it
296      * to this Map
297      * @param key the key to associate with the given value
298      * @param value the object to add an association for in this Map
299     **/
300     private void addEntry(Object   key, Object   value) {
301         
302         // compute hash
303         int hash = hashCode(key);
304         
305         Entry newEntry = new Entry(hash, key, value);
306         
307         Bucket bucket = table[hash % table.length];
308         
309         if (bucket.entry == null) bucket.entry = newEntry;
310         else {
311             //-- entries are ordered for faster retrieval
312             Entry current = bucket.entry;
313             while (current != null) {
314                 if (hash <= current.hash) {                    
315                     //-- insert new entry
316                     if (current.prev != null) {                        
317                         //-- current.prev<->newEntry
318                         current.prev.next = newEntry;
319                         newEntry.prev = current.prev;
320                     }
321                     // bucket.entry->newEntry
322                     else bucket.entry = newEntry;
323                     //--newEntry->current
324                     newEntry.next = current;
325                     break;
326                 }
327                 else if (current.next == null) {
328                     //-- add entry to end of list
329                     //-- current<->newEntry->null
330                     current.next = newEntry;
331                     newEntry.prev = current;
332                     break;
333                 }
334                 current = current.next;
335             }
336         }
337         
338         ++bucket.size;
339         ++elementCount;
340     } //-- addEntry
341     
342     /**
343      * Finds the Map entry associated with the given Key
344      * @return the desired Map.Entry, or null if not found
345     **/
346     private Entry findEntry(Object   key) {
347         if (elementCount == 0) return null;
348         return findEntry(key, hashCode(key));
349     } //-- findEntry
350 
351     /**
352      * Finds the Map entry associated with the given Key
353      * @param key the key to search for
354      * @param hash the pre-computed hashCode of the given key
355      * @return the desired Map.Entry, or null if not found
356     **/
357     private Entry findEntry(Object   key, int hash) {
358         
359         if (elementCount == 0) return null;
360         
361         int index = hash % table.length;
362         
363         Entry entry = table[index].entry;
364         
365         boolean nullKey = (key == null);
366         
367         while (entry != null) {
368             
369             if (nullKey) {
370                 if (entry.getKey() == null) 
371                     return entry;
372             }
373             else if (hash == entry.hash) {
374                 if (entry.getKey().equals(key))
375                     return entry;
376             }
377             else if (hash < entry.hash) break; //-- not in list
378             
379             entry = entry.next;
380         }
381         
382         return null;
383     } //-- findEntry
384     
385     
386     //-----------------/
387     //- Inner classes -/
388     //-----------------/
389     
390     /**
391      * The Entry bucket used by this Map implementation
392     **/
393     class Bucket {
394         int size = 0;
395         Entry entry = null;
396     } //-- Bucket
397     
398     /**
399      * An object representing an entry in the Map table
400     **/
401     class Entry {
402         
403         int hash = 0;
404         
405         Object   key   = null;
406         Object   value = null;
407         
408         Entry next = null;
409         Entry prev = null;
410         
411         public Entry(int hashCode, Object   key, Object   value) {
412             this.hash = hashCode;
413             this.key = key;
414             this.value = value;
415         } //-- Entry
416         
417         public Object   getKey() {
418             return key;
419         } //-- getKey
420         
421         public Object   getValue() {
422             return value;
423         } //-- getValue
424         
425         public boolean equals(Object   object) {
426             
427             if (object == null) return false;
428             
429             if (object instanceof Entry) {
430                 
431                 Entry entry = (Entry) object;
432                 
433                 if (this.key == null)
434                     if (entry.getKey() != null) 
435                         return false;
436                 else
437                     if (!this.key.equals(entry.getKey())) 
438                         return false;
439                
440                 if (this.value == null)
441                     return (entry.getValue() == null);
442                 else 
443                     return (this.value.equals(entry.getValue()));
444             }
445             
446             return false;
447         } //-- equals
448         
449         public int hashCode() {
450             int keyHash = (key == null) ? 0 : key.hashCode();
451             int valHash = (value == null) ? 0 : value.hashCode();
452             return (keyHash ^ valHash);
453         } //-- hashCode
454         
455         public void setValue(Object   value) {
456             this.value = value;
457         } //-- setValue
458     } //-- Entry
459     
460 } //-- Map
461 
462 class HashMapEntryIterator implements Iterator {
463     
464     HashMap.Bucket[] table = null;
465     private int index = 0;
466     private HashMap.Entry current = null;
467     private HashMap.Entry next = null;
468     
469     HashMapEntryIterator(HashMap.Bucket[] table) {
470         
471         System.out.println("<HashMapEntryIterator>");
472         this.table = table;
473         //-- find first
474         while (index < table.length) {
475             next = table[index].entry;
476             if (next != null) break;
477             ++index;
478         }
479         
480         System.out.println("</HashMapEntryIterator>");
481     } //-- HashMapEntryIterator
482     
483     public boolean hasNext() {
484         return (next != null);
485     } //-- hasNext
486     
487     public Object   next() {
488         current = next;        
489         if (next == null) return null;
490         next = next.next;
491         if (next == null) {
492             //-- find next non empty bucket
493             while (++index < table.length) {
494                 next = table[index].entry;
495                 if (next != null) break;
496             }
497         }
498         return current;
499     } //-- next
500     
501     public Object   remove() {
502         //-- Not Yet Implemented
503         throw new IllegalStateException  ("#remove() is not yet implemented");
504     } //-- remove
505     
506 } //-- HashMapEntryIterator
507 
508 class HashMapKeyIterator extends HashMapEntryIterator {
509     
510     HashMapKeyIterator(HashMap.Bucket[] table) {
511         super(table);
512     } //-- HashMapKeyIterator
513     
514     public Object   next() {
515         HashMap.Entry entry = (HashMap.Entry)super.next();
516         if (entry != null) return entry.getKey();
517         return null;
518     } //-- next
519     
520 } // HashMapKeyIterator
521
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags