BucketizedHashtable


1   /*
2    * The contents of this file are subject to the terms 
3    * of the Common Development and Distribution License 
4    * (the License).  You may not use this file except in
5    * compliance with the License.
6    * 
7    * You can obtain a copy of the license at 
8    * https://glassfish.dev.java.net/public/CDDLv1.0.html or
9    * glassfish/bootstrap/legal/CDDLv1.0.txt.
10   * See the License for the specific language governing 
11   * permissions and limitations under the License.
12   * 
13   * When distributing Covered Code, include this CDDL 
14   * Header Notice in each file and include the License file 
15   * at glassfish/bootstrap/legal/CDDLv1.0.txt.  
16   * If applicable, add the following below the CDDL Header, 
17   * with the fields enclosed by brackets [] replaced by
18   * you own identifying information: 
19   * "Portions Copyrighted [year] [name of copyright owner]"
20   * 
21   * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
22   */
23  
24  package com.sun.jdo.spi.persistence.utility;
25  
26  import java.io.Serializable  ;
27  import java.util.Collection  ;
28  import java.util.Hashtable  ;
29  import java.util.Iterator  ;
30  import java.util.Map  ;
31  import java.util.Set  ;
32  
33  /**
34   * This class implements bucketize hashtable, which subdivide the key
35   * collection stored into several hashtables (buckets) of smaller size.
36   * This will reduce the contention of hashtable.
37   *
38   * @author Shing Wai Chan
39   */
40  public class BucketizedHashtable implements Cloneable  , Map  , Serializable   {
41      private int bucketSize;
42      private Hashtable  [] hashtables = null;
43  
44      /**
45       * Constructs a new, empty BucketizedHashtable with the specified
46       * bucket size, initial capacity and load factor.
47       * @param bucketSize      the number of buckets used for hashing
48       * @param initialCapacity the initial capacity of BucketizedHashtable
49       * @param loadFactor      the load factor of hashtable
50       */
51      public BucketizedHashtable(int bucketSize, int initialCapacity,
52              float loadFactor) {
53          if (bucketSize <= 0 || initialCapacity < 0) {
54              throw new IllegalArgumentException  ();
55          }
56  
57          this.bucketSize = bucketSize;   
58  
59          hashtables = new Hashtable  [bucketSize];
60  
61          // always round up to the nearest integer so that it has at
62          // least the initialCapacity
63          int initialHashtableSize =
64                  (int)Math.ceil((double)initialCapacity / bucketSize);
65  
66          for (int i = 0; i < bucketSize; i++) {
67              hashtables[i] = new Hashtable  (initialHashtableSize, loadFactor);
68          }
69      }
70  
71      /**
72       * Constructs a new, empty BucketizedHashtable with the specified
73       * bucket size, initial capacity and default load factor 0.75.
74       * @param bucketSize      the number of buckets used for hashing
75       * @param initialCapacity the initial capacity of hashtable
76       */
77      public BucketizedHashtable(int bucketSize, int initialCapacity) {
78          this(bucketSize, initialCapacity, 0.75f);
79      }
80  
81      /**
82       * Constructs a new, empty BucketizedHashtable with the specified
83       * bucket size, default initial capacity (11 * bucketSize) and
84       * default load factor 0.75.
85       * @param bucketSize      the number of buckets used for hashing
86       */
87      public BucketizedHashtable(int bucketSize) {
88          this(bucketSize, 11 * bucketSize, 0.75f);
89      }
90  
91      /**
92       * Constructs a new, empty BucketizedHashtable with the default bucket
93       * size 11, default initial capacity (11 * bucketSize)
94       * and default load factor 0.75.
95       * @param bucketSize      the number of buckets used for hashing
96       */
97      public BucketizedHashtable() {
98          this(11, 11 * 11, 0.75f);
99      }
100 
101     //-------- implementing Map --------
102 
103     /**
104      * @param  key  a key in the hashtable
105      * @return the value to which the specified key is mapped.
106      */
107     public Object   get(Object   key) {
108         return hashtables[getBucketIndex(key)].get(key);
109     }
110 
111     /**
112      * Remove the key and its corresponding value.
113      * @param  key  the key that needs to be removed
114      * @return the value to which the key had been mapped,
115      *         or <code>null</code> if the key did not have a mapping.
116      */
117     public Object   remove(Object   key) {
118         return hashtables[getBucketIndex(key)].remove(key);
119     }
120 
121     /**
122      * Maps the specified <code>key</code> to the specified
123      * <code>value</code> in this hashtable. Neither the key nor the
124      * value can be <code>null</code>. <p>
125      * @param key   the hashtable key
126      * @param value the value
127      * @return      the previous value of the specified key in hashtables,
128      *              or <code>null</code> if it did not have one.
129      */
130     public Object   put(Object   key, Object   value) {
131         return hashtables[getBucketIndex(key)].put(key, value);
132     }
133 
134     /** 
135      * @param t  BucketizedHashtable
136      *           or a Map with a supported operation entrySet
137      */
138     public void putAll(Map   t) {
139         if (t instanceof BucketizedHashtable) {
140             BucketizedHashtable bt = (BucketizedHashtable)t;
141             for (int i = 0; i < bt.bucketSize; i++) {
142                 putAllFromMapWithEntrySet(bt.hashtables[i]);
143             }
144         } else {
145             putAllFromMapWithEntrySet(t);
146         }
147     }
148 
149     /**
150      * @param  key  possible key
151      * @return true if and only if the specified object is a key in one of
152      *         of the hashtables
153      */
154     public boolean containsKey(Object   key) {
155         return hashtables[getBucketIndex(key)].containsKey(key);
156     }
157 
158     /**
159      * @param  value  possible value
160      * @return true if and only if the specified object is a value in one of
161      *         of the hashtables
162      */
163     public boolean containsValue(Object   value) {
164         for (int i = 0; i < bucketSize; i++) {
165             if (hashtables[i].containsValue(value)) {
166                 return true;
167             }
168         }
169         return false;
170     }
171 
172     /**
173      * @return the total number of key-value mappings of all buckets
174      */
175     public int size() {
176         int totalSize = 0;
177         for (int i = 0; i < bucketSize; i++) {
178              totalSize += hashtables[i].size();
179         }
180         return totalSize;
181     }
182 
183     /**
184      * @return the hash code value for this map
185      */
186     public int hashCode() {
187         int h = 0;
188         for (int i = 0; i < bucketSize; i++) {
189             h += hashtables[i].hashCode();
190         }
191         return h;
192     }
193 
194     /**
195      * @return true if this map contains no key-value mappings
196      */
197     public boolean isEmpty() {
198         for (int i = 0; i < bucketSize; i++) {
199              if (!hashtables[i].isEmpty()) {
200                  return false;
201              }
202         }
203         return true;
204     }
205 
206     /**
207      * Clears this BucketizedHashtable so that it contains no key.
208      */
209     public void clear() {
210         for (int i = 0; i < bucketSize; i++) {
211             hashtables[i].clear();
212         }
213     }
214 
215     /**
216      * The return set is backed by the map, so changes to the map are
217      * reflected in the set, and vice-versa.
218      * @return a set of Map.Entry when bucketSet equal 1
219      * @exception UnsupportedOperationException when bucketSize is greater one
220      */
221     public Set   entrySet() {
222         if (bucketSize == 1) {
223             return hashtables[0].entrySet();
224         } else {
225             throw new UnsupportedOperationException  ();
226         }
227     }
228 
229     /**
230      * The return set is backed by the map, so changes to the map are
231      * reflected in the set, and vice-versa.
232      * @return a set of keys when bucketSet equal 1
233      * @exception UnsupportedOperationException when bucketSize is greater one
234      */
235     public Set   keySet() {
236         if (bucketSize == 1) {
237             return hashtables[0].keySet();
238         } else {
239             throw new UnsupportedOperationException  ();
240         }
241     }
242 
243     /**
244      * The return collection is backed by the map, so changes to the map
245      * are reflected in the collection, and vice-versa.
246      * @return a collection of values when bucketSet equal 1
247      * @exception UnsupportedOperationException when bucketSize is greater one
248      */
249     public Collection   values() {
250         if (bucketSize == 1) {
251             return hashtables[0].values();
252         } else {
253             throw new UnsupportedOperationException  ();
254         }
255     }
256 
257     /**
258      * Compares the specified object with this map for equality.
259      * @return true if the specified object is a BucketizedHashtable
260      *         with hashtables represent the same set of mappings. 
261      */
262     public boolean equals(Object   o) {
263         if (o == this) {
264             return true;
265         }
266 
267         if (!(o instanceof BucketizedHashtable)) {
268             return false;
269         }
270         BucketizedHashtable bt = (BucketizedHashtable)o;
271         if (bt.bucketSize != bucketSize || bt.size() != size()) {
272             return false;
273         }
274 
275         for (int i = 0; i < bucketSize; i++) {
276              if (!hashtables[i].equals(bt.hashtables[i])) {
277                  return false;
278              }
279         }
280         return true;
281     }
282 
283     //-------- implementing Cloneable --------
284     /**
285      * Creates and returns a shallow copy of this object.
286      * The keys and values are not cloned.
287      * @return  a clone of BucketizedHashtable
288      */
289     public Object   clone() {
290         try {
291             BucketizedHashtable bt = (BucketizedHashtable)super.clone();
292             bt.bucketSize = bucketSize;
293             bt.hashtables = new Hashtable  [bucketSize];
294             for (int i = 0; i < bucketSize; i++) {
295                 bt.hashtables[i] = (Hashtable  )hashtables[i].clone();
296             }
297             return bt;
298         } catch (CloneNotSupportedException   e) {
299             // this shouldn't happen, since we are Cloneable
300             throw new InternalError  ();
301         }
302     }
303 
304     //----------------
305     /**
306      * @return a string representation of this BucketizedHashtable
307      */
308     public String   toString() {
309         StringBuffer   buf = new StringBuffer  ("[");  // NOI18N
310         //bucketSize always >= 1 
311         buf.append(hashtables[0].toString());
312         for (int i = 1; i < bucketSize; i++) {
313             buf.append(", "); // NOI18N
314             buf.append(hashtables[i].toString());
315         }
316         buf.append("]"); // NOI18N
317         return buf.toString();
318     }
319 
320     /**
321      * @param t  Map with a supported entrySet operation
322      */
323     private void putAllFromMapWithEntrySet(Map   t) {
324         Iterator   iter = t.entrySet().iterator();
325         while (iter.hasNext()) {
326             Map.Entry   e = (Map.Entry  )iter.next();
327             put(e.getKey(), e.getValue());
328         }
329     }
330 
331     /**
332      * @param  key 
333      * @return the bucket index for the specified key
334      */
335     private int getBucketIndex(Object   key) {
336         int index = key.hashCode() % bucketSize;
337         return (index >= 0) ? index : index + bucketSize;
338     }
339 }
340
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags