001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 Søren Bak
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019: package bak.pcj.map;
020:
021: import bak.pcj.CharIterator;
022: import bak.pcj.AbstractCharCollection;
023: import bak.pcj.set.AbstractCharSet;
024: import bak.pcj.set.CharSet;
025: import bak.pcj.hash.CharHashFunction;
026: import bak.pcj.hash.DefaultCharHashFunction;
027: import bak.pcj.util.Exceptions;
028:
029: import java.util.Collection;
030: import java.util.AbstractCollection;
031: import java.util.Iterator;
032:
033: import java.io.Serializable;
034: import java.io.IOException;
035: import java.io.ObjectInputStream;
036: import java.io.ObjectOutputStream;
037:
038: /**
039: * This class represents open addressing hash table based maps from
040: * char values to objects.
041: *
042: * @see CharKeyChainedHashMap
043: * @see java.util.Map
044: *
045: * @author Søren Bak
046: * @version 1.3 21-08-2003 19:45
047: * @since 1.0
048: */
049: public class CharKeyOpenHashMap extends AbstractCharKeyMap implements
050: CharKeyMap, Cloneable, Serializable {
051:
052: /** Constant indicating relative growth policy. */
053: private static final int GROWTH_POLICY_RELATIVE = 0;
054:
055: /** Constant indicating absolute growth policy. */
056: private static final int GROWTH_POLICY_ABSOLUTE = 1;
057:
058: /**
059: * The default growth policy of this map.
060: * @see #GROWTH_POLICY_RELATIVE
061: * @see #GROWTH_POLICY_ABSOLUTE
062: */
063: private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
064:
065: /** The default factor with which to increase the capacity of this map. */
066: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
067:
068: /** The default chunk size with which to increase the capacity of this map. */
069: public static final int DEFAULT_GROWTH_CHUNK = 10;
070:
071: /** The default capacity of this map. */
072: public static final int DEFAULT_CAPACITY = 11;
073:
074: /** The default load factor of this map. */
075: public static final double DEFAULT_LOAD_FACTOR = 0.75;
076:
077: /**
078: * The hash function used to hash keys in this map.
079: * @serial
080: */
081: private CharHashFunction keyhash;
082:
083: /**
084: * The size of this map.
085: * @serial
086: */
087: private int size;
088:
089: /**
090: * The keys of this map. Contains key values directly.
091: * Due to the use of a secondary hash function, the length of this
092: * array must be a prime.
093: */
094: private transient char[] keys;
095:
096: /**
097: * The values of this map. Contains values directly.
098: * Due to the use of a secondary hash function, the length of this
099: * array must be a prime.
100: */
101: private transient Object[] values;
102:
103: /** The states of each cell in the keys[] and values[]. */
104: private transient byte[] states;
105:
106: private static final byte EMPTY = 0;
107: private static final byte OCCUPIED = 1;
108: private static final byte REMOVED = 2;
109:
110: /** The number of entries in use (removed or occupied). */
111: private transient int used;
112:
113: /**
114: * The growth policy of this map (0 is relative growth, 1 is absolute growth).
115: * @serial
116: */
117: private int growthPolicy;
118:
119: /**
120: * The growth factor of this map, if the growth policy is
121: * relative.
122: * @serial
123: */
124: private double growthFactor;
125:
126: /**
127: * The growth chunk size of this map, if the growth policy is
128: * absolute.
129: * @serial
130: */
131: private int growthChunk;
132:
133: /**
134: * The load factor of this map.
135: * @serial
136: */
137: private double loadFactor;
138:
139: /**
140: * The next size at which to expand the data[].
141: * @serial
142: */
143: private int expandAt;
144:
145: /** A set view of the keys of this map. */
146: private transient CharSet ckeys;
147:
148: /** A collection view of the values of this map. */
149: private transient Collection cvalues;
150:
151: private CharKeyOpenHashMap(CharHashFunction keyhash, int capacity,
152: int growthPolicy, double growthFactor, int growthChunk,
153: double loadFactor) {
154: if (keyhash == null)
155: Exceptions.nullArgument("hash function");
156: if (capacity < 0)
157: Exceptions.negativeArgument("capacity", String
158: .valueOf(capacity));
159: if (growthFactor <= 0.0)
160: Exceptions.negativeOrZeroArgument("growthFactor", String
161: .valueOf(growthFactor));
162: if (growthChunk <= 0)
163: Exceptions.negativeOrZeroArgument("growthChunk", String
164: .valueOf(growthChunk));
165: if (loadFactor <= 0.0)
166: Exceptions.negativeOrZeroArgument("loadFactor", String
167: .valueOf(loadFactor));
168: this .keyhash = keyhash;
169: capacity = bak.pcj.hash.Primes.nextPrime(capacity);
170: keys = new char[capacity];
171: values = new Object[capacity];
172: this .states = new byte[capacity];
173: size = 0;
174: expandAt = (int) Math.round(loadFactor * capacity);
175: this .used = 0;
176: this .growthPolicy = growthPolicy;
177: this .growthFactor = growthFactor;
178: this .growthChunk = growthChunk;
179: this .loadFactor = loadFactor;
180: }
181:
182: private CharKeyOpenHashMap(int capacity, int growthPolicy,
183: double growthFactor, int growthChunk, double loadFactor) {
184: this (DefaultCharHashFunction.INSTANCE, capacity, growthPolicy,
185: growthFactor, growthChunk, loadFactor);
186: }
187:
188: /**
189: * Creates a new hash map with capacity 11, a relative
190: * growth factor of 1.0, and a load factor of 75%.
191: */
192: public CharKeyOpenHashMap() {
193: this (DEFAULT_CAPACITY);
194: }
195:
196: /**
197: * Creates a new hash map with the same mappings as a specified map.
198: *
199: * @param map
200: * the map whose mappings to put into the new map.
201: *
202: * @throws NullPointerException
203: * if <tt>map</tt> is <tt>null</tt>.
204: */
205: public CharKeyOpenHashMap(CharKeyMap map) {
206: this ();
207: putAll(map);
208: }
209:
210: /**
211: * Creates a new hash map with a specified capacity, a relative
212: * growth factor of 1.0, and a load factor of 75%.
213: *
214: * @param capacity
215: * the initial capacity of the map.
216: *
217: * @throws IllegalArgumentException
218: * if <tt>capacity</tt> is negative.
219: */
220: public CharKeyOpenHashMap(int capacity) {
221: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
222: DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
223: }
224:
225: /**
226: * Creates a new hash map with a capacity of 11, a relative
227: * growth factor of 1.0, and a specified load factor.
228: *
229: * @param loadFactor
230: * the load factor of the map.
231: *
232: * @throws IllegalArgumentException
233: * if <tt>capacity</tt> is negative;
234: * if <tt>loadFactor</tt> is not positive.
235: */
236: public CharKeyOpenHashMap(double loadFactor) {
237: this (DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
238: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
239: }
240:
241: /**
242: * Creates a new hash map with a specified capacity and
243: * load factor, and a relative growth factor of 1.0.
244: *
245: * @param capacity
246: * the initial capacity of the map.
247: *
248: * @param loadFactor
249: * the load factor of the map.
250: *
251: * @throws IllegalArgumentException
252: * if <tt>capacity</tt> is negative;
253: * if <tt>loadFactor</tt> is not positive.
254: */
255: public CharKeyOpenHashMap(int capacity, double loadFactor) {
256: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
257: DEFAULT_GROWTH_CHUNK, loadFactor);
258: }
259:
260: /**
261: * Creates a new hash map with a specified capacity,
262: * load factor, and relative growth factor.
263: *
264: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
265: * This strategy is good for avoiding many capacity increases, but
266: * the amount of wasted memory is approximately the size of the map.
267: *
268: * @param capacity
269: * the initial capacity of the map.
270: *
271: * @param loadFactor
272: * the load factor of the map.
273: *
274: * @param growthFactor
275: * the relative amount with which to increase the
276: * the capacity when a capacity increase is needed.
277: *
278: * @throws IllegalArgumentException
279: * if <tt>capacity</tt> is negative;
280: * if <tt>loadFactor</tt> is not positive;
281: * if <tt>growthFactor</tt> is not positive.
282: */
283: public CharKeyOpenHashMap(int capacity, double loadFactor,
284: double growthFactor) {
285: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
286: DEFAULT_GROWTH_CHUNK, loadFactor);
287: }
288:
289: /**
290: * Creates a new hash map with a specified capacity,
291: * load factor, and absolute growth factor.
292: *
293: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
294: * This strategy is good for avoiding wasting memory. However, an
295: * overhead is potentially introduced by frequent capacity increases.
296: *
297: * @param capacity
298: * the initial capacity of the map.
299: *
300: * @param loadFactor
301: * the load factor of the map.
302: *
303: * @param growthChunk
304: * the absolute amount with which to increase the
305: * the capacity when a capacity increase is needed.
306: *
307: * @throws IllegalArgumentException
308: * if <tt>capacity</tt> is negative;
309: * if <tt>loadFactor</tt> is not positive;
310: * if <tt>growthChunk</tt> is not positive.
311: */
312: public CharKeyOpenHashMap(int capacity, double loadFactor,
313: int growthChunk) {
314: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
315: growthChunk, loadFactor);
316: }
317:
318: // ---------------------------------------------------------------
319: // Constructors with hash function argument
320: // ---------------------------------------------------------------
321:
322: /**
323: * Creates a new hash map with capacity 11, a relative
324: * growth factor of 1.0, and a load factor of 75%.
325: *
326: * @param keyhash
327: * the hash function to use when hashing keys.
328: *
329: * @throws NullPointerException
330: * if <tt>keyhash</tt> is <tt>null</tt>.
331: */
332: public CharKeyOpenHashMap(CharHashFunction keyhash) {
333: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
334: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
335: DEFAULT_LOAD_FACTOR);
336: }
337:
338: /**
339: * Creates a new hash map with a specified capacity, a relative
340: * growth factor of 1.0, and a load factor of 75%.
341: *
342: * @param keyhash
343: * the hash function to use when hashing keys.
344: *
345: * @param capacity
346: * the initial capacity of the map.
347: *
348: * @throws IllegalArgumentException
349: * if <tt>capacity</tt> is negative.
350: *
351: * @throws NullPointerException
352: * if <tt>keyhash</tt> is <tt>null</tt>.
353: */
354: public CharKeyOpenHashMap(CharHashFunction keyhash, int capacity) {
355: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
356: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
357: DEFAULT_LOAD_FACTOR);
358: }
359:
360: /**
361: * Creates a new hash map with a capacity of 11, a relative
362: * growth factor of 1.0, and a specified load factor.
363: *
364: * @param keyhash
365: * the hash function to use when hashing keys.
366: *
367: * @param loadFactor
368: * the load factor of the map.
369: *
370: * @throws IllegalArgumentException
371: * if <tt>capacity</tt> is negative;
372: * if <tt>loadFactor</tt> is not positive.
373: *
374: * @throws NullPointerException
375: * if <tt>keyhash</tt> is <tt>null</tt>.
376: */
377: public CharKeyOpenHashMap(CharHashFunction keyhash,
378: double loadFactor) {
379: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
380: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
381: }
382:
383: /**
384: * Creates a new hash map with a specified capacity and
385: * load factor, and a relative growth factor of 1.0.
386: *
387: * @param keyhash
388: * the hash function to use when hashing keys.
389: *
390: * @param capacity
391: * the initial capacity of the map.
392: *
393: * @param loadFactor
394: * the load factor of the map.
395: *
396: * @throws IllegalArgumentException
397: * if <tt>capacity</tt> is negative;
398: * if <tt>loadFactor</tt> is not positive.
399: *
400: * @throws NullPointerException
401: * if <tt>keyhash</tt> is <tt>null</tt>.
402: */
403: public CharKeyOpenHashMap(CharHashFunction keyhash, int capacity,
404: double loadFactor) {
405: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
406: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
407: }
408:
409: /**
410: * Creates a new hash map with a specified capacity,
411: * load factor, and relative growth factor.
412: *
413: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
414: * This strategy is good for avoiding many capacity increases, but
415: * the amount of wasted memory is approximately the size of the map.
416: *
417: * @param keyhash
418: * the hash function to use when hashing keys.
419: *
420: * @param capacity
421: * the initial capacity of the map.
422: *
423: * @param loadFactor
424: * the load factor of the map.
425: *
426: * @param growthFactor
427: * the relative amount with which to increase the
428: * the capacity when a capacity increase is needed.
429: *
430: * @throws IllegalArgumentException
431: * if <tt>capacity</tt> is negative;
432: * if <tt>loadFactor</tt> is not positive;
433: * if <tt>growthFactor</tt> is not positive.
434: *
435: * @throws NullPointerException
436: * if <tt>keyhash</tt> is <tt>null</tt>.
437: */
438: public CharKeyOpenHashMap(CharHashFunction keyhash, int capacity,
439: double loadFactor, double growthFactor) {
440: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
441: DEFAULT_GROWTH_CHUNK, loadFactor);
442: }
443:
444: /**
445: * Creates a new hash map with a specified capacity,
446: * load factor, and absolute growth factor.
447: *
448: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
449: * This strategy is good for avoiding wasting memory. However, an
450: * overhead is potentially introduced by frequent capacity increases.
451: *
452: * @param keyhash
453: * the hash function to use when hashing keys.
454: *
455: * @param capacity
456: * the initial capacity of the map.
457: *
458: * @param loadFactor
459: * the load factor of the map.
460: *
461: * @param growthChunk
462: * the absolute amount with which to increase the
463: * the capacity when a capacity increase is needed.
464: *
465: * @throws IllegalArgumentException
466: * if <tt>capacity</tt> is negative;
467: * if <tt>loadFactor</tt> is not positive;
468: * if <tt>growthChunk</tt> is not positive.
469: *
470: * @throws NullPointerException
471: * if <tt>keyhash</tt> is <tt>null</tt>.
472: */
473: public CharKeyOpenHashMap(CharHashFunction keyhash, int capacity,
474: double loadFactor, int growthChunk) {
475: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
476: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
477: }
478:
479: // ---------------------------------------------------------------
480: // Hash table management
481: // ---------------------------------------------------------------
482:
483: private void ensureCapacity(int elements) {
484: if (elements >= expandAt) {
485: int newcapacity;
486: if (growthPolicy == GROWTH_POLICY_RELATIVE)
487: newcapacity = (int) (keys.length * (1.0 + growthFactor));
488: else
489: newcapacity = keys.length + growthChunk;
490: if (newcapacity * loadFactor < elements)
491: newcapacity = (int) Math
492: .round(((double) elements / loadFactor));
493: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
494: expandAt = (int) Math.round(loadFactor * newcapacity);
495:
496: char[] newkeys = new char[newcapacity];
497: Object[] newvalues = new Object[newcapacity];
498: byte[] newstates = new byte[newcapacity];
499:
500: used = 0;
501: // re-hash
502: for (int i = 0; i < keys.length; i++) {
503: if (states[i] == OCCUPIED) {
504: used++;
505: char k = keys[i];
506: Object v = values[i];
507: // first hash
508: int h = Math.abs(keyhash.hash(k));
509: int n = h % newcapacity;
510: if (newstates[n] == OCCUPIED) {
511: // second hash
512: int c = 1 + (h % (newcapacity - 2));
513: for (;;) {
514: n -= c;
515: if (n < 0)
516: n += newcapacity;
517: if (newstates[n] == EMPTY)
518: break;
519: }
520: }
521: newstates[n] = OCCUPIED;
522: newvalues[n] = v;
523: newkeys[n] = k;
524: }
525: }
526:
527: keys = newkeys;
528: values = newvalues;
529: states = newstates;
530: }
531: }
532:
533: // ---------------------------------------------------------------
534: // Operations not supported by abstract implementation
535: // ---------------------------------------------------------------
536:
537: public CharSet keySet() {
538: if (ckeys == null)
539: ckeys = new KeySet();
540: return ckeys;
541: }
542:
543: public Object put(char key, Object value) {
544: Object result;
545:
546: // first hash
547: int h = Math.abs(keyhash.hash(key));
548: int i = h % keys.length;
549: if (states[i] == OCCUPIED) {
550: if (keys[i] == key) {
551: Object oldValue = values[i];
552: values[i] = value;
553: return oldValue;
554: }
555: // second hash
556: int c = 1 + (h % (keys.length - 2));
557: for (;;) {
558: i -= c;
559: if (i < 0)
560: i += keys.length;
561: // Empty entries are re-used
562: if (states[i] == EMPTY || states[i] == REMOVED)
563: break;
564: if (states[i] == OCCUPIED && keys[i] == key) {
565: Object oldValue = values[i];
566: values[i] = value;
567: return oldValue;
568: }
569: }
570: }
571:
572: if (states[i] == EMPTY)
573: used++;
574: states[i] = OCCUPIED;
575: keys[i] = key;
576: values[i] = value;
577: size++;
578: ensureCapacity(used);
579: return null;
580: }
581:
582: public Collection values() {
583: if (cvalues == null)
584: cvalues = new ValueCollection();
585: return cvalues;
586: }
587:
588: /**
589: * Returns a clone of this hash map.
590: *
591: * @return a clone of this hash map.
592: *
593: * @since 1.1
594: */
595: public Object clone() {
596: try {
597: CharKeyOpenHashMap c = (CharKeyOpenHashMap) super .clone();
598: c.keys = new char[keys.length];
599: System.arraycopy(keys, 0, c.keys, 0, keys.length);
600: c.values = new Object[values.length];
601: System.arraycopy(values, 0, c.values, 0, values.length);
602: c.states = new byte[states.length];
603: System.arraycopy(states, 0, c.states, 0, states.length);
604: // The views should not refer to this map's views
605: c.cvalues = null;
606: c.ckeys = null;
607: return c;
608: } catch (CloneNotSupportedException e) {
609: Exceptions.cloning();
610: return null;
611: }
612: }
613:
614: public CharKeyMapIterator entries() {
615: return new CharKeyMapIterator() {
616: int nextEntry = nextEntry(0);
617: int lastEntry = -1;
618:
619: int nextEntry(int index) {
620: while (index < keys.length && states[index] != OCCUPIED)
621: index++;
622: return index;
623: }
624:
625: public boolean hasNext() {
626: return nextEntry < keys.length;
627: }
628:
629: public void next() {
630: if (!hasNext())
631: Exceptions.endOfIterator();
632: lastEntry = nextEntry;
633: nextEntry = nextEntry(nextEntry + 1);
634: }
635:
636: public void remove() {
637: if (lastEntry == -1)
638: Exceptions.noElementToRemove();
639: states[lastEntry] = REMOVED;
640: values[lastEntry] = null; // GC
641: size--;
642: lastEntry = -1;
643: }
644:
645: public char getKey() {
646: if (lastEntry == -1)
647: Exceptions.noElementToGet();
648: return keys[lastEntry];
649: }
650:
651: public Object getValue() {
652: if (lastEntry == -1)
653: Exceptions.noElementToGet();
654: return values[lastEntry];
655: }
656: };
657: }
658:
659: private class KeySet extends AbstractCharSet {
660:
661: public void clear() {
662: CharKeyOpenHashMap.this .clear();
663: }
664:
665: public boolean contains(char v) {
666: return containsKey(v);
667: }
668:
669: public CharIterator iterator() {
670: return new CharIterator() {
671: int nextEntry = nextEntry(0);
672: int lastEntry = -1;
673:
674: int nextEntry(int index) {
675: while (index < keys.length
676: && states[index] != OCCUPIED)
677: index++;
678: return index;
679: }
680:
681: public boolean hasNext() {
682: return nextEntry < keys.length;
683: }
684:
685: public char next() {
686: if (!hasNext())
687: Exceptions.endOfIterator();
688: lastEntry = nextEntry;
689: nextEntry = nextEntry(nextEntry + 1);
690: return keys[lastEntry];
691: }
692:
693: public void remove() {
694: if (lastEntry == -1)
695: Exceptions.noElementToRemove();
696: states[lastEntry] = REMOVED;
697: values[lastEntry] = null; // GC
698: size--;
699: lastEntry = -1;
700: }
701: };
702: }
703:
704: public boolean remove(char v) {
705: boolean result = containsKey(v);
706: if (result)
707: CharKeyOpenHashMap.this .remove(v);
708: return result;
709: }
710:
711: public int size() {
712: return size;
713: }
714:
715: }
716:
717: private class ValueCollection extends AbstractCollection {
718:
719: public void clear() {
720: CharKeyOpenHashMap.this .clear();
721: }
722:
723: public boolean contains(Object v) {
724: return containsValue(v);
725: }
726:
727: public Iterator iterator() {
728: return new Iterator() {
729: int nextEntry = nextEntry(0);
730: int lastEntry = -1;
731:
732: int nextEntry(int index) {
733: while (index < keys.length
734: && states[index] != OCCUPIED)
735: index++;
736: return index;
737: }
738:
739: public boolean hasNext() {
740: return nextEntry < keys.length;
741: }
742:
743: public Object next() {
744: if (!hasNext())
745: Exceptions.endOfIterator();
746: lastEntry = nextEntry;
747: nextEntry = nextEntry(nextEntry + 1);
748: return values[lastEntry];
749: }
750:
751: public void remove() {
752: if (lastEntry == -1)
753: Exceptions.noElementToRemove();
754: states[lastEntry] = REMOVED;
755: values[lastEntry] = null; // GC
756: size--;
757: lastEntry = -1;
758: }
759: };
760: }
761:
762: public int size() {
763: return size;
764: }
765:
766: }
767:
768: // ---------------------------------------------------------------
769: // Operations overwritten for efficiency
770: // ---------------------------------------------------------------
771:
772: public void clear() {
773: java.util.Arrays.fill(states, EMPTY);
774: java.util.Arrays.fill(values, null); // GC
775: size = 0;
776: used = 0;
777: }
778:
779: public boolean containsKey(char key) {
780: int h = Math.abs(keyhash.hash(key));
781: int i = h % keys.length;
782: if (states[i] != EMPTY) {
783: if (states[i] == OCCUPIED && keys[i] == key)
784: return true;
785:
786: // second hash
787: int c = 1 + (h % (keys.length - 2));
788: for (;;) {
789: i -= c;
790: if (i < 0)
791: i += keys.length;
792: if (states[i] == EMPTY)
793: return false;
794: if (states[i] == OCCUPIED && keys[i] == key)
795: return true;
796: }
797: }
798: return false;
799: }
800:
801: public boolean containsValue(Object value) {
802: if (value == null) {
803: for (int i = 0; i < states.length; i++)
804: if (states[i] == OCCUPIED && values[i] == null)
805: return true;
806: } else {
807: for (int i = 0; i < states.length; i++)
808: if (states[i] == OCCUPIED && value.equals(values[i]))
809: return true;
810: }
811: return false;
812: }
813:
814: public Object get(char key) {
815: int h = Math.abs(keyhash.hash(key));
816: int i = h % keys.length;
817: if (states[i] != EMPTY) {
818: if (states[i] == OCCUPIED && keys[i] == key)
819: return values[i];
820: // second hash
821:
822: int c = 1 + (h % (keys.length - 2));
823: for (;;) {
824: i -= c;
825: if (i < 0)
826: i += keys.length;
827: if (states[i] == EMPTY)
828: return null;
829: if (states[i] == OCCUPIED && keys[i] == key)
830: return values[i];
831: }
832: }
833: return null;
834: }
835:
836: public boolean isEmpty() {
837: return size == 0;
838: }
839:
840: public Object remove(char key) {
841: int h = Math.abs(keyhash.hash(key));
842: int i = h % keys.length;
843: if (states[i] != EMPTY) {
844: if (states[i] == OCCUPIED && keys[i] == key) {
845: Object oldValue = values[i];
846: values[i] = null; // GC
847: states[i] = REMOVED;
848: size--;
849: return oldValue;
850: }
851: // second hash
852: int c = 1 + (h % (keys.length - 2));
853: for (;;) {
854: i -= c;
855: if (i < 0)
856: i += keys.length;
857: if (states[i] == EMPTY) {
858: return null;
859: }
860: if (states[i] == OCCUPIED && keys[i] == key) {
861: Object oldValue = values[i];
862: values[i] = null; // GC
863: states[i] = REMOVED;
864: size--;
865: return oldValue;
866: }
867: }
868: }
869: return null;
870: }
871:
872: public int size() {
873: return size;
874: }
875:
876: // ---------------------------------------------------------------
877: // Serialization
878: // ---------------------------------------------------------------
879:
880: /**
881: * @serialData Default fields; the capacity of the
882: * map (<tt>int</tt>); the maps's entries
883: * (<tt>char</tt>, <tt>Object</tt>).
884: *
885: * @since 1.1
886: */
887: private void writeObject(ObjectOutputStream s) throws IOException {
888: s.defaultWriteObject();
889: s.writeInt(keys.length);
890: CharKeyMapIterator i = entries();
891: while (i.hasNext()) {
892: i.next();
893: s.writeChar(i.getKey());
894: s.writeObject(i.getValue());
895: }
896: }
897:
898: /**
899: * @since 1.1
900: */
901: private void readObject(ObjectInputStream s) throws IOException,
902: ClassNotFoundException {
903: s.defaultReadObject();
904: keys = new char[s.readInt()];
905: states = new byte[keys.length];
906: values = new Object[keys.length];
907: used = size;
908:
909: for (int n = 0; n < size; n++) {
910: char key = s.readChar();
911: Object value = s.readObject();
912:
913: // first hash
914: int h = Math.abs(keyhash.hash(key));
915: int i = h % keys.length;
916: if (states[i] != EMPTY) {
917: // second hash
918: int c = 1 + (h % (keys.length - 2));
919: for (;;) {
920: i -= c;
921: if (i < 0)
922: i += keys.length;
923: if (states[i] == EMPTY)
924: break;
925: }
926: }
927: states[i] = OCCUPIED;
928: keys[i] = key;
929: values[i] = value;
930: }
931: }
932:
933: }
|