Java > Open Source Codes > bak > pcj > map > IntKeyOpenHashMap


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags