Java > Open Source Codes > org > apache > commons > collections > map > StaticBucketMap


1 /*
2  * Copyright 2002-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.map;
17
18 import java.util.AbstractCollection ;
19 import java.util.AbstractSet ;
20 import java.util.ArrayList ;
21 import java.util.Collection ;
22 import java.util.Iterator ;
23 import java.util.Map ;
24 import java.util.NoSuchElementException ;
25 import java.util.Set ;
26
27 import org.apache.commons.collections.KeyValue;
28
29 /**
30  * A StaticBucketMap is an efficient, thread-safe implementation of
31  * <code>java.util.Map</code> that performs well in in a highly
32  * thread-contentious environment. The map supports very efficient
33  * {@link #get(Object) get}, {@link #put(Object,Object) put},
34  * {@link #remove(Object) remove} and {@link #containsKey(Object) containsKey}
35  * operations, assuming (approximate) uniform hashing and
36  * that the number of entries does not exceed the number of buckets. If the
37  * number of entries exceeds the number of buckets or if the hash codes of the
38  * objects are not uniformly distributed, these operations have a worst case
39  * scenario that is proportional to the number of elements in the map
40  * (<i>O(n)</i>).<p>
41  *
42  * Each bucket in the hash table has its own monitor, so two threads can
43  * safely operate on the map at the same time, often without incurring any
44  * monitor contention. This means that you don't have to wrap instances
45  * of this class with {@link java.util.Collections#synchronizedMap(Map)};
46  * instances are already thread-safe. Unfortunately, however, this means
47  * that this map implementation behaves in ways you may find disconcerting.
48  * Bulk operations, such as {@link #putAll(Map) putAll} or the
49  * {@link Collection#retainAll(Collection) retainAll} operation in collection
50  * views, are <i>not</i> atomic. If two threads are simultaneously
51  * executing
52  *
53  * <pre>
54  * staticBucketMapInstance.putAll(map);
55  * </pre>
56  *
57  * and
58  *
59  * <pre>
60  * staticBucketMapInstance.entrySet().removeAll(map.entrySet());
61  * </pre>
62  *
63  * then the results are generally random. Those two statement could cancel
64  * each other out, leaving <code>staticBucketMapInstance</code> essentially
65  * unchanged, or they could leave some random subset of <code>map</code> in
66  * <code>staticBucketMapInstance</code>.<p>
67  *
68  * Also, much like an encyclopedia, the results of {@link #size()} and
69  * {@link #isEmpty()} are out-of-date as soon as they are produced.<p>
70  *
71  * The iterators returned by the collection views of this class are <i>not</i>
72  * fail-fast. They will <i>never</i> raise a
73  * {@link java.util.ConcurrentModificationException}. Keys and values
74  * added to the map after the iterator is created do not necessarily appear
75  * during iteration. Similarly, the iterator does not necessarily fail to
76  * return keys and values that were removed after the iterator was created.<p>
77  *
78  * Finally, unlike {@link java.util.HashMap}-style implementations, this
79  * class <i>never</i> rehashes the map. The number of buckets is fixed
80  * at construction time and never altered. Performance may degrade if
81  * you do not allocate enough buckets upfront.<p>
82  *
83  * The {@link #atomic(Runnable)} method is provided to allow atomic iterations
84  * and bulk operations; however, overuse of {@link #atomic(Runnable) atomic}
85  * will basically result in a map that's slower than an ordinary synchronized
86  * {@link java.util.HashMap}.
87  *
88  * Use this class if you do not require reliable bulk operations and
89  * iterations, or if you can make your own guarantees about how bulk
90  * operations will affect the map.<p>
91  *
92  * @since Commons Collections 3.0 (previously in main package v2.1)
93  * @version $Revision: 1.11 $ $Date: 2004/02/18 01:13:19 $
94  *
95  * @author Berin Loritsch
96  * @author Gerhard Froehlich
97  * @author Michael A. Smith
98  * @author Paul Jack
99  * @author Leo Sutic
100  * @author Janek Bogucki
101  */
102 public final class StaticBucketMap implements Map {
103
104     /** The default number of buckets to use */
105     private static final int DEFAULT_BUCKETS = 255;
106     /** The array of buckets, where the actual data is held */
107     private Node[] buckets;
108     /** The matching array of locks */
109     private Lock[] locks;
110
111     /**
112      * Initializes the map with the default number of buckets (255).
113      */
114     public StaticBucketMap() {
115         this(DEFAULT_BUCKETS);
116     }
117
118     /**
119      * Initializes the map with a specified number of buckets. The number
120      * of buckets is never below 17, and is always an odd number (StaticBucketMap
121      * ensures this). The number of buckets is inversely proportional to the
122      * chances for thread contention. The fewer buckets, the more chances for
123      * thread contention. The more buckets the fewer chances for thread
124      * contention.
125      *
126      * @param numBuckets the number of buckets for this map
127      */
128     public StaticBucketMap(int numBuckets) {
129         int size = Math.max(17, numBuckets);
130
131         // Ensure that bucketSize is never a power of 2 (to ensure maximal distribution)
132 if (size % 2 == 0) {
133             size--;
134         }
135
136         buckets = new Node[size];
137         locks = new Lock[size];
138
139         for (int i = 0; i < size; i++) {
140             locks[i] = new Lock();
141         }
142     }
143
144     //-----------------------------------------------------------------------
145 /**
146      * Determine the exact hash entry for the key. The hash algorithm
147      * is rather simplistic, but it does the job:
148      *
149      * <pre>
150      * He = |Hk mod n|
151      * </pre>
152      *
153      * <p>
154      * He is the entry's hashCode, Hk is the key's hashCode, and n is
155      * the number of buckets.
156      * </p>
157      */
158     private final int getHash(Object key) {
159         if (key == null) {
160             return 0;
161         }
162         int hash = key.hashCode();
163         hash += ~(hash << 15);
164         hash ^= (hash >>> 10);
165         hash += (hash << 3);
166         hash ^= (hash >>> 6);
167         hash += ~(hash << 11);
168         hash ^= (hash >>> 16);
169         hash %= buckets.length;
170         return (hash < 0) ? hash * -1 : hash;
171     }
172
173     /**
174      * Gets the current size of the map.
175      * The value is computed fresh each time the method is called.
176      *
177      * @return the current size
178      */
179     public int size() {
180         int cnt = 0;
181
182         for (int i = 0; i < buckets.length; i++) {
183             cnt += locks[i].size;
184         }
185         return cnt;
186     }
187
188     /**
189      * Checks if the size is currently zero.
190      *
191      * @return true if empty
192      */
193     public boolean isEmpty() {
194         return (size() == 0);
195     }
196
197     /**
198      * Gets the value associated with the key.
199      *
200      * @param key the key to retrieve
201      * @return the associated value
202      */
203     public Object get(final Object key) {
204         int hash = getHash(key);
205
206         synchronized (locks[hash]) {
207             Node n = buckets[hash];
208
209             while (n != null) {
210                 if (n.key == key || (n.key != null && n.key.equals(key))) {
211                     return n.value;
212                 }
213
214                 n = n.next;
215             }
216         }
217         return null;
218     }
219
220     /**
221      * Checks if the map contains the specified key.
222      *
223      * @param key the key to check
224      * @return true if found
225      */
226     public boolean containsKey(final Object key) {
227         int hash = getHash(key);
228
229         synchronized (locks[hash]) {
230             Node n = buckets[hash];
231
232             while (n != null) {
233                 if (n.key == null || (n.key != null && n.key.equals(key))) {
234                     return true;
235                 }
236
237                 n = n.next;
238             }
239         }
240         return false;
241     }
242
243     /**
244      * Checks if the map contains the specified value.
245      *
246      * @param value the value to check
247      * @return true if found
248      */
249     public boolean containsValue(final Object value) {
250         for (int i = 0; i < buckets.length; i++) {
251             synchronized (locks[i]) {
252                 Node n = buckets[i];
253
254                 while (n != null) {
255                     if (n.value == value || (n.value != null && n.value.equals(value))) {
256                         return true;
257                     }
258
259                     n = n.next;
260                 }
261             }
262         }
263         return false;
264     }
265
266     //-----------------------------------------------------------------------
267 /**
268      * Puts a new key value mapping into the map.
269      *
270      * @param key the key to use
271      * @param value the value to use
272      * @return the previous mapping for the key
273      */
274     public Object put(final Object key, final Object value) {
275         int hash = getHash(key);
276
277         synchronized (locks[hash]) {
278             Node n = buckets[hash];
279
280             if (n == null) {
281                 n = new Node();
282                 n.key = key;
283                 n.value = value;
284                 buckets[hash] = n;
285                 locks[hash].size++;
286                 return null;
287             }
288
289             // Set n to the last node in the linked list. Check each key along the way
290 // If the key is found, then change the value of that node and return
291 // the old value.
292 for (Node next = n; next != null; next = next.next) {
293                 n = next;
294
295                 if (n.key == key || (n.key != null && n.key.equals(key))) {
296                     Object returnVal = n.value;
297                     n.value = value;
298                     return returnVal;
299                 }
300             }
301
302             // The key was not found in the current list of nodes, add it to the end
303 // in a new node.
304 Node newNode = new Node();
305             newNode.key = key;
306             newNode.value = value;
307             n.next = newNode;
308             locks[hash].size++;
309         }
310         return null;
311     }
312
313     /**
314      * Removes the specified key from the map.
315      *
316      * @param key the key to remove
317      * @return the previous value at this key
318      */
319     public Object remove(Object key) {
320         int hash = getHash(key);
321
322         synchronized (locks[hash]) {
323             Node n = buckets[hash];
324             Node prev = null;
325
326             while (n != null) {
327                 if (n.key == key || (n.key != null && n.key.equals(key))) {
328                     // Remove this node from the linked list of nodes.
329 if (null == prev) {
330                         // This node was the head, set the next node to be the new head.
331 buckets[hash] = n.next;
332                     } else {
333                         // Set the next node of the previous node to be the node after this one.
334 prev.next = n.next;
335                     }
336                     locks[hash].size--;
337                     return n.value;
338                 }
339
340                 prev = n;
341                 n = n.next;
342             }
343         }
344         return null;
345     }
346     
347     //-----------------------------------------------------------------------
348 /**
349      * Gets the key set.
350      *
351      * @return the key set
352      */
353     public Set keySet() {
354         return new KeySet();
355     }
356
357     /**
358      * Gets the values.
359      *
360      * @return the values
361      */
362     public Collection values() {
363         return new Values();
364     }
365
366     /**
367      * Gets the entry set.
368      *
369      * @return the entry set
370      */
371     public Set entrySet() {
372         return new EntrySet();
373     }
374
375     //-----------------------------------------------------------------------
376 /**
377      * Puts all the entries from the specified map into this map.
378      * This operation is <b>not atomic</b> and may have undesired effects.
379      *
380      * @param map the map of entries to add
381      */
382     public void putAll(Map map) {
383         Iterator i = map.keySet().iterator();
384
385         while (i.hasNext()) {
386             Object key = i.next();
387             put(key, map.get(key));
388         }
389     }
390
391     /**
392      * Clears the map of all entries.
393      */
394     public void clear() {
395         for (int i = 0; i < buckets.length; i++) {
396             Lock lock = locks[i];
397             synchronized (lock) {
398                 buckets[i] = null;
399                 lock.size = 0;
400             }
401         }
402     }
403
404     /**
405      * Compares this map to another, as per the Map specification.
406      *
407      * @param obj the object to compare to
408      * @return true if equal
409      */
410     public boolean equals(Object obj) {
411         if (obj == this) {
412             return true;
413         }
414         if (obj instanceof Map == false) {
415             return false;
416         }
417         Map other = (Map ) obj;
418         return entrySet().equals(other.entrySet());
419     }
420
421     /**
422      * Gets the hash code, as per the Map specification.
423      *
424      * @return the hash code
425      */
426     public int hashCode() {
427         int hashCode = 0;
428
429         for (int i = 0; i < buckets.length; i++) {
430             synchronized (locks[i]) {
431                 Node n = buckets[i];
432
433                 while (n != null) {
434                     hashCode += n.hashCode();
435                     n = n.next;
436                 }
437             }
438         }
439         return hashCode;
440     }
441
442     //-----------------------------------------------------------------------
443 /**
444      * The Map.Entry for the StaticBucketMap.
445      */
446     private static final class Node implements Map.Entry , KeyValue {
447         protected Object key;
448         protected Object value;
449         protected Node next;
450
451         public Object getKey() {
452             return key;
453         }
454
455         public Object getValue() {
456             return value;
457         }
458
459         public int hashCode() {
460             return ((key == null ? 0 : key.hashCode()) ^
461                     (value == null ? 0 : value.hashCode()));
462         }
463
464         public boolean equals(Object obj) {
465             if (obj == this) {
466                 return true;
467             }
468             if (obj instanceof Map.Entry == false) {
469                 return false;
470             }
471
472             Map.Entry e2 = (Map.Entry ) obj;
473             return (
474                 (key == null ? e2.getKey() == null : key.equals(e2.getKey())) &&
475                 (value == null ? e2.getValue() == null : value.equals(e2.getValue())));
476         }
477
478         public Object setValue(Object obj) {
479             Object retVal = value;
480             value = obj;
481             return retVal;
482         }
483     }
484
485
486     /**
487      * The lock object, which also includes a count of the nodes in this lock.
488      */
489     private final static class Lock {
490         public int size;
491     }
492
493
494     //-----------------------------------------------------------------------
495 private class EntryIterator implements Iterator {
496
497         private ArrayList current = new ArrayList ();
498         private int bucket;
499         private Map.Entry last;
500
501
502         public boolean hasNext() {
503             if (current.size() > 0) return true;
504             while (bucket < buckets.length) {
505                 synchronized (locks[bucket]) {
506                     Node n = buckets[bucket];
507                     while (n != null) {
508                         current.add(n);
509                         n = n.next;
510                     }
511                     bucket++;
512                     if (current.size() > 0) return true;
513                 }
514             }
515             return false;
516         }
517
518         protected Map.Entry nextEntry() {
519             if (!hasNext()) throw new NoSuchElementException ();
520             last = (Map.Entry )current.remove(current.size() - 1);
521             return last;
522         }
523
524         public Object next() {
525             return nextEntry();
526         }
527
528         public void remove() {
529             if (last == null) throw new IllegalStateException ();
530             StaticBucketMap.this.remove(last.getKey());
531             last = null;
532         }
533
534     }
535
536     private class ValueIterator extends EntryIterator {
537
538         public Object next() {
539             return nextEntry().getValue();
540         }
541
542     }
543
544     private class KeyIterator extends EntryIterator {
545
546         public Object next() {
547             return nextEntry().getKey();
548         }
549
550     }
551
552     private class EntrySet extends AbstractSet {
553
554         public int size() {
555             return StaticBucketMap.this.size();
556         }
557
558         public void clear() {
559             StaticBucketMap.this.clear();
560         }
561
562         public Iterator iterator() {
563             return new EntryIterator();
564         }
565
566         public boolean contains(Object obj) {
567             Map.Entry entry = (Map.Entry ) obj;
568             int hash = getHash(entry.getKey());
569             synchronized (locks[hash]) {
570                 for (Node n = buckets[hash]; n != null; n = n.next) {
571                     if (n.equals(entry)) return true;
572                 }
573             }
574             return false;
575         }
576
577         public boolean remove(Object obj) {
578             if (obj instanceof Map.Entry == false) {
579                 return false;
580             }
581             Map.Entry entry = (Map.Entry ) obj;
582             int hash = getHash(entry.getKey());
583             synchronized (locks[hash]) {
584                 for (Node n = buckets[hash]; n != null; n = n.next) {
585                     if (n.equals(entry)) {
586                         StaticBucketMap.this.remove(n.getKey());
587                         return true;
588                     }
589                 }
590             }
591             return false;
592         }
593
594     }
595
596
597     private class KeySet extends AbstractSet {
598
599         public int size() {
600             return StaticBucketMap.this.size();
601         }
602
603         public void clear() {
604             StaticBucketMap.this.clear();
605         }
606
607         public Iterator iterator() {
608             return new KeyIterator();
609         }
610
611         public boolean contains(Object obj) {
612             return StaticBucketMap.this.containsKey(obj);
613         }
614
615         public boolean remove(Object obj) {
616             int hash = getHash(obj);
617             synchronized (locks[hash]) {
618                 for (Node n = buckets[hash]; n != null; n = n.next) {
619                     Object k = n.getKey();
620                     if ((k == obj) || ((k != null) && k.equals(obj))) {
621                         StaticBucketMap.this.remove(k);
622                         return true;
623                     }
624                 }
625             }
626             return false;
627
628         }
629
630     }
631
632
633     private class Values extends AbstractCollection {
634
635         public int size() {
636             return StaticBucketMap.this.size();
637         }
638
639         public void clear() {
640             StaticBucketMap.this.clear();
641         }
642
643         public Iterator iterator() {
644             return new ValueIterator();
645         }
646
647     }
648
649
650     /**
651      * Prevents any operations from occurring on this map while the
652      * given {@link Runnable} executes. This method can be used, for
653      * instance, to execute a bulk operation atomically:
654      *
655      * <pre>
656      * staticBucketMapInstance.atomic(new Runnable() {
657      * public void run() {
658      * staticBucketMapInstance.putAll(map);
659      * }
660      * });
661      * </pre>
662      *
663      * It can also be used if you need a reliable iterator:
664      *
665      * <pre>
666      * staticBucketMapInstance.atomic(new Runnable() {
667      * public void run() {
668      * Iterator iterator = staticBucketMapInstance.iterator();
669      * while (iterator.hasNext()) {
670      * foo(iterator.next();
671      * }
672      * }
673      * });
674      * </pre>
675      *
676      * <b>Implementation note:</b> This method requires a lot of time
677      * and a ton of stack space. Essentially a recursive algorithm is used
678      * to enter each bucket's monitor. If you have twenty thousand buckets
679      * in your map, then the recursive method will be invoked twenty thousand
680      * times. You have been warned.
681      *
682      * @param r the code to execute atomically
683      */
684     public void atomic(Runnable r) {
685         if (r == null) throw new NullPointerException ();
686         atomic(r, 0);
687     }
688
689     private void atomic(Runnable r, int bucket) {
690         if (bucket >= buckets.length) {
691             r.run();
692             return;
693         }
694         synchronized (locks[bucket]) {
695             atomic(r, bucket + 1);
696         }
697     }
698
699 }
700

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags