001: package com.jclark.util;
002:
003: /**
004: * A more efficient version of <code>java.util.Hashtable</code>
005: * It is not synchronized. It only performs allocation when
006: * the hash table is resized.
007: */
008:
009: public class Hashtable extends java.util.Dictionary {
010: // The first half of table contains the keys, the second half the values.
011: // The value for a key at index i is at index i + halfTableLength
012: private Object[] table;
013: private int halfTableLength;
014: private int used;
015: private int usedLimit;
016: private static final int INIT_SIZE = 16;
017: private static final float LOAD_FACTOR = 0.5f;
018:
019: private final int nextIndex(int i) {
020: return i == 0 ? halfTableLength - 1 : i - 1;
021: }
022:
023: // It might be a good idea to multiple the hashCode by a large prime.
024: private final int firstIndex(Object key) {
025: return key.hashCode() & (halfTableLength - 1);
026: }
027:
028: public Hashtable() {
029: }
030:
031: /**
032: * Creates a hash table with the specified initial capacity.
033: */
034: public Hashtable(int n) {
035: n = (int) ((n + 1) / LOAD_FACTOR);
036: halfTableLength = 1;
037: while (halfTableLength < n)
038: halfTableLength <<= 1;
039: table = new Object[halfTableLength << 1];
040: usedLimit = (int) (n * LOAD_FACTOR);
041: }
042:
043: public final int size() {
044: return used;
045: }
046:
047: public final boolean isEmpty() {
048: return used == 0;
049: }
050:
051: public final Object get(Object key) {
052: if (used != 0) {
053: for (int i = firstIndex(key); table[i] != null; i = nextIndex(i))
054: if (table[i].equals(key))
055: return table[i | halfTableLength];
056: }
057: return null;
058: }
059:
060: public final Object put(Object key, Object value) {
061: if (value == null)
062: throw new NullPointerException();
063: int h;
064: if (table == null) {
065: table = new Object[INIT_SIZE];
066: halfTableLength = INIT_SIZE >> 1;
067: usedLimit = (int) ((INIT_SIZE >> 1) * LOAD_FACTOR);
068: h = firstIndex(key);
069: } else {
070: for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
071: if (key.equals(table[h])) {
072: h |= halfTableLength;
073: Object tem = table[h];
074: table[h] = value;
075: return tem;
076: }
077: }
078: if (used >= usedLimit) {
079: // rehash
080: halfTableLength = table.length;
081: usedLimit = (int) (halfTableLength * LOAD_FACTOR);
082: Object[] oldTable = table;
083: table = new Object[halfTableLength << 1];
084: for (int i = oldTable.length >> 1; i > 0;) {
085: --i;
086: if (oldTable[i] != null) {
087: int j;
088: for (j = firstIndex(oldTable[i]); table[j] != null; j = nextIndex(j))
089: ;
090: table[j] = oldTable[i];
091: // copy the value
092: table[j | halfTableLength] = oldTable[i
093: + (oldTable.length >> 1)];
094: }
095: }
096: for (h = firstIndex(key); table[h] != null; h = nextIndex(h))
097: ;
098: }
099: used++;
100: table[h] = key;
101: table[h | halfTableLength] = value;
102: return null;
103: }
104:
105: private static class Enumerator implements java.util.Enumeration {
106: private final Object[] table;
107: private final int add;
108: private int i;
109:
110: Enumerator(Object[] table, int add) {
111: this .table = table;
112: this .add = add;
113: if (table == null)
114: i = -1;
115: else {
116: i = (table.length >> 1);
117: while (--i >= 0 && table[i] == null)
118: ;
119: }
120: }
121:
122: public boolean hasMoreElements() {
123: return i >= 0;
124: }
125:
126: public Object nextElement() {
127: if (i < 0)
128: throw new java.util.NoSuchElementException();
129: Object tem = table[i + add];
130: while (--i >= 0 && table[i] == null)
131: ;
132: return tem;
133: }
134: }
135:
136: public final java.util.Enumeration keys() {
137: return new Enumerator(table, 0);
138: }
139:
140: public final java.util.Enumeration elements() {
141: return new Enumerator(table, halfTableLength);
142: }
143:
144: /**
145: * Removes the object with the specified key from the table.
146: * Returns the object removed or null if there was no such object
147: * in the table.
148: */
149: public final Object remove(Object key) {
150: if (used > 0) {
151: for (int i = firstIndex(key); table[i] != null; i = nextIndex(i))
152: if (table[i].equals(key)) {
153: Object obj = table[i];
154: do {
155: table[i] = null;
156: table[i | halfTableLength] = null;
157: int j = i;
158: int r;
159: do {
160: i = nextIndex(i);
161: if (table[i] == null)
162: break;
163: r = firstIndex(table[i]);
164: } while ((i <= r && r < j) || (r < j && j < i)
165: || (j < i && i <= r));
166: table[j] = table[i];
167: table[j | halfTableLength] = table[i
168: | halfTableLength];
169: } while (table[i] != null);
170: --used;
171: return obj;
172: }
173: }
174: return null;
175: }
176:
177: /**
178: * Removes all objects from the hash table, so that the hash table
179: * becomes empty.
180: */
181: public final void clear() {
182: int i = halfTableLength;
183: while (--i >= 0) {
184: table[i] = null;
185: table[i | halfTableLength] = null;
186: }
187: used = 0;
188: }
189: }
|