AbstractHashMap


1   /*
2    Copyright � 1999 CERN - European Organization for Nuclear Research.
3    Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose 
4    is hereby granted without fee, provided that the above copyright notice appear in all copies and 
5    that both that copyright notice and this permission notice appear in supporting documentation. 
6    CERN makes no representations about the suitability of this software for any purpose. 
7    It is provided "as is" without expressed or implied warranty.
8    */
9   package prefuse.util.collections;
10  
11  /**
12   * Abstract base class for hash maps holding objects or primitive data types
13   * such as <code>int</code>, <code>float</code>, etc. as keys and/or
14   * values. First see the <a HREF="package-summary.html">package summary</a> and
15   * javadoc <a HREF="package-tree.html">tree view</a> to get the broad picture.
16   * <p>
17   * Note that implementations are not synchronized.
18   * 
19   * @author wolfgang.hoschek@cern.ch
20   * @version 1.0, 09/24/99
21   * @see java.util.HashMap
22   */
23  public abstract class AbstractHashMap {
24  
25      /**
26       * The number of distinct associations in the map; its "size()".
27       */
28      protected int distinct;
29  
30      /**
31       * The table capacity c=table.length always satisfies the invariant
32       * <tt>c * minLoadFactor <= s <= c * maxLoadFactor</tt>, where s=size()
33       * is the number of associations currently contained. The term "c *
34       * minLoadFactor" is called the "lowWaterMark", "c * maxLoadFactor" is
35       * called the "highWaterMark". In other words, the table capacity (and
36       * proportionally the memory used by this class) oscillates within these
37       * constraints. The terms are precomputed and cached to avoid recalculating
38       * them each time put(..) or removeKey(...) is called.
39       */
40      protected int lowWaterMark;
41  
42      protected int highWaterMark;
43  
44      /**
45       * The minimum load factor for the hashtable.
46       */
47      protected double minLoadFactor;
48  
49      /**
50       * The maximum load factor for the hashtable.
51       */
52      protected double maxLoadFactor;
53  
54      protected static final int defaultCapacity = 277;
55  
56      protected static final double defaultMinLoadFactor = 0.2;
57  
58      protected static final double defaultMaxLoadFactor = 0.5;
59  
60      /**
61       * Makes this class non instantiable, but still let's others inherit from
62       * it.
63       */
64      protected AbstractHashMap() {
65      }
66  
67      /**
68       * Chooses a new prime table capacity optimized for growing that
69       * (approximately) satisfies the invariant
70       * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
71       * least one FREE slot for the given size.
72       */
73      protected int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
74          return nextPrime(Math.max(size + 1,
75                  (int) ((4 * size / (3 * minLoad + maxLoad)))));
76      }
77  
78      /**
79       * Returns new high water mark threshold based on current capacity and
80       * maxLoadFactor.
81       * 
82       * @return int the new threshold.
83       */
84      protected int chooseHighWaterMark(int capacity, double maxLoad) {
85          return Math.min(capacity - 2, (int) (capacity * maxLoad)); // makes
86                                                                      // sure
87                                                                      // there is
88                                                                      // always at
89                                                                      // least one
90                                                                      // FREE slot
91      }
92  
93      /**
94       * Returns new low water mark threshold based on current capacity and
95       * minLoadFactor.
96       * 
97       * @return int the new threshold.
98       */
99      protected int chooseLowWaterMark(int capacity, double minLoad) {
100         return (int) (capacity * minLoad);
101     }
102 
103     /**
104      * Chooses a new prime table capacity neither favoring shrinking nor
105      * growing, that (approximately) satisfies the invariant
106      * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
107      * least one FREE slot for the given size.
108      */
109     protected int chooseMeanCapacity(int size, double minLoad, double maxLoad) {
110         return nextPrime(Math.max(size + 1,
111                 (int) ((2 * size / (minLoad + maxLoad)))));
112     }
113 
114     /**
115      * Chooses a new prime table capacity optimized for shrinking that
116      * (approximately) satisfies the invariant
117      * <tt>c * minLoadFactor <= size <= c * maxLoadFactor</tt> and has at
118      * least one FREE slot for the given size.
119      */
120     protected int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
121         return nextPrime(Math.max(size + 1,
122                 (int) ((4 * size / (minLoad + 3 * maxLoad)))));
123     }
124 
125     /**
126      * Removes all (key,value) associations from the receiver.
127      */
128     public abstract void clear();
129 
130     /**
131      * Ensures that the receiver can hold at least the specified number of
132      * elements without needing to allocate new internal memory. If necessary,
133      * allocates new internal memory and increases the capacity of the receiver.
134      * <p>
135      * This method never need be called; it is for performance tuning only.
136      * Calling this method before <tt>put()</tt>ing a large number of
137      * associations boosts performance, because the receiver will grow only once
138      * instead of potentially many times.
139      * <p>
140      * <b>This default implementation does nothing.</b> Override this method if
141      * necessary.
142      * 
143      * @param minCapacity
144      *            the desired minimum capacity.
145      */
146     public void ensureCapacity(int minCapacity) {
147     }
148 
149     /**
150      * Returns <tt>true</tt> if the receiver contains no (key,value)
151      * associations.
152      * 
153      * @return <tt>true</tt> if the receiver contains no (key,value)
154      *         associations.
155      */
156     public boolean isEmpty() {
157         return distinct == 0;
158     }
159 
160     /**
161      * Returns a prime number which is <code>&gt;= desiredCapacity</code> and
162      * very close to <code>desiredCapacity</code> (within 11% if
163      * <code>desiredCapacity &gt;= 1000</code>).
164      * 
165      * @param desiredCapacity
166      *            the capacity desired by the user.
167      * @return the capacity which should be used for a hashtable.
168      */
169     protected int nextPrime(int desiredCapacity) {
170         return PrimeFinder.nextPrime(desiredCapacity);
171     }
172 
173     /**
174      * Initializes the receiver. You will almost certainly need to override this
175      * method in subclasses to initialize the hash table.
176      * 
177      * @param initialCapacity
178      *            the initial capacity of the receiver.
179      * @param minLoadFactor
180      *            the minLoadFactor of the receiver.
181      * @param maxLoadFactor
182      *            the maxLoadFactor of the receiver.
183      * @throws IllegalArgumentException
184      *             if
185      *             <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
186      */
187     protected void setUp(int initialCapacity, double minLoadFactor,
188             double maxLoadFactor) {
189         if (initialCapacity < 0)
190             throw new IllegalArgumentException  (
191                     "Initial Capacity must not be less than zero: "
192                             + initialCapacity);
193         if (minLoadFactor < 0.0 || minLoadFactor >= 1.0)
194             throw new IllegalArgumentException  ("Illegal minLoadFactor: "
195                     + minLoadFactor);
196         if (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0)
197             throw new IllegalArgumentException  ("Illegal maxLoadFactor: "
198                     + maxLoadFactor);
199         if (minLoadFactor >= maxLoadFactor)
200             throw new IllegalArgumentException  ("Illegal minLoadFactor: "
201                     + minLoadFactor + " and maxLoadFactor: " + maxLoadFactor);
202     }
203 
204     /**
205      * Returns the number of (key,value) associations currently contained.
206      *
207      * @return the number of (key,value) associations currently contained.
208      */
209     public int size() {
210         return distinct;
211     }
212 
213     /**
214      * Trims the capacity of the receiver to be the receiver's current 
215      * size. Releases any superfluous internal memory. An application can use this operation to minimize the 
216      * storage of the receiver.
217      * <p>
218      * This default implementation does nothing. Override this method if necessary.
219      */
220     public void trimToSize() {
221     }
222     
223 } // end of class AbstractHashMap
224
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags