PrimitiveHashBase


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 keys of
29   * primitive types. This base class implementation is based on a design using
30   * parallel arrays for "slot in use" flags and the actual key values, with
31   * type-specific subclasses implementing the key value hashing and comparisons.
32   * Subclasses may use additional parallel arrays beyond these two, and the
33   * internal operation is designed to allow for this case.<p>
34   *
35   * Hash classes based on this class are unsynchronized in order to provide the
36   * best possible performance for typical usage scenarios, so explicit
37   * synchronization must be implemented by the subclass or the application in
38   * cases where they are to be modified in a multithreaded environment.<p>
39   *
40   * This implementation uses the standard naive hash technique of adding a
41   * fixed offset to the computed position in the table when a collision occurs,
42   * so that several checks may potentially be necessary in order to determine if
43   * a particular key value is present in the table (since if the slot calculated
44   * by the hash function is occupied by a different entry it's still necessary to
45   * check the offset slot for a match, and then the offset slot from that, until
46   * an empty slot is found).<p>
47   *
48   * Each time the number of entries present in the table grows above the
49   * specified fraction full the table is expanded to twice its prior size
50   * plus one (to ensure the size is always an odd number). The collision
51   * offset is set to half the table size rounded down, ensuring that it
52   * will cycle through all slots of the table before returning to the
53   * original slot.<p>
54   *
55   * Subclasses need to implement the abstract methods defined by this class
56   * for working with the key array, as well as the actual data access methods.
57   *
58   * @see com.sosnoski.util.ObjectHashBase
59   * @author Dennis M. Sosnoski
60   * @version 1.0
61   */
62  
63  public abstract class PrimitiveHashBase
64  {
65      /** Default fill fraction allowed before growing table. */
66      protected static final double DEFAULT_FILL = 0.3d;
67  
68      /** Minimum size used for table. */
69      protected static final int MINIMUM_SIZE = 31;
70  
71      /** Hash value multiplier to scramble bits before calculating slot. */
72      protected static final int KEY_MULTIPLIER = 517;
73  
74      /** Fill fraction allowed for table. */
75      protected double m_fillFraction;
76  
77      /** Number of entries present in table. */
78      protected int m_entryCount;
79  
80      /** Entries allowed before growing table. */
81      protected int m_entryLimit;
82  
83      /** Offset added (modulo table size) to slot number on collision. */
84      protected int m_hitOffset;
85  
86      /** Array of slot occupied flags. */
87      protected boolean[] m_flagTable;
88  
89      /**
90       * Constructor with full specification.
91       *
92       * @param count number of values to assume in initial sizing of table
93       * @param fill fraction full allowed for table before growing
94       * @param ktype type of primitives used for keys
95       */
96  
97      public PrimitiveHashBase(int count, double fill, Class   ktype) {
98  
99          // check the passed in fill fraction
100         if (fill <= 0.0d || fill >= 1.0d) {
101             throw new IllegalArgumentException  ("fill value out of range");
102         }
103         m_fillFraction = fill;
104 
105         // compute initial table size (ensuring odd)
106         int size = Math.max((int) (count / m_fillFraction), MINIMUM_SIZE);
107         size += (size + 1) % 2;
108 
109         // initialize the table information
110         m_entryLimit = (int) (size * m_fillFraction);
111         m_hitOffset = size / 2;
112         m_flagTable = new boolean[size];
113         setKeyArray(Array.newInstance(ktype, size));
114     }
115 
116     /**
117      * Copy (clone) constructor.
118      *
119      * @param base instance being copied
120      */
121 
122     public PrimitiveHashBase(PrimitiveHashBase base) {
123 
124         // copy the basic occupancy information
125         m_fillFraction = base.m_fillFraction;
126         m_entryCount = base.m_entryCount;
127         m_entryLimit = base.m_entryLimit;
128         m_hitOffset = base.m_hitOffset;
129 
130         // copy table of slot occupied flags
131         int size = base.m_flagTable.length;
132         m_flagTable = new boolean[size];
133         System.arraycopy(base.m_flagTable, 0, m_flagTable, 0,
134             m_flagTable.length);
135 
136         // copy table of keys
137         Class   type = base.getKeyArray().getClass().getComponentType();
138         Object   copy = Array.newInstance(type, size);
139         System.arraycopy(base.getKeyArray(), 0, copy, 0, size);
140         setKeyArray(copy);
141     }
142 
143     /**
144      * Get number of items in table.
145      *
146      * @return item count present
147      */
148 
149     public final int size() {
150         return m_entryCount;
151     }
152 
153     /**
154      * Get the backing array of keys. This method is used by the type-agnostic
155      * base class code to access the array used for type-specific storage by
156      * the child class.
157      *
158      * @return backing key array object
159      */
160 
161     protected abstract Object   getKeyArray();
162 
163     /**
164      * Set the backing array of keys. This method is used by the type-agnostic
165      * base class code to set the array used for type-specific storage by the
166      * child class.
167      *
168      * @param array backing key array object
169      */
170 
171     protected abstract void setKeyArray(Object   array);
172 
173     /**
174      * Resize the base arrays after a size change. This is a separate abstract
175      * method so that derived classes can implement the handling appropriate
176      * for their data structures (which may include more than just the arrays
177      * of flags and key values).
178      *
179      * @param size new size for base arrays
180      */
181 
182     protected abstract void reallocate(int size);
183 
184     /**
185      * Increase table capacity. This method is called when we actually need
186      * to increase the table size.
187      *
188      * @param min minimum new table capacity
189      */
190 
191     protected void growCapacity(int min) {
192 
193         // find the array size required
194         int size = m_flagTable.length;
195         int limit = m_entryLimit;
196         while (limit < min) {
197             size = size * 2 + 1;
198             limit = (int) (size * m_fillFraction);
199         }
200 
201         // set parameters for new array size
202         m_entryLimit = limit;
203         m_hitOffset = size / 2;
204 
205         // let the subclass handle the adjustments to data
206         reallocate(size);
207     }
208 
209     /**
210      * Ensure that the table has the capacity for at least the specified
211      * number of keys.
212      *
213      * @param min minimum capacity to be guaranteed
214      */
215 
216     public final void ensureCapacity(int min) {
217         if (min > m_entryLimit) {
218             growCapacity(min);
219         }
220     }
221 
222     /**
223      * Set the table to the empty state. This method may need to be overridden
224      * in cases where other information associated with the keys also needs to
225      * be cleared.
226      */
227 
228     public void clear() {
229         for (int i = 0; i < m_flagTable.length; i++) {
230             m_flagTable[i] = false;
231         }
232         m_entryCount = 0;
233     }
234 
235     /**
236      * Step the slot number for an entry. Adds the collision offset (modulo
237      * the table size) to the slot number.
238      *
239      * @param slot slot number to be stepped
240      * @return stepped slot number
241      */
242 
243     protected final int stepSlot(int slot) {
244         return (slot + m_hitOffset) % m_flagTable.length;
245     }
246 
247     /**
248      * Find free slot number for entry. Starts at the slot based directly
249      * on the hashed key value. If this slot is already occupied, it adds
250      * the collision offset (modulo the table size) to the slot number and
251      * checks that slot, repeating until an unused slot is found.
252      *
253      * @param slot initial slot computed from key
254      * @return slot at which entry was added
255      */
256 
257     protected final int freeSlot(int slot) {
258         while (m_flagTable[slot]) {
259             slot = stepSlot(slot);
260         }
261         return slot;
262     }
263 }
264
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags