CustomHashtable


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     Peter Shipton - original hashtable implementation
10   *     Nick Edgar - added element comparer support
11   *******************************************************************************/
12  
13  package org.eclipse.jface.viewers;
14  
15  import java.util.Enumeration  ;
16  import java.util.NoSuchElementException  ;
17  
18  /**
19   * CustomHashtable associates keys with values. Keys and values cannot be null.
20   * The size of the Hashtable is the number of key/value pairs it contains.
21   * The capacity is the number of key/value pairs the Hashtable can hold.
22   * The load factor is a float value which determines how full the Hashtable
23   * gets before expanding the capacity. If the load factor of the Hashtable
24   * is exceeded, the capacity is doubled.
25   * <p>
26   * CustomHashtable allows a custom comparator and hash code provider.
27   */
28  /* package */final class CustomHashtable {
29  
30      /**
31       * HashMapEntry is an internal class which is used to hold the entries of a Hashtable.
32       */
33      private static class HashMapEntry {
34          Object   key, value;
35  
36          HashMapEntry next;
37  
38          HashMapEntry(Object   theKey, Object   theValue) {
39              key = theKey;
40              value = theValue;
41          }
42      }
43  
44      private static final class EmptyEnumerator implements Enumeration   {
45          public boolean hasMoreElements() {
46              return false;
47          }
48  
49          public Object   nextElement() {
50              throw new NoSuchElementException  ();
51          }
52      }
53  
54      private class HashEnumerator implements Enumeration   {
55          boolean key;
56  
57          int start;
58  
59          HashMapEntry entry;
60  
61          HashEnumerator(boolean isKey) {
62              key = isKey;
63              start = firstSlot;
64          }
65  
66          public boolean hasMoreElements() {
67              if (entry != null) {
68                  return true;
69              }
70              while (start <= lastSlot) {
71                  if (elementData[start++] != null) {
72                      entry = elementData[start - 1];
73                      return true;
74                  }
75              }
76              return false;
77          }
78  
79          public Object   nextElement() {
80              if (hasMoreElements()) {
81                  Object   result = key ? entry.key : entry.value;
82                  entry = entry.next;
83                  return result;
84              } else {
85                  throw new NoSuchElementException  ();
86              }
87          }
88      }
89  
90      transient int elementCount;
91  
92      transient HashMapEntry[] elementData;
93  
94      private float loadFactor;
95  
96      private int threshold;
97  
98      transient int firstSlot = 0;
99  
100     transient int lastSlot = -1;
101 
102     transient private IElementComparer comparer;
103 
104     private static final EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
105 
106     /**
107      * The default capacity used when not specified in the constructor.
108      */
109     public static final int DEFAULT_CAPACITY = 13;
110 
111     /**
112      * Constructs a new Hashtable using the default capacity
113      * and load factor.
114      */
115     public CustomHashtable() {
116         this(13);
117     }
118 
119     /**
120      * Constructs a new Hashtable using the specified capacity
121      * and the default load factor.
122      *
123      * @param capacity the initial capacity
124      */
125     public CustomHashtable(int capacity) {
126         this(capacity, null);
127     }
128 
129     /**
130      * Constructs a new hash table with the default capacity and the given
131      * element comparer.
132      *
133      * @param comparer the element comparer to use to compare keys and obtain
134      *   hash codes for keys, or <code>null</code>  to use the normal 
135      *   <code>equals</code> and <code>hashCode</code> methods
136      */
137     public CustomHashtable(IElementComparer comparer) {
138         this(DEFAULT_CAPACITY, comparer);
139     }
140 
141     /**
142      * Constructs a new hash table with the given capacity and the given
143      * element comparer.
144      * 
145      * @param capacity the maximum number of elements that can be added without
146      *   rehashing
147      * @param comparer the element comparer to use to compare keys and obtain
148      *   hash codes for keys, or <code>null</code>  to use the normal 
149      *   <code>equals</code> and <code>hashCode</code> methods
150      */
151     public CustomHashtable(int capacity, IElementComparer comparer) {
152         if (capacity >= 0) {
153             elementCount = 0;
154             elementData = new HashMapEntry[capacity == 0 ? 1 : capacity];
155             firstSlot = elementData.length;
156             loadFactor = 0.75f;
157             computeMaxSize();
158         } else {
159             throw new IllegalArgumentException  ();
160         }
161         this.comparer = comparer;
162     }
163 
164     /**
165      * Constructs a new hash table with enough capacity to hold all keys in the
166      * given hash table, then adds all key/value pairs in the given hash table
167      * to the new one, using the given element comparer.
168      * @param table the original hash table to copy from
169      * 
170      * @param comparer the element comparer to use to compare keys and obtain
171      *   hash codes for keys, or <code>null</code>  to use the normal 
172      *   <code>equals</code> and <code>hashCode</code> methods
173      */
174     public CustomHashtable(CustomHashtable table, IElementComparer comparer) {
175         this(table.size() * 2, comparer);
176         for (int i = table.elementData.length; --i >= 0;) {
177             HashMapEntry entry = table.elementData[i];
178             while (entry != null) {
179                 put(entry.key, entry.value);
180                 entry = entry.next;
181             }
182         }
183     }
184     
185     /**
186      * Returns the element comparer used  to compare keys and to obtain
187      * hash codes for keys, or <code>null</code> if no comparer has been
188      * provided.
189      * 
190      * @return the element comparer or <code>null</code>
191      * 
192      * @since 3.2
193      */
194     public IElementComparer getComparer() {
195         return comparer;
196     }
197 
198     private void computeMaxSize() {
199         threshold = (int) (elementData.length * loadFactor);
200     }
201 
202     /**
203      * Answers if this Hashtable contains the specified object as a key
204      * of one of the key/value pairs.
205      *
206      * @param       key the object to look for as a key in this Hashtable
207      * @return      true if object is a key in this Hashtable, false otherwise
208      */
209     public boolean containsKey(Object   key) {
210         return getEntry(key) != null;
211     }
212 
213     /**
214      * Answers an Enumeration on the values of this Hashtable. The
215      * results of the Enumeration may be affected if the contents
216      * of this Hashtable are modified.
217      *
218      * @return      an Enumeration of the values of this Hashtable
219      */
220     public Enumeration   elements() {
221         if (elementCount == 0) {
222             return emptyEnumerator;
223         }
224         return new HashEnumerator(false);
225     }
226 
227     /**
228      * Answers the value associated with the specified key in
229      * this Hashtable.
230      *
231      * @param       key the key of the value returned
232      * @return      the value associated with the specified key, null if the specified key
233      *              does not exist
234      */
235     public Object   get(Object   key) {
236         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
237         HashMapEntry entry = elementData[index];
238         while (entry != null) {
239             if (keyEquals(key, entry.key)) {
240                 return entry.value;
241             }
242             entry = entry.next;
243         }
244         return null;
245     }
246 
247     private HashMapEntry getEntry(Object   key) {
248         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
249         HashMapEntry entry = elementData[index];
250         while (entry != null) {
251             if (keyEquals(key, entry.key)) {
252                 return entry;
253             }
254             entry = entry.next;
255         }
256         return null;
257     }
258 
259     /**
260      * Answers the hash code for the given key.
261      */
262     private int hashCode(Object   key) {
263         if (comparer == null) {
264             return key.hashCode();
265         } else {
266             return comparer.hashCode(key);
267         }
268     }
269 
270     /**
271      * Compares two keys for equality.
272      */
273     private boolean keyEquals(Object   a, Object   b) {
274         if (comparer == null) {
275             return a.equals(b);
276         } else {
277             return comparer.equals(a, b);
278         }
279     }
280 
281     /**
282      * Answers an Enumeration on the keys of this Hashtable. The
283      * results of the Enumeration may be affected if the contents
284      * of this Hashtable are modified.
285      *
286      * @return      an Enumeration of the keys of this Hashtable
287      */
288     public Enumeration   keys() {
289         if (elementCount == 0) {
290             return emptyEnumerator;
291         }
292         return new HashEnumerator(true);
293     }
294 
295     /**
296      * Associate the specified value with the specified key in this Hashtable.
297      * If the key already exists, the old value is replaced. The key and value
298      * cannot be null.
299      *
300      * @param       key the key to add
301      * @param       value   the value to add
302      * @return      the old value associated with the specified key, null if the key did
303      *              not exist
304      */
305     public Object   put(Object   key, Object   value) {
306         if (key != null && value != null) {
307             int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
308             HashMapEntry entry = elementData[index];
309             while (entry != null && !keyEquals(key, entry.key)) {
310                 entry = entry.next;
311             }
312             if (entry == null) {
313                 if (++elementCount > threshold) {
314                     rehash();
315                     index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
316                 }
317                 if (index < firstSlot) {
318                     firstSlot = index;
319                 }
320                 if (index > lastSlot) {
321                     lastSlot = index;
322                 }
323                 entry = new HashMapEntry(key, value);
324                 entry.next = elementData[index];
325                 elementData[index] = entry;
326                 return null;
327             }
328             Object   result = entry.value;
329             entry.key = key; // important to avoid hanging onto keys that are equal but "old" -- see bug 30607
330             entry.value = value;
331             return result;
332         } else {
333             throw new NullPointerException  ();
334         }
335     }
336 
337     /**
338      * Increases the capacity of this Hashtable. This method is sent when
339      * the size of this Hashtable exceeds the load factor.
340      */
341     private void rehash() {
342         int length = elementData.length << 1;
343         if (length == 0) {
344             length = 1;
345         }
346         firstSlot = length;
347         lastSlot = -1;
348         HashMapEntry[] newData = new HashMapEntry[length];
349         for (int i = elementData.length; --i >= 0;) {
350             HashMapEntry entry = elementData[i];
351             while (entry != null) {
352                 int index = (hashCode(entry.key) & 0x7FFFFFFF) % length;
353                 if (index < firstSlot) {
354                     firstSlot = index;
355                 }
356                 if (index > lastSlot) {
357                     lastSlot = index;
358                 }
359                 HashMapEntry next = entry.next;
360                 entry.next = newData[index];
361                 newData[index] = entry;
362                 entry = next;
363             }
364         }
365         elementData = newData;
366         computeMaxSize();
367     }
368 
369     /**
370      * Remove the key/value pair with the specified key from this Hashtable.
371      *
372      * @param       key the key to remove
373      * @return      the value associated with the specified key, null if the specified key
374      *              did not exist
375      */
376     public Object   remove(Object   key) {
377         HashMapEntry last = null;
378         int index = (hashCode(key) & 0x7FFFFFFF) % elementData.length;
379         HashMapEntry entry = elementData[index];
380         while (entry != null && !keyEquals(key, entry.key)) {
381             last = entry;
382             entry = entry.next;
383         }
384         if (entry != null) {
385             if (last == null) {
386                 elementData[index] = entry.next;
387             } else {
388                 last.next = entry.next;
389             }
390             elementCount--;
391             return entry.value;
392         }
393         return null;
394     }
395 
396     /**
397      * Answers the number of key/value pairs in this Hashtable.
398      *
399      * @return      the number of key/value pairs in this Hashtable
400      */
401     public int size() {
402         return elementCount;
403     }
404 
405     /**
406      * Answers the string representation of this Hashtable.
407      *
408      * @return      the string representation of this Hashtable
409      */
410     public String   toString() {
411         if (size() == 0) {
412             return "{}"; //$NON-NLS-1$
413         }
414 
415         StringBuffer   buffer = new StringBuffer  ();
416         buffer.append('{');
417         for (int i = elementData.length; --i >= 0;) {
418             HashMapEntry entry = elementData[i];
419             while (entry != null) {
420                 buffer.append(entry.key);
421                 buffer.append('=');
422                 buffer.append(entry.value);
423                 buffer.append(", "); //$NON-NLS-1$
424                 entry = entry.next;
425             }
426         }
427         // Remove the last ", "
428         if (elementCount > 0) {
429             buffer.setLength(buffer.length() - 2);
430         }
431         buffer.append('}');
432         return buffer.toString();
433     }
434 }
435
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags