ObjectHashBase


1   /*
2    * Copyright (c) 2000-2001 Sosnoski Software Solutions, Inc.
3    *
4    * Permission is hereby granted, free of charge, to any person obtaining a copy
5    * of this software and associated documentation files (the "Software"), to deal
6    * in the Software without restriction, including without limitation the rights
7    * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8    * copies of the Software, and to permit persons to whom the Software is
9    * furnished to do so, subject to the following conditions:
10   *
11   * The above copyright notice and this permission notice shall be included in
12   * all copies or substantial portions of the Software.
13   *
14   * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15   * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16   * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17   * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18   * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19   * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20   * IN THE SOFTWARE.
21   */
22  
23  package com.sosnoski.util;
24  
25  import java.lang.reflect.Array  ;
26  
27  /**
28   * Base class for type-specific hash map and hash set classes using
29   * object keys. This class uses a single array for keys with <code>null</code>
30   * values in unused slots. Subclasses may use additional arrays in parallel to
31   * this key array, and the internal operation is designed to allow for this
32   * case.<p>
33   *
34   * Hash classes based on this class are unsynchronized in order to provide the
35   * best possible performance for typical usage scenarios, so explicit
36   * synchronization must be implemented by the subclass or the application in
37   * cases where they are to be modified in a multithreaded environment.<p>
38   *
39   * This implementation uses the standard naive hash technique of adding a
40   * fixed offset to the computed position in the table when a collision occurs,
41   * so that several checks may potentially be necessary in order to determine if
42   * a particular key value is present in the table (since if the slot calculated
43   * by the hash function is occupied by a different entry it's still necessary to
44   * check the offset slot for a match, and then the offset slot from that, until
45   * an empty slot is found).<p>
46   *
47   * Each time the number of entries present in the table grows above the
48   * specified fraction full the table is expanded to twice its prior size
49   * plus one (to ensure the size is always an odd number). The collision
50   * offset is set to half the table size rounded down, ensuring that it
51   * will cycle through all slots of the table before returning to the
52   * original slot.<p>
53   *
54   * Subclasses need to implement the abstract methods defined by this class
55   * for working with the key array, as well as the actual data access methods.
56   *
57   * @author Dennis M. Sosnoski
58   * @version 1.1
59   */
60  
61  public abstract class ObjectHashBase
62  {
63      /** Standard hashing technique specifier. */
64      public static final String   STANDARD_HASH = "base";
65  
66      /** Standard hash with object identity comparison technique specifier. */
67      public static final String   IDENTITY_COMP = "comp";
68  
69      /** Identity hash with object identity comparison technique specifier. */
70      public static final String   IDENTITY_HASH = "ident";
71  
72      /** Default fill fraction allowed before growing table. */
73      protected static final double DEFAULT_FILL = 0.3d;
74  
75      /** Minimum size used for hash table. */
76      protected static final int MINIMUM_SIZE = 31;
77  
78      /** Use identity hash flag. */
79      protected final boolean m_identHash;
80  
81      /** Use identity comparison flag. */
82      protected final boolean m_identCompare;
83  
84      /** Fill fraction allowed for this hash table. */
85      protected final double m_fillFraction;
86  
87      /** Number of entries present in table. */
88      protected int m_entryCount;
89  
90      /** Entries allowed before growing table. */
91      protected int m_entryLimit;
92  
93      /** Size of array used for keys. */
94      protected int m_arraySize;
95  
96      /** Offset added (modulo table size) to slot number on collision. */
97      protected int m_hitOffset;
98  
99      /**
100      * Constructor with full specification.
101      *
102      * @param count number of values to assume in initial sizing of table
103      * @param fill fraction full allowed for table before growing
104      * @param type type of keys contained in table
105      * @param tech hash technique specifier (one of STANDARD_HASH,
106      * IDENTITY_COMP, or IDENTITY_HASH)
107      */
108 
109     public ObjectHashBase(int count, double fill, Class   type, Object   tech) {
110 
111         // check the passed in fill fraction
112         if (fill <= 0.0d || fill >= 1.0d) {
113             throw new IllegalArgumentException  ("fill value out of range");
114         }
115         m_fillFraction = fill;
116 
117         // set flags for hash technique control
118         if (tech == STANDARD_HASH) {
119             m_identHash = false;
120             m_identCompare = false;
121         } else if (tech == IDENTITY_COMP) {
122             m_identHash = false;
123             m_identCompare = true;
124         } else if (tech == IDENTITY_HASH) {
125             m_identHash = true;
126             m_identCompare = true;
127         } else {
128             throw new IllegalArgumentException  
129                 ("Unknown hash technique specifier");
130         }
131 
132         // compute initial table size (ensuring odd)
133         m_arraySize = Math.max((int) (count / m_fillFraction), MINIMUM_SIZE);
134         m_arraySize += (m_arraySize + 1) % 2;
135 
136         // initialize the table information
137         m_entryLimit = (int) (m_arraySize * m_fillFraction);
138         m_hitOffset = m_arraySize / 2;
139         setKeyArray(Array.newInstance(type, m_arraySize));
140     }
141 
142     /**
143      * Copy (clone) constructor.
144      *
145      * @param base instance being copied
146      */
147 
148     public ObjectHashBase(ObjectHashBase base) {
149 
150         // copy the basic occupancy information
151         m_fillFraction = base.m_fillFraction;
152         m_entryCount = base.m_entryCount;
153         m_entryLimit = base.m_entryLimit;
154         m_arraySize = base.m_arraySize;
155         m_hitOffset = base.m_hitOffset;
156         m_identHash = base.m_identHash;
157         m_identCompare = base.m_identCompare;
158 
159         // copy table of items
160         Class   type = base.getKeyArray().getClass().getComponentType();
161         Object   copy = Array.newInstance(type, m_arraySize);
162         System.arraycopy(base.getKeyArray(), 0, copy, 0, m_arraySize);
163         setKeyArray(copy);
164     }
165 
166     /**
167      * Get number of items in table.
168      *
169      * @return item count present
170      */
171 
172     public final int size() {
173         return m_entryCount;
174     }
175 
176     /**
177      * Get the backing array of items. This method is used by the type-agnostic
178      * base class code to access the array used for type-specific storage by
179      * the child class.
180      *
181      * @return backing item array object
182      */
183 
184     protected abstract Object  [] getKeyArray();
185 
186     /**
187      * Set the backing array of items. This method is used by the type-agnostic
188      * base class code to set the array used for type-specific storage by the
189      * child class.
190      *
191      * @param array backing item array object
192      */
193 
194     protected abstract void setKeyArray(Object   array);
195 
196     /**
197      * Resize the base arrays after a size change. This is a separate abstract
198      * method so that derived classes can implement the handling appropriate
199      * for their data structures (which may include more than just the array
200      * of key values).
201      *
202      * @param size new size for base arrays
203      */
204 
205     protected abstract void reallocate(int size);
206 
207     /**
208      * Increase table capacity. This method is called when we actually need
209      * to increase the table size.
210      *
211      * @param min minimum new table capacity
212      */
213 
214     protected void growCapacity(int min) {
215 
216         // find the array size required
217         int size = m_arraySize;
218         int limit = m_entryLimit;
219         while (limit < min) {
220             size = size * 2 + 1;
221             limit = (int) (size * m_fillFraction);
222         }
223 
224         // set parameters for new array size
225         m_arraySize = size;
226         m_entryLimit = limit;
227         m_hitOffset = size / 2;
228 
229         // let the subclass handle the adjustments to data
230         reallocate(size);
231     }
232 
233     /**
234      * Ensure that the table has the capacity for at least the specified
235      * number of items.
236      *
237      * @param min minimum capacity to be guaranteed
238      */
239 
240     public final void ensureCapacity(int min) {
241         if (min > m_entryLimit) {
242             growCapacity(min);
243         }
244     }
245 
246     /**
247      * Set the table to the empty state. This method may need to be overridden
248      * in cases where other information associated with the keys also needs to
249      * be cleared.
250      */
251 
252     public void clear() {
253         Object  [] items = getKeyArray();
254         for (int i = 0; i < m_arraySize; i++) {
255             items[i] = null;
256         }
257         m_entryCount = 0;
258     }
259 
260     /**
261      * Step the slot number for an entry. Adds the collision offset (modulo
262      * the table size) to the slot number.
263      *
264      * @param slot slot number to be stepped
265      * @return stepped slot number
266      */
267 
268     protected final int stepSlot(int slot) {
269         return (slot + m_hitOffset) % m_arraySize;
270     }
271 
272     /**
273      * Find free slot number for entry. Starts at the slot based directly
274      * on the hashed key value. If this slot is already occupied, it adds
275      * the collision offset (modulo the table size) to the slot number and
276      * checks that slot, repeating until an unused slot is found.
277      *
278      * @param slot initial slot computed from key
279      * @return slot at which entry was added
280      */
281 
282     protected final int freeSlot(int slot) {
283         Object  [] items = getKeyArray();
284         while (items[slot] != null) {
285             slot = stepSlot(slot);
286         }
287         return slot;
288     }
289 
290     /**
291      * Standard base slot computation for a key. This method may be used
292      * directly for key lookup using either the <code>hashCode()</code> method
293      * defined for the key objects or the <code>System.identityHashCode()</code>
294      * method, as selected by the hash technique constructor parameter. To
295      * implement a hash class based on some other methods of hashing and/or
296      * equality testing, define a separate method in the subclass with a
297      * different name and use that method instead. This avoids the overhead
298      * caused by overrides of a very heavily used method.
299      *
300      * @param key key value to be computed
301      * @return base slot for key
302      */
303 
304     protected final int standardSlot(Object   key) {
305         return ((m_identHash ? System.identityHashCode(key) : key.hashCode()) &
306             Integer.MAX_VALUE) % m_arraySize;
307     }
308 
309     /**
310      * Standard find key in table. This method may be used directly for key
311      * lookup using either the <code>hashCode()</code> method defined for the
312      * key objects or the <code>System.identityHashCode()</code> method, and
313      * either the <code>equals()</code> method defined for the key objects or
314      * the <code>==</code> operator, as selected by the hash technique
315      * constructor parameter. To implement a hash class based on some other
316      * methods of hashing and/or equality testing, define a separate method in
317      * the subclass with a different name and use that method instead. This
318      * avoids the overhead caused by overrides of a very heavily used method.
319      *
320      * @param key to be found in table
321      * @return index of matching key, or <code>-index-1</code> of slot to be
322      * used for inserting key in table if not already present (always negative)
323      */
324 
325     protected int standardFind(Object   key) {
326 
327         // find the starting point for searching table
328         int slot = standardSlot(key);
329 
330         // scan through table to find target key
331         Object   keys[] = getKeyArray();
332         if (m_identCompare) {
333             while (keys[slot] != null) {
334 
335                 // check if we have a match on target key
336                 if (keys[slot] == key) {
337                     return slot;
338                 } else {
339                     slot = stepSlot(slot);
340                 }
341 
342             }
343         } else {
344             while (keys[slot] != null) {
345 
346                 // check if we have a match on target key
347                 if (keys[slot].equals(key)) {
348                     return slot;
349                 } else {
350                     slot = stepSlot(slot);
351                 }
352 
353             }
354         }
355         return -slot-1;
356     }
357 }
358
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags