CustomHashtable


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