Java > Open Source Codes > org > apache > commons > collections > FastHashMap


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 package org.apache.commons.collections;
17
18 import java.util.Collection ;
19 import java.util.ConcurrentModificationException ;
20 import java.util.HashMap ;
21 import java.util.Iterator ;
22 import java.util.Map ;
23 import java.util.Set ;
24
25 /**
26  * <p>A customized implementation of <code>java.util.HashMap</code> designed
27  * to operate in a multithreaded environment where the large majority of
28  * method calls are read-only, instead of structural changes. When operating
29  * in "fast" mode, read calls are non-synchronized and write calls perform the
30  * following steps:</p>
31  * <ul>
32  * <li>Clone the existing collection
33  * <li>Perform the modification on the clone
34  * <li>Replace the existing collection with the (modified) clone
35  * </ul>
36  * <p>When first created, objects of this class default to "slow" mode, where
37  * all accesses of any type are synchronized but no cloning takes place. This
38  * is appropriate for initially populating the collection, followed by a switch
39  * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
40  * is complete.</p>
41  *
42  * <p><strong>NOTE</strong>: If you are creating and accessing a
43  * <code>HashMap</code> only within a single thread, you should use
44  * <code>java.util.HashMap</code> directly (with no synchronization), for
45  * maximum performance.</p>
46  *
47  * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
48  * Using it may cause unexpected failures on some architectures.</i>
49  * It suffers from the same problems as the double-checked locking idiom.
50  * In particular, the instruction that clones the internal collection and the
51  * instruction that sets the internal reference to the clone can be executed
52  * or perceived out-of-order. This means that any read operation might fail
53  * unexpectedly, as it may be reading the state of the internal collection
54  * before the internal collection is fully formed.
55  * For more information on the double-checked locking idiom, see the
56  * <a HREF="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
57  * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
58  *
59  * @since Commons Collections 1.0
60  * @version $Revision: 1.17 $ $Date: 2004/02/18 01:15:42 $
61  *
62  * @author Craig R. McClanahan
63  * @author Stephen Colebourne
64  */
65 public class FastHashMap extends HashMap {
66
67     /**
68      * The underlying map we are managing.
69      */
70     protected HashMap map = null;
71
72     /**
73      * Are we currently operating in "fast" mode?
74      */
75     protected boolean fast = false;
76
77     // Constructors
78 // ----------------------------------------------------------------------
79
80     /**
81      * Construct an empty map.
82      */
83     public FastHashMap() {
84         super();
85         this.map = new HashMap ();
86     }
87
88     /**
89      * Construct an empty map with the specified capacity.
90      *
91      * @param capacity the initial capacity of the empty map
92      */
93     public FastHashMap(int capacity) {
94         super();
95         this.map = new HashMap (capacity);
96     }
97
98     /**
99      * Construct an empty map with the specified capacity and load factor.
100      *
101      * @param capacity the initial capacity of the empty map
102      * @param factor the load factor of the new map
103      */
104     public FastHashMap(int capacity, float factor) {
105         super();
106         this.map = new HashMap (capacity, factor);
107     }
108
109     /**
110      * Construct a new map with the same mappings as the specified map.
111      *
112      * @param map the map whose mappings are to be copied
113      */
114     public FastHashMap(Map map) {
115         super();
116         this.map = new HashMap (map);
117     }
118
119
120     // Property access
121 // ----------------------------------------------------------------------
122
123     /**
124      * Returns true if this map is operating in fast mode.
125      *
126      * @return true if this map is operating in fast mode
127      */
128     public boolean getFast() {
129         return (this.fast);
130     }
131
132     /**
133      * Sets whether this map is operating in fast mode.
134      *
135      * @param fast true if this map should operate in fast mode
136      */
137     public void setFast(boolean fast) {
138         this.fast = fast;
139     }
140
141
142     // Map access
143 // ----------------------------------------------------------------------
144 // These methods can forward straight to the wrapped Map in 'fast' mode.
145 // (because they are query methods)
146
147     /**
148      * Return the value to which this map maps the specified key. Returns
149      * <code>null</code> if the map contains no mapping for this key, or if
150      * there is a mapping with a value of <code>null</code>. Use the
151      * <code>containsKey()</code> method to disambiguate these cases.
152      *
153      * @param key the key whose value is to be returned
154      * @return the value mapped to that key, or null
155      */
156     public Object get(Object key) {
157         if (fast) {
158             return (map.get(key));
159         } else {
160             synchronized (map) {
161                 return (map.get(key));
162             }
163         }
164     }
165
166     /**
167      * Return the number of key-value mappings in this map.
168      *
169      * @return the current size of the map
170      */
171     public int size() {
172         if (fast) {
173             return (map.size());
174         } else {
175             synchronized (map) {
176                 return (map.size());
177             }
178         }
179     }
180
181     /**
182      * Return <code>true</code> if this map contains no mappings.
183      *
184      * @return is the map currently empty
185      */
186     public boolean isEmpty() {
187         if (fast) {
188             return (map.isEmpty());
189         } else {
190             synchronized (map) {
191                 return (map.isEmpty());
192             }
193         }
194     }
195
196     /**
197      * Return <code>true</code> if this map contains a mapping for the
198      * specified key.
199      *
200      * @param key the key to be searched for
201      * @return true if the map contains the key
202      */
203     public boolean containsKey(Object key) {
204         if (fast) {
205             return (map.containsKey(key));
206         } else {
207             synchronized (map) {
208                 return (map.containsKey(key));
209             }
210         }
211     }
212
213     /**
214      * Return <code>true</code> if this map contains one or more keys mapping
215      * to the specified value.
216      *
217      * @param value the value to be searched for
218      * @return true if the map contains the value
219      */
220     public boolean containsValue(Object value) {
221         if (fast) {
222             return (map.containsValue(value));
223         } else {
224             synchronized (map) {
225                 return (map.containsValue(value));
226             }
227         }
228     }
229
230     // Map modification
231 // ----------------------------------------------------------------------
232 // These methods perform special behaviour in 'fast' mode.
233 // The map is cloned, updated and then assigned back.
234 // See the comments at the top as to why this won't always work.
235
236     /**
237      * Associate the specified value with the specified key in this map.
238      * If the map previously contained a mapping for this key, the old
239      * value is replaced and returned.
240      *
241      * @param key the key with which the value is to be associated
242      * @param value the value to be associated with this key
243      * @return the value previously mapped to the key, or null
244      */
245     public Object put(Object key, Object value) {
246         if (fast) {
247             synchronized (this) {
248                 HashMap temp = (HashMap ) map.clone();
249                 Object result = temp.put(key, value);
250                 map = temp;
251                 return (result);
252             }
253         } else {
254             synchronized (map) {
255                 return (map.put(key, value));
256             }
257         }
258     }
259
260     /**
261      * Copy all of the mappings from the specified map to this one, replacing
262      * any mappings with the same keys.
263      *
264      * @param in the map whose mappings are to be copied
265      */
266     public void putAll(Map in) {
267         if (fast) {
268             synchronized (this) {
269                 HashMap temp = (HashMap ) map.clone();
270                 temp.putAll(in);
271                 map = temp;
272             }
273         } else {
274             synchronized (map) {
275                 map.putAll(in);
276             }
277         }
278     }
279
280     /**
281      * Remove any mapping for this key, and return any previously
282      * mapped value.
283      *
284      * @param key the key whose mapping is to be removed
285      * @return the value removed, or null
286      */
287     public Object remove(Object key) {
288         if (fast) {
289             synchronized (this) {
290                 HashMap temp = (HashMap ) map.clone();
291                 Object result = temp.remove(key);
292                 map = temp;
293                 return (result);
294             }
295         } else {
296             synchronized (map) {
297                 return (map.remove(key));
298             }
299         }
300     }
301
302     /**
303      * Remove all mappings from this map.
304      */
305     public void clear() {
306         if (fast) {
307             synchronized (this) {
308                 map = new HashMap ();
309             }
310         } else {
311             synchronized (map) {
312                 map.clear();
313             }
314         }
315     }
316
317     // Basic object methods
318 // ----------------------------------------------------------------------
319
320     /**
321      * Compare the specified object with this list for equality. This
322      * implementation uses exactly the code that is used to define the
323      * list equals function in the documentation for the
324      * <code>Map.equals</code> method.
325      *
326      * @param o the object to be compared to this list
327      * @return true if the two maps are equal
328      */
329     public boolean equals(Object o) {
330         // Simple tests that require no synchronization
331 if (o == this) {
332             return (true);
333         } else if (!(o instanceof Map )) {
334             return (false);
335         }
336         Map mo = (Map ) o;
337
338         // Compare the two maps for equality
339 if (fast) {
340             if (mo.size() != map.size()) {
341                 return (false);
342             }
343             Iterator i = map.entrySet().iterator();
344             while (i.hasNext()) {
345                 Map.Entry e = (Map.Entry ) i.next();
346                 Object key = e.getKey();
347                 Object value = e.getValue();
348                 if (value == null) {
349                     if (!(mo.get(key) == null && mo.containsKey(key))) {
350                         return (false);
351                     }
352                 } else {
353                     if (!value.equals(mo.get(key))) {
354                         return (false);
355                     }
356                 }
357             }
358             return (true);
359             
360         } else {
361             synchronized (map) {
362                 if (mo.size() != map.size()) {
363                     return (false);
364                 }
365                 Iterator i = map.entrySet().iterator();
366                 while (i.hasNext()) {
367                     Map.Entry e = (Map.Entry ) i.next();
368                     Object key = e.getKey();
369                     Object value = e.getValue();
370                     if (value == null) {
371                         if (!(mo.get(key) == null && mo.containsKey(key))) {
372                             return (false);
373                         }
374                     } else {
375                         if (!value.equals(mo.get(key))) {
376                             return (false);
377                         }
378                     }
379                 }
380                 return (true);
381             }
382         }
383     }
384
385     /**
386      * Return the hash code value for this map. This implementation uses
387      * exactly the code that is used to define the list hash function in the
388      * documentation for the <code>Map.hashCode</code> method.
389      *
390      * @return suitable integer hash code
391      */
392     public int hashCode() {
393         if (fast) {
394             int h = 0;
395             Iterator i = map.entrySet().iterator();
396             while (i.hasNext()) {
397                 h += i.next().hashCode();
398             }
399             return (h);
400         } else {
401             synchronized (map) {
402                 int h = 0;
403                 Iterator i = map.entrySet().iterator();
404                 while (i.hasNext()) {
405                     h += i.next().hashCode();
406                 }
407                 return (h);
408             }
409         }
410     }
411
412     /**
413      * Return a shallow copy of this <code>FastHashMap</code> instance.
414      * The keys and values themselves are not copied.
415      *
416      * @return a clone of this map
417      */
418     public Object clone() {
419         FastHashMap results = null;
420         if (fast) {
421             results = new FastHashMap(map);
422         } else {
423             synchronized (map) {
424                 results = new FastHashMap(map);
425             }
426         }
427         results.setFast(getFast());
428         return (results);
429     }
430
431     // Map views
432 // ----------------------------------------------------------------------
433
434     /**
435      * Return a collection view of the mappings contained in this map. Each
436      * element in the returned collection is a <code>Map.Entry</code>.
437      */
438     public Set entrySet() {
439         return new EntrySet();
440     }
441
442     /**
443      * Return a set view of the keys contained in this map.
444      */
445     public Set keySet() {
446         return new KeySet();
447     }
448
449     /**
450      * Return a collection view of the values contained in this map.
451      */
452     public Collection values() {
453         return new Values();
454     }
455
456     // Map view inner classes
457 // ----------------------------------------------------------------------
458
459     /**
460      * Abstract collection implementation shared by keySet(), values() and entrySet().
461      */
462     private abstract class CollectionView implements Collection {
463
464         public CollectionView() {
465         }
466
467         protected abstract Collection get(Map map);
468         protected abstract Object iteratorNext(Map.Entry entry);
469
470
471         public void clear() {
472             if (fast) {
473                 synchronized (FastHashMap.this) {
474                     map = new HashMap ();
475                 }
476             } else {
477                 synchronized (map) {
478                     get(map).clear();
479                 }
480             }
481         }
482
483         public boolean remove(Object o) {
484             if (fast) {
485                 synchronized (FastHashMap.this) {
486                     HashMap temp = (HashMap ) map.clone();
487                     boolean r = get(temp).remove(o);
488                     map = temp;
489                     return r;
490                 }
491             } else {
492                 synchronized (map) {
493                     return get(map).remove(o);
494                 }
495             }
496         }
497
498         public boolean removeAll(Collection o) {
499             if (fast) {
500                 synchronized (FastHashMap.this) {
501                     HashMap temp = (HashMap ) map.clone();
502                     boolean r = get(temp).removeAll(o);
503                     map = temp;
504                     return r;
505                 }
506             } else {
507                 synchronized (map) {
508                     return get(map).removeAll(o);
509                 }
510             }
511         }
512
513         public boolean retainAll(Collection o) {
514             if (fast) {
515                 synchronized (FastHashMap.this) {
516                     HashMap temp = (HashMap ) map.clone();
517                     boolean r = get(temp).retainAll(o);
518                     map = temp;
519                     return r;
520                 }
521             } else {
522                 synchronized (map) {
523                     return get(map).retainAll(o);
524                 }
525             }
526         }
527
528         public int size() {
529             if (fast) {
530                 return get(map).size();
531             } else {
532                 synchronized (map) {
533                     return get(map).size();
534                 }
535             }
536         }
537
538
539         public boolean isEmpty() {
540             if (fast) {
541                 return get(map).isEmpty();
542             } else {
543                 synchronized (map) {
544                     return get(map).isEmpty();
545                 }
546             }
547         }
548
549         public boolean contains(Object o) {
550             if (fast) {
551                 return get(map).contains(o);
552             } else {
553                 synchronized (map) {
554                     return get(map).contains(o);
555                 }
556             }
557         }
558
559         public boolean containsAll(Collection o) {
560             if (fast) {
561                 return get(map).containsAll(o);
562             } else {
563                 synchronized (map) {
564                     return get(map).containsAll(o);
565                 }
566             }
567         }
568
569         public Object [] toArray(Object [] o) {
570             if (fast) {
571                 return get(map).toArray(o);
572             } else {
573                 synchronized (map) {
574                     return get(map).toArray(o);
575                 }
576             }
577         }
578
579         public Object [] toArray() {
580             if (fast) {
581                 return get(map).toArray();
582             } else {
583                 synchronized (map) {
584                     return get(map).toArray();
585                 }
586             }
587         }
588
589
590         public boolean equals(Object o) {
591             if (o == this) return true;
592             if (fast) {
593                 return get(map).equals(o);
594             } else {
595                 synchronized (map) {
596                     return get(map).equals(o);
597                 }
598             }
599         }
600
601         public int hashCode() {
602             if (fast) {
603                 return get(map).hashCode();
604             } else {
605                 synchronized (map) {
606                     return get(map).hashCode();
607                 }
608             }
609         }
610
611         public boolean add(Object o) {
612             throw new UnsupportedOperationException ();
613         }
614
615         public boolean addAll(Collection c) {
616             throw new UnsupportedOperationException ();
617         }
618
619         public Iterator iterator() {
620             return new CollectionViewIterator();
621         }
622
623         private class CollectionViewIterator implements Iterator {
624
625             private Map expected;
626             private Map.Entry lastReturned = null;
627             private Iterator iterator;
628
629             public CollectionViewIterator() {
630                 this.expected = map;
631                 this.iterator = expected.entrySet().iterator();
632             }
633  
634             public boolean hasNext() {
635                 if (expected != map) {
636                     throw new ConcurrentModificationException ();
637                 }
638                 return iterator.hasNext();
639             }
640
641             public Object next() {
642                 if (expected != map) {
643                     throw new ConcurrentModificationException ();
644                 }
645                 lastReturned = (Map.Entry )iterator.next();
646                 return iteratorNext(lastReturned);
647             }
648
649             public void remove() {
650                 if (lastReturned == null) {
651                     throw new IllegalStateException ();
652                 }
653                 if (fast) {
654                     synchronized (FastHashMap.this) {
655                         if (expected != map) {
656                             throw new ConcurrentModificationException ();
657                         }
658                         FastHashMap.this.remove(lastReturned.getKey());
659                         lastReturned = null;
660                         expected = map;
661                     }
662                 } else {
663                     iterator.remove();
664                     lastReturned = null;
665                 }
666             }
667         }
668     }
669
670     /**
671      * Set implementation over the keys of the FastHashMap
672      */
673     private class KeySet extends CollectionView implements Set {
674     
675         protected Collection get(Map map) {
676             return map.keySet();
677         }
678     
679         protected Object iteratorNext(Map.Entry entry) {
680             return entry.getKey();
681         }
682     
683     }
684     
685     /**
686      * Collection implementation over the values of the FastHashMap
687      */
688     private class Values extends CollectionView {
689     
690         protected Collection get(Map map) {
691             return map.values();
692         }
693     
694         protected Object iteratorNext(Map.Entry entry) {
695             return entry.getValue();
696         }
697     }
698     
699     /**
700      * Set implementation over the entries of the FastHashMap
701      */
702     private class EntrySet extends CollectionView implements Set {
703     
704         protected Collection get(Map map) {
705             return map.entrySet();
706         }
707     
708         protected Object iteratorNext(Map.Entry entry) {
709             return entry;
710         }
711     
712     }
713
714 }
715

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags