KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > jdo > spi > persistence > utility > 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 JavaDoc;
27 import java.util.Collection JavaDoc;
28 import java.util.Hashtable JavaDoc;
29 import java.util.Iterator JavaDoc;
30 import java.util.Map JavaDoc;
31 import java.util.Set JavaDoc;
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 JavaDoc, Map JavaDoc, Serializable JavaDoc {
41     private int bucketSize;
42     private Hashtable JavaDoc[] 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 JavaDoc();
55         }
56
57         this.bucketSize = bucketSize;
58
59         hashtables = new Hashtable JavaDoc[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 JavaDoc(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 JavaDoc get(Object JavaDoc 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 JavaDoc remove(Object JavaDoc 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 JavaDoc put(Object JavaDoc key, Object JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc 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 JavaDoc entrySet() {
222         if (bucketSize == 1) {
223             return hashtables[0].entrySet();
224         } else {
225             throw new UnsupportedOperationException JavaDoc();
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 JavaDoc keySet() {
236         if (bucketSize == 1) {
237             return hashtables[0].keySet();
238         } else {
239             throw new UnsupportedOperationException JavaDoc();
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 JavaDoc values() {
250         if (bucketSize == 1) {
251             return hashtables[0].values();
252         } else {
253             throw new UnsupportedOperationException JavaDoc();
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 JavaDoc 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 JavaDoc clone() {
290         try {
291             BucketizedHashtable bt = (BucketizedHashtable)super.clone();
292             bt.bucketSize = bucketSize;
293             bt.hashtables = new Hashtable JavaDoc[bucketSize];
294             for (int i = 0; i < bucketSize; i++) {
295                 bt.hashtables[i] = (Hashtable JavaDoc)hashtables[i].clone();
296             }
297             return bt;
298         } catch (CloneNotSupportedException JavaDoc e) {
299             // this shouldn't happen, since we are Cloneable
300
throw new InternalError JavaDoc();
301         }
302     }
303
304     //----------------
305
/**
306      * @return a string representation of this BucketizedHashtable
307      */

308     public String JavaDoc toString() {
309         StringBuffer JavaDoc buf = new StringBuffer JavaDoc("["); // 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 JavaDoc t) {
324         Iterator JavaDoc iter = t.entrySet().iterator();
325         while (iter.hasNext()) {
326             Map.Entry JavaDoc e = (Map.Entry JavaDoc)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 JavaDoc key) {
336         int index = key.hashCode() % bucketSize;
337         return (index >= 0) ? index : index + bucketSize;
338     }
339 }
340
Popular Tags