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.IntIterator;
022: import bak.pcj.AbstractIntCollection;
023: import bak.pcj.set.AbstractIntSet;
024: import bak.pcj.set.IntSet;
025: import bak.pcj.hash.IntHashFunction;
026: import bak.pcj.hash.DefaultIntHashFunction;
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: * int values to objects.
041: *
042: * @see IntKeyChainedHashMap
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 IntKeyOpenHashMap extends AbstractIntKeyMap implements
050: IntKeyMap, 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 IntHashFunction 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 int[] 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 IntSet ckeys;
147:
148: /** A collection view of the values of this map. */
149: private transient Collection cvalues;
150:
151: private IntKeyOpenHashMap(IntHashFunction 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 int[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 IntKeyOpenHashMap(int capacity, int growthPolicy,
183: double growthFactor, int growthChunk, double loadFactor) {
184: this (DefaultIntHashFunction.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 IntKeyOpenHashMap() {
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 IntKeyOpenHashMap(IntKeyMap 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 IntKeyOpenHashMap(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 IntKeyOpenHashMap(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 IntKeyOpenHashMap(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 IntKeyOpenHashMap(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 IntKeyOpenHashMap(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 IntKeyOpenHashMap(IntHashFunction 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 IntKeyOpenHashMap(IntHashFunction 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 IntKeyOpenHashMap(IntHashFunction keyhash, double loadFactor) {
378: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
379: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
380: }
381:
382: /**
383: * Creates a new hash map with a specified capacity and
384: * load factor, and a relative growth factor of 1.0.
385: *
386: * @param keyhash
387: * the hash function to use when hashing keys.
388: *
389: * @param capacity
390: * the initial capacity of the map.
391: *
392: * @param loadFactor
393: * the load factor of the map.
394: *
395: * @throws IllegalArgumentException
396: * if <tt>capacity</tt> is negative;
397: * if <tt>loadFactor</tt> is not positive.
398: *
399: * @throws NullPointerException
400: * if <tt>keyhash</tt> is <tt>null</tt>.
401: */
402: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
403: double loadFactor) {
404: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
405: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
406: }
407:
408: /**
409: * Creates a new hash map with a specified capacity,
410: * load factor, and relative growth factor.
411: *
412: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
413: * This strategy is good for avoiding many capacity increases, but
414: * the amount of wasted memory is approximately the size of the map.
415: *
416: * @param keyhash
417: * the hash function to use when hashing keys.
418: *
419: * @param capacity
420: * the initial capacity of the map.
421: *
422: * @param loadFactor
423: * the load factor of the map.
424: *
425: * @param growthFactor
426: * the relative amount with which to increase the
427: * the capacity when a capacity increase is needed.
428: *
429: * @throws IllegalArgumentException
430: * if <tt>capacity</tt> is negative;
431: * if <tt>loadFactor</tt> is not positive;
432: * if <tt>growthFactor</tt> is not positive.
433: *
434: * @throws NullPointerException
435: * if <tt>keyhash</tt> is <tt>null</tt>.
436: */
437: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
438: double loadFactor, double growthFactor) {
439: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
440: DEFAULT_GROWTH_CHUNK, loadFactor);
441: }
442:
443: /**
444: * Creates a new hash map with a specified capacity,
445: * load factor, and absolute growth factor.
446: *
447: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
448: * This strategy is good for avoiding wasting memory. However, an
449: * overhead is potentially introduced by frequent capacity increases.
450: *
451: * @param keyhash
452: * the hash function to use when hashing keys.
453: *
454: * @param capacity
455: * the initial capacity of the map.
456: *
457: * @param loadFactor
458: * the load factor of the map.
459: *
460: * @param growthChunk
461: * the absolute amount with which to increase the
462: * the capacity when a capacity increase is needed.
463: *
464: * @throws IllegalArgumentException
465: * if <tt>capacity</tt> is negative;
466: * if <tt>loadFactor</tt> is not positive;
467: * if <tt>growthChunk</tt> is not positive.
468: *
469: * @throws NullPointerException
470: * if <tt>keyhash</tt> is <tt>null</tt>.
471: */
472: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
473: double loadFactor, int growthChunk) {
474: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
475: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
476: }
477:
478: // ---------------------------------------------------------------
479: // Hash table management
480: // ---------------------------------------------------------------
481:
482: private void ensureCapacity(int elements) {
483: if (elements >= expandAt) {
484: int newcapacity;
485: if (growthPolicy == GROWTH_POLICY_RELATIVE)
486: newcapacity = (int) (keys.length * (1.0 + growthFactor));
487: else
488: newcapacity = keys.length + growthChunk;
489: if (newcapacity * loadFactor < elements)
490: newcapacity = (int) Math
491: .round(((double) elements / loadFactor));
492: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
493: expandAt = (int) Math.round(loadFactor * newcapacity);
494:
495: int[] newkeys = new int[newcapacity];
496: Object[] newvalues = new Object[newcapacity];
497: byte[] newstates = new byte[newcapacity];
498:
499: used = 0;
500: // re-hash
501: for (int i = 0; i < keys.length; i++) {
502: if (states[i] == OCCUPIED) {
503: used++;
504: int k = keys[i];
505: Object v = values[i];
506: // first hash
507: int h = Math.abs(keyhash.hash(k));
508: int n = h % newcapacity;
509: if (newstates[n] == OCCUPIED) {
510: // second hash
511: int c = 1 + (h % (newcapacity - 2));
512: for (;;) {
513: n -= c;
514: if (n < 0)
515: n += newcapacity;
516: if (newstates[n] == EMPTY)
517: break;
518: }
519: }
520: newstates[n] = OCCUPIED;
521: newvalues[n] = v;
522: newkeys[n] = k;
523: }
524: }
525:
526: keys = newkeys;
527: values = newvalues;
528: states = newstates;
529: }
530: }
531:
532: // ---------------------------------------------------------------
533: // Operations not supported by abstract implementation
534: // ---------------------------------------------------------------
535:
536: public IntSet keySet() {
537: if (ckeys == null)
538: ckeys = new KeySet();
539: return ckeys;
540: }
541:
542: public Object put(int key, Object value) {
543: Object result;
544:
545: // first hash
546: int h = Math.abs(keyhash.hash(key));
547: int i = h % keys.length;
548: if (states[i] == OCCUPIED) {
549: if (keys[i] == key) {
550: Object oldValue = values[i];
551: values[i] = value;
552: return oldValue;
553: }
554: // second hash
555: int c = 1 + (h % (keys.length - 2));
556: for (;;) {
557: i -= c;
558: if (i < 0)
559: i += keys.length;
560: // Empty entries are re-used
561: if (states[i] == EMPTY || states[i] == REMOVED)
562: break;
563: if (states[i] == OCCUPIED && keys[i] == key) {
564: Object oldValue = values[i];
565: values[i] = value;
566: return oldValue;
567: }
568: }
569: }
570:
571: if (states[i] == EMPTY)
572: used++;
573: states[i] = OCCUPIED;
574: keys[i] = key;
575: values[i] = value;
576: size++;
577: ensureCapacity(used);
578: return null;
579: }
580:
581: public Collection values() {
582: if (cvalues == null)
583: cvalues = new ValueCollection();
584: return cvalues;
585: }
586:
587: /**
588: * Returns a clone of this hash map.
589: *
590: * @return a clone of this hash map.
591: *
592: * @since 1.1
593: */
594: public Object clone() {
595: try {
596: IntKeyOpenHashMap c = (IntKeyOpenHashMap) super .clone();
597: c.keys = new int[keys.length];
598: System.arraycopy(keys, 0, c.keys, 0, keys.length);
599: c.values = new Object[values.length];
600: System.arraycopy(values, 0, c.values, 0, values.length);
601: c.states = new byte[states.length];
602: System.arraycopy(states, 0, c.states, 0, states.length);
603: // The views should not refer to this map's views
604: c.cvalues = null;
605: c.ckeys = null;
606: return c;
607: } catch (CloneNotSupportedException e) {
608: Exceptions.cloning();
609: return null;
610: }
611: }
612:
613: public IntKeyMapIterator entries() {
614: return new IntKeyMapIterator() {
615: int nextEntry = nextEntry(0);
616: int lastEntry = -1;
617:
618: int nextEntry(int index) {
619: while (index < keys.length && states[index] != OCCUPIED)
620: index++;
621: return index;
622: }
623:
624: public boolean hasNext() {
625: return nextEntry < keys.length;
626: }
627:
628: public void next() {
629: if (!hasNext())
630: Exceptions.endOfIterator();
631: lastEntry = nextEntry;
632: nextEntry = nextEntry(nextEntry + 1);
633: }
634:
635: public void remove() {
636: if (lastEntry == -1)
637: Exceptions.noElementToRemove();
638: states[lastEntry] = REMOVED;
639: values[lastEntry] = null; // GC
640: size--;
641: lastEntry = -1;
642: }
643:
644: public int getKey() {
645: if (lastEntry == -1)
646: Exceptions.noElementToGet();
647: return keys[lastEntry];
648: }
649:
650: public Object getValue() {
651: if (lastEntry == -1)
652: Exceptions.noElementToGet();
653: return values[lastEntry];
654: }
655: };
656: }
657:
658: private class KeySet extends AbstractIntSet {
659:
660: public void clear() {
661: IntKeyOpenHashMap.this .clear();
662: }
663:
664: public boolean contains(int v) {
665: return containsKey(v);
666: }
667:
668: public IntIterator iterator() {
669: return new IntIterator() {
670: int nextEntry = nextEntry(0);
671: int lastEntry = -1;
672:
673: int nextEntry(int index) {
674: while (index < keys.length
675: && states[index] != OCCUPIED)
676: index++;
677: return index;
678: }
679:
680: public boolean hasNext() {
681: return nextEntry < keys.length;
682: }
683:
684: public int next() {
685: if (!hasNext())
686: Exceptions.endOfIterator();
687: lastEntry = nextEntry;
688: nextEntry = nextEntry(nextEntry + 1);
689: return keys[lastEntry];
690: }
691:
692: public void remove() {
693: if (lastEntry == -1)
694: Exceptions.noElementToRemove();
695: states[lastEntry] = REMOVED;
696: values[lastEntry] = null; // GC
697: size--;
698: lastEntry = -1;
699: }
700: };
701: }
702:
703: public boolean remove(int v) {
704: boolean result = containsKey(v);
705: if (result)
706: IntKeyOpenHashMap.this .remove(v);
707: return result;
708: }
709:
710: public int size() {
711: return size;
712: }
713:
714: }
715:
716: private class ValueCollection extends AbstractCollection {
717:
718: public void clear() {
719: IntKeyOpenHashMap.this .clear();
720: }
721:
722: public boolean contains(Object v) {
723: return containsValue(v);
724: }
725:
726: public Iterator iterator() {
727: return new Iterator() {
728: int nextEntry = nextEntry(0);
729: int lastEntry = -1;
730:
731: int nextEntry(int index) {
732: while (index < keys.length
733: && states[index] != OCCUPIED)
734: index++;
735: return index;
736: }
737:
738: public boolean hasNext() {
739: return nextEntry < keys.length;
740: }
741:
742: public Object next() {
743: if (!hasNext())
744: Exceptions.endOfIterator();
745: lastEntry = nextEntry;
746: nextEntry = nextEntry(nextEntry + 1);
747: return values[lastEntry];
748: }
749:
750: public void remove() {
751: if (lastEntry == -1)
752: Exceptions.noElementToRemove();
753: states[lastEntry] = REMOVED;
754: values[lastEntry] = null; // GC
755: size--;
756: lastEntry = -1;
757: }
758: };
759: }
760:
761: public int size() {
762: return size;
763: }
764:
765: }
766:
767: // ---------------------------------------------------------------
768: // Operations overwritten for efficiency
769: // ---------------------------------------------------------------
770:
771: public void clear() {
772: java.util.Arrays.fill(states, EMPTY);
773: java.util.Arrays.fill(values, null); // GC
774: size = 0;
775: used = 0;
776: }
777:
778: public boolean containsKey(int key) {
779: int h = Math.abs(keyhash.hash(key));
780: int i = h % keys.length;
781: if (states[i] != EMPTY) {
782: if (states[i] == OCCUPIED && keys[i] == key)
783: return true;
784:
785: // second hash
786: int c = 1 + (h % (keys.length - 2));
787: for (;;) {
788: i -= c;
789: if (i < 0)
790: i += keys.length;
791: if (states[i] == EMPTY)
792: return false;
793: if (states[i] == OCCUPIED && keys[i] == key)
794: return true;
795: }
796: }
797: return false;
798: }
799:
800: public boolean containsValue(Object value) {
801: if (value == null) {
802: for (int i = 0; i < states.length; i++)
803: if (states[i] == OCCUPIED && values[i] == null)
804: return true;
805: } else {
806: for (int i = 0; i < states.length; i++)
807: if (states[i] == OCCUPIED && value.equals(values[i]))
808: return true;
809: }
810: return false;
811: }
812:
813: public Object get(int key) {
814: int h = Math.abs(keyhash.hash(key));
815: int i = h % keys.length;
816: if (states[i] != EMPTY) {
817: if (states[i] == OCCUPIED && keys[i] == key)
818: return values[i];
819: // second hash
820:
821: int c = 1 + (h % (keys.length - 2));
822: for (;;) {
823: i -= c;
824: if (i < 0)
825: i += keys.length;
826: if (states[i] == EMPTY)
827: return null;
828: if (states[i] == OCCUPIED && keys[i] == key)
829: return values[i];
830: }
831: }
832: return null;
833: }
834:
835: public boolean isEmpty() {
836: return size == 0;
837: }
838:
839: public Object remove(int key) {
840: int h = Math.abs(keyhash.hash(key));
841: int i = h % keys.length;
842: if (states[i] != EMPTY) {
843: if (states[i] == OCCUPIED && keys[i] == key) {
844: Object oldValue = values[i];
845: values[i] = null; // GC
846: states[i] = REMOVED;
847: size--;
848: return oldValue;
849: }
850: // second hash
851: int c = 1 + (h % (keys.length - 2));
852: for (;;) {
853: i -= c;
854: if (i < 0)
855: i += keys.length;
856: if (states[i] == EMPTY) {
857: return null;
858: }
859: if (states[i] == OCCUPIED && keys[i] == key) {
860: Object oldValue = values[i];
861: values[i] = null; // GC
862: states[i] = REMOVED;
863: size--;
864: return oldValue;
865: }
866: }
867: }
868: return null;
869: }
870:
871: public int size() {
872: return size;
873: }
874:
875: // ---------------------------------------------------------------
876: // Serialization
877: // ---------------------------------------------------------------
878:
879: /**
880: * @serialData Default fields; the capacity of the
881: * map (<tt>int</tt>); the maps's entries
882: * (<tt>int</tt>, <tt>Object</tt>).
883: *
884: * @since 1.1
885: */
886: private void writeObject(ObjectOutputStream s) throws IOException {
887: s.defaultWriteObject();
888: s.writeInt(keys.length);
889: IntKeyMapIterator i = entries();
890: while (i.hasNext()) {
891: i.next();
892: s.writeInt(i.getKey());
893: s.writeObject(i.getValue());
894: }
895: }
896:
897: /**
898: * @since 1.1
899: */
900: private void readObject(ObjectInputStream s) throws IOException,
901: ClassNotFoundException {
902: s.defaultReadObject();
903: keys = new int[s.readInt()];
904: states = new byte[keys.length];
905: values = new Object[keys.length];
906: used = size;
907:
908: for (int n = 0; n < size; n++) {
909: int key = s.readInt();
910: Object value = s.readObject();
911:
912: // first hash
913: int h = Math.abs(keyhash.hash(key));
914: int i = h % keys.length;
915: if (states[i] != EMPTY) {
916: // second hash
917: int c = 1 + (h % (keys.length - 2));
918: for (;;) {
919: i -= c;
920: if (i < 0)
921: i += keys.length;
922: if (states[i] == EMPTY)
923: break;
924: }
925: }
926: states[i] = OCCUPIED;
927: keys[i] = key;
928: values[i] = value;
929: }
930: }
931:
932: }
|