001: /*
002: *
003: * @(#)IntHashtable.java 1.14 06/10/10
004: *
005: * Portions Copyright 2000-2006 Sun Microsystems, Inc. All Rights
006: * Reserved. Use is subject to license terms.
007: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
008: *
009: * This program is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU General Public License version
011: * 2 only, as published by the Free Software Foundation.
012: *
013: * This program is distributed in the hope that it will be useful, but
014: * WITHOUT ANY WARRANTY; without even the implied warranty of
015: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
016: * General Public License version 2 for more details (a copy is
017: * included at /legal/license.txt).
018: *
019: * You should have received a copy of the GNU General Public License
020: * version 2 along with this work; if not, write to the Free Software
021: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
022: * 02110-1301 USA
023: *
024: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
025: * Clara, CA 95054 or visit www.sun.com if you need additional
026: * information or have any questions.
027: */
028:
029: /*
030: * (C) Copyright Taligent, Inc. 1996,1997 - All Rights Reserved
031: * (C) Copyright IBM Corp. 1996, 1997 - All Rights Reserved
032: */
033:
034: package sun.text;
035:
036: /** Simple internal class for doing hash mapping. Much, much faster than the
037: * standard Hashtable for integer to integer mappings,
038: * and doesn't require object creation.<br>
039: * If a key is not found, the defaultValue is returned.
040: * Note: the keys are limited to values above Integer.MIN_VALUE+1.<br>
041: */
042: public final class IntHashtable {
043:
044: public IntHashtable() {
045: initialize(3);
046: }
047:
048: public IntHashtable(int initialSize) {
049: initialize(leastGreaterPrimeIndex((int) (initialSize / HIGH_WATER_FACTOR)));
050: }
051:
052: public int size() {
053: return count;
054: }
055:
056: public boolean isEmpty() {
057: return count == 0;
058: }
059:
060: public void put(int key, int value) {
061: if (count > highWaterMark) {
062: rehash();
063: }
064: int index = find(key);
065: if (keyList[index] <= MAX_UNUSED) { // deleted or empty
066: keyList[index] = key;
067: ++count;
068: }
069: values[index] = value; // reset value
070: }
071:
072: public int get(int key) {
073: return values[find(key)];
074: }
075:
076: public void remove(int key) {
077: int index = find(key);
078: if (keyList[index] > MAX_UNUSED) { // neither deleted nor empty
079: keyList[index] = DELETED; // set to deleted
080: values[index] = defaultValue; // set to default
081: --count;
082: if (count < lowWaterMark) {
083: rehash();
084: }
085: }
086: }
087:
088: public int getDefaultValue() {
089: return defaultValue;
090: }
091:
092: public void setDefaultValue(int newValue) {
093: defaultValue = newValue;
094: rehash();
095: }
096:
097: public boolean equals(Object that) {
098: if (that.getClass() != this .getClass())
099: return false;
100:
101: IntHashtable other = (IntHashtable) that;
102: if (other.size() != count || other.defaultValue != defaultValue) {
103: return false;
104: }
105: for (int i = 0; i < keyList.length; ++i) {
106: int key = keyList[i];
107: if (key > MAX_UNUSED && other.get(key) != values[i])
108: return false;
109: }
110: return true;
111: }
112:
113: public int hashCode() {
114: // NOTE: This function isn't actually used anywhere in this package, but it's here
115: // in case this class is ever used to make sure we uphold the invariants about
116: // hashCode() and equals()
117:
118: // WARNING: This function hasn't undergone rigorous testing to make sure it actually
119: // gives good distribution. We've eyeballed the results, and they appear okay, but
120: // you copy this algorithm (or these seed and multiplier values) at your own risk.
121: // --rtg 8/17/99
122:
123: int result = 465; // an arbitrary seed value
124: int scrambler = 1362796821; // an arbitrary multiplier.
125: for (int i = 0; i < keyList.length; ++i) {
126: // this line just scrambles the bits as each value is added into the
127: // has value. This helps to make sure we affect all the bits and that
128: // the same values in a different order will produce a different hash value
129: result = (int) (result * scrambler + 1);
130: result += keyList[i];
131: }
132: for (int i = 0; i < values.length; ++i) {
133: result = (int) (result * scrambler + 1);
134: result += values[i];
135: }
136: return result;
137: }
138:
139: public Object clone() throws CloneNotSupportedException {
140: IntHashtable result = (IntHashtable) super .clone();
141: values = (int[]) values.clone();
142: keyList = (int[]) keyList.clone();
143: return result;
144: }
145:
146: // =======================PRIVATES============================
147: private int defaultValue = 0;
148:
149: // the tables have to have prime-number lengths. Rather than compute
150: // primes, we just keep a table, with the current index we are using.
151: private int primeIndex;
152:
153: // highWaterFactor determines the maximum number of elements before
154: // a rehash. Can be tuned for different performance/storage characteristics.
155: private static final float HIGH_WATER_FACTOR = 0.4F;
156: private int highWaterMark;
157:
158: // lowWaterFactor determines the minimum number of elements before
159: // a rehash. Can be tuned for different performance/storage characteristics.
160: private static final float LOW_WATER_FACTOR = 0.0F;
161: private int lowWaterMark;
162:
163: private int count;
164:
165: // we use two arrays to minimize allocations
166: private int[] values;
167: private int[] keyList;
168:
169: private static final int EMPTY = Integer.MIN_VALUE;
170: private static final int DELETED = EMPTY + 1;
171: private static final int MAX_UNUSED = DELETED;
172:
173: private void initialize(int primeIndex) {
174: if (primeIndex < 0) {
175: primeIndex = 0;
176: } else if (primeIndex >= PRIMES.length) {
177: System.out.println("TOO BIG");
178: primeIndex = PRIMES.length - 1;
179: // throw new java.util.IllegalArgumentError();
180: }
181: this .primeIndex = primeIndex;
182: int initialSize = PRIMES[primeIndex];
183: values = new int[initialSize];
184: keyList = new int[initialSize];
185: for (int i = 0; i < initialSize; ++i) {
186: keyList[i] = EMPTY;
187: values[i] = defaultValue;
188: }
189: count = 0;
190: lowWaterMark = (int) (initialSize * LOW_WATER_FACTOR);
191: highWaterMark = (int) (initialSize * HIGH_WATER_FACTOR);
192: }
193:
194: private void rehash() {
195: int[] oldValues = values;
196: int[] oldkeyList = keyList;
197: int newPrimeIndex = primeIndex;
198: if (count > highWaterMark) {
199: ++newPrimeIndex;
200: } else if (count < lowWaterMark) {
201: newPrimeIndex -= 2;
202: }
203: initialize(newPrimeIndex);
204: for (int i = oldValues.length - 1; i >= 0; --i) {
205: int key = oldkeyList[i];
206: if (key > MAX_UNUSED) {
207: putInternal(key, oldValues[i]);
208: }
209: }
210: }
211:
212: public void putInternal(int key, int value) {
213: int index = find(key);
214: if (keyList[index] < MAX_UNUSED) { // deleted or empty
215: keyList[index] = key;
216: ++count;
217: }
218: values[index] = value; // reset value
219: }
220:
221: private int find(int key) {
222: if (key <= MAX_UNUSED)
223: throw new IllegalArgumentException(
224: "key can't be less than 0xFFFFFFFE");
225: int firstDeleted = -1; // assume invalid index
226: int index = (key ^ 0x4000000) % keyList.length;
227: if (index < 0)
228: index = -index; // positive only
229: int jump = 0;
230: while (true) {
231: int tableHash = keyList[index];
232: if (tableHash == key) { // quick check
233: return index;
234: } else if (tableHash > MAX_UNUSED) { // neither correct nor unused
235: // ignore
236: } else if (tableHash == EMPTY) { // empty, end o' the line
237: if (firstDeleted >= 0) {
238: index = firstDeleted; // reset if had deleted slot
239: }
240: return index;
241: } else if (firstDeleted < 0) { // remember first deleted
242: firstDeleted = index;
243: }
244: if (jump == 0) { // lazy compute jump
245: jump = (key % (keyList.length - 1));
246: if (jump < 0)
247: jump = -jump;
248: ++jump;
249: }
250:
251: index = (index + jump) % keyList.length;
252: if (index == firstDeleted) {
253: // We've searched all entries for the given key.
254: return index;
255: }
256: }
257: }
258:
259: private static int leastGreaterPrimeIndex(int source) {
260: int i;
261: for (i = 0; i < PRIMES.length; ++i) {
262: if (source < PRIMES[i]) {
263: break;
264: }
265: }
266: return (i == 0) ? 0 : (i - 1);
267: }
268:
269: // This list is the result of buildList below. Can be tuned for different
270: // performance/storage characteristics.
271: private static final int[] PRIMES = { 17, 37, 67, 131, 257, 521,
272: 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101,
273: 262147, 524309, 1048583, 2097169, 4194319, 8388617,
274: 16777259, 33554467, 67108879, 134217757, 268435459,
275: 536870923, 1073741827, 2147483647 };
276: }
|