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


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.ShortCollection;
22 import bak.pcj.AbstractShortCollection;
23 import bak.pcj.ShortIterator;
24 import bak.pcj.hash.ShortHashFunction;
25 import bak.pcj.hash.DefaultShortHashFunction;
26 import bak.pcj.util.Exceptions;
27 import java.util.Set ;
28 import java.util.AbstractSet ;
29 import java.util.Iterator ;
30
31 import java.io.Serializable ;
32 import java.io.IOException ;
33 import java.io.ObjectInputStream ;
34 import java.io.ObjectOutputStream ;
35
36 /**
37  * This class represents open addressing hash table based maps from
38  * object values to short values.
39  *
40  * @see ObjectKeyShortChainedHashMap
41  * @see java.util.Map
42  *
43  * @author Søren Bak
44  * @version 1.2 21-08-2003 19:41
45  * @since 1.1
46  */
47 public class ObjectKeyShortOpenHashMap extends AbstractObjectKeyShortMap implements ObjectKeyShortMap, Cloneable , Serializable {
48
49     /** Constant indicating relative growth policy. */
50     private static final int GROWTH_POLICY_RELATIVE = 0;
51
52     /** Constant indicating absolute growth policy. */
53     private static final int GROWTH_POLICY_ABSOLUTE = 1;
54
55     /**
56      * The default growth policy of this map.
57      * @see #GROWTH_POLICY_RELATIVE
58      * @see #GROWTH_POLICY_ABSOLUTE
59      */
60     private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
61
62     /** The default factor with which to increase the capacity of this map. */
63     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
64
65     /** The default chunk size with which to increase the capacity of this map. */
66     public static final int DEFAULT_GROWTH_CHUNK = 10;
67
68     /** The default capacity of this map. */
69     public static final int DEFAULT_CAPACITY = 11;
70
71     /** The default load factor of this map. */
72     public static final double DEFAULT_LOAD_FACTOR = 0.75;
73
74     /**
75      * The size of this map.
76      * @serial
77      */
78     private int size;
79
80     /**
81      * The keys of this map. Contains key values directly.
82      * Due to the use of a secondary hash function, the length of this
83      * array must be a prime.
84      */
85     private transient Object [] keys;
86
87     /**
88      * The values of this map. Contains values directly.
89      * Due to the use of a secondary hash function, the length of this
90      * array must be a prime.
91      */
92     private transient short[] values;
93
94     /** The states of each cell in the keys[] and values[]. */
95     private transient byte[] states;
96
97     private static final byte EMPTY = 0;
98     private static final byte OCCUPIED = 1;
99     private static final byte REMOVED = 2;
100
101     /** The number of entries in use (removed or occupied). */
102     private transient int used;
103
104     /**
105      * The growth policy of this map (0 is relative growth, 1 is absolute growth).
106      * @serial
107      */
108     private int growthPolicy;
109
110     /**
111      * The growth factor of this map, if the growth policy is
112      * relative.
113      * @serial
114      */
115     private double growthFactor;
116
117     /**
118      * The growth chunk size of this map, if the growth policy is
119      * absolute.
120      * @serial
121      */
122     private int growthChunk;
123
124     /**
125      * The load factor of this map.
126      * @serial
127      */
128     private double loadFactor;
129
130     /**
131      * The next size at which to expand the data[].
132      * @serial
133      */
134     private int expandAt;
135
136     /** A set view of the keys of this map. */
137     private transient Set ckeys;
138
139     /** A collection view of the values of this map. */
140     private transient ShortCollection cvalues;
141
142     /** Indicates whether last call to containsKey() had a corresponding value. */
143     private transient boolean hasLastValue;
144
145     /** Value corresponding to to the key of the last call of containsKey(). */
146     private transient short lastValue;
147
148     private ObjectKeyShortOpenHashMap(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
149         if (capacity < 0)
150             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
151         if (growthFactor <= 0.0)
152             Exceptions.negativeOrZeroArgument("growthFactor", String.valueOf(growthFactor));
153         if (growthChunk <= 0)
154             Exceptions.negativeOrZeroArgument("growthChunk", String.valueOf(growthChunk));
155         if (loadFactor <= 0.0)
156             Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor));
157         capacity = bak.pcj.hash.Primes.nextPrime(capacity);
158         keys = new Object [capacity];
159         values = new short[capacity];
160         this.states = new byte[capacity];
161         size = 0;
162         expandAt = (int)Math.round(loadFactor*capacity);
163         this.used = 0;
164         this.growthPolicy = growthPolicy;
165         this.growthFactor = growthFactor;
166         this.growthChunk = growthChunk;
167         this.loadFactor = loadFactor;
168         hasLastValue = false;
169     }
170
171     /**
172      * Creates a new hash map with capacity 11, a relative
173      * growth factor of 1.0, and a load factor of 75%.
174      */
175     public ObjectKeyShortOpenHashMap() {
176         this(DEFAULT_CAPACITY);
177     }
178
179     /**
180      * Creates a new hash map with the same mappings as a specified map.
181      *
182      * @param map
183      * the map whose mappings to put into the new map.
184      *
185      * @throws NullPointerException
186      * if <tt>map</tt> is <tt>null</tt>.
187      */
188     public ObjectKeyShortOpenHashMap(ObjectKeyShortMap map) {
189         this();
190         putAll(map);
191     }
192
193     /**
194      * Creates a new hash map with a specified capacity, a relative
195      * growth factor of 1.0, and a load factor of 75%.
196      *
197      * @param capacity
198      * the initial capacity of the map.
199      *
200      * @throws IllegalArgumentException
201      * if <tt>capacity</tt> is negative.
202      */
203     public ObjectKeyShortOpenHashMap(int capacity) {
204         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
205     }
206
207     /**
208      * Creates a new hash map with a capacity of 11, a relative
209      * growth factor of 1.0, and a specified load factor.
210      *
211      * @param loadFactor
212      * the load factor of the map.
213      *
214      * @throws IllegalArgumentException
215      * if <tt>capacity</tt> is negative;
216      * if <tt>loadFactor</tt> is not positive.
217      */
218     public ObjectKeyShortOpenHashMap(double loadFactor) {
219         this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
220     }
221
222     /**
223      * Creates a new hash map with a specified capacity and
224      * load factor, and a relative growth factor of 1.0.
225      *
226      * @param capacity
227      * the initial capacity of the map.
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 ObjectKeyShortOpenHashMap(int capacity, double loadFactor) {
237         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
238     }
239
240     /**
241      * Creates a new hash map with a specified capacity,
242      * load factor, and relative growth factor.
243      *
244      * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
245      * This strategy is good for avoiding many capacity increases, but
246      * the amount of wasted memory is approximately the size of the map.
247      *
248      * @param capacity
249      * the initial capacity of the map.
250      *
251      * @param loadFactor
252      * the load factor of the map.
253      *
254      * @param growthFactor
255      * the relative amount with which to increase the
256      * the capacity when a capacity increase is needed.
257      *
258      * @throws IllegalArgumentException
259      * if <tt>capacity</tt> is negative;
260      * if <tt>loadFactor</tt> is not positive;
261      * if <tt>growthFactor</tt> is not positive.
262      */
263     public ObjectKeyShortOpenHashMap(int capacity, double loadFactor, double growthFactor) {
264         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
265     }
266
267     /**
268      * Creates a new hash map with a specified capacity,
269      * load factor, and absolute growth factor.
270      *
271      * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
272      * This strategy is good for avoiding wasting memory. However, an
273      * overhead is potentially introduced by frequent capacity increases.
274      *
275      * @param capacity
276      * the initial capacity of the map.
277      *
278      * @param loadFactor
279      * the load factor of the map.
280      *
281      * @param growthChunk
282      * the absolute amount with which to increase the
283      * the capacity when a capacity increase is needed.
284      *
285      * @throws IllegalArgumentException
286      * if <tt>capacity</tt> is negative;
287      * if <tt>loadFactor</tt> is not positive;
288      * if <tt>growthChunk</tt> is not positive.
289      */
290     public ObjectKeyShortOpenHashMap(int capacity, double loadFactor, int growthChunk) {
291         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
292     }
293
294     // ---------------------------------------------------------------
295 // Hash table management
296 // ---------------------------------------------------------------
297
298     private static int hash(Object key)
299     { return key == null ? 0 : key.hashCode(); }
300
301     private static boolean keyeq(Object k1, Object k2)
302     { return k1 == null ? k2 == null : k1.equals(k2); }
303
304     private void ensureCapacity(int elements) {
305         if (elements >= expandAt) {
306             int newcapacity;
307             if (growthPolicy == GROWTH_POLICY_RELATIVE)
308                 newcapacity = (int)(keys.length * (1.0 + growthFactor));
309             else
310                 newcapacity = keys.length + growthChunk;
311             if (newcapacity*loadFactor < elements)
312                 newcapacity = (int)Math.round(((double)elements/loadFactor));
313             newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
314             expandAt = (int)Math.round(loadFactor*newcapacity);
315
316             Object [] newkeys = new Object [newcapacity];
317             short[] newvalues = new short[newcapacity];
318             byte[] newstates = new byte[newcapacity];
319
320             used = 0;
321             // re-hash
322 for (int i = 0; i < keys.length; i++) {
323                 if (states[i] == OCCUPIED) {
324                     used++;
325                     Object k = keys[i];
326                     short v = values[i];
327                     // first hash
328 int h = Math.abs(hash(k));
329                     int n = h % newcapacity;
330                     if (newstates[n] == OCCUPIED) {
331                         // second hash
332 int c = 1 + (h % (newcapacity - 2));
333                         for (;;) {
334                             n -= c;
335                             if (n < 0)
336                                 n += newcapacity;
337                             if (newstates[n] == EMPTY)
338                                 break;
339                         }
340                     }
341                     newstates[n] = OCCUPIED;
342                     newvalues[n] = v;
343                     newkeys[n] = k;
344                 }
345             }
346
347             keys = newkeys;
348             values = newvalues;
349             states = newstates;
350         }
351     }
352
353     // ---------------------------------------------------------------
354 // Operations not supported by abstract implementation
355 // ---------------------------------------------------------------
356
357     public Set keySet() {
358         if (ckeys == null)
359             ckeys = new KeySet();
360         return ckeys;
361     }
362
363     public short lget() {
364         if (!hasLastValue)
365             Exceptions.noLastElement();
366         return lastValue;
367     }
368
369     public short put(Object key, short value) {
370         short result;
371
372         // first hash
373 int h = Math.abs(hash(key));
374         int i = h % keys.length;
375         if (states[i] == OCCUPIED) {
376             if (keyeq(keys[i], key)) {
377                 short oldValue = values[i];
378                 values[i] = value;
379                 return oldValue;
380             }
381             // second hash
382 int c = 1 + (h % (keys.length - 2));
383             for (;;) {
384                 i -= c;
385                 if (i < 0)
386                     i += keys.length;
387                 // Empty entries are re-used
388 if (states[i] == EMPTY || states[i] == REMOVED)
389                     break;
390                 if (states[i] == OCCUPIED && keyeq(keys[i], key)) {
391                     short oldValue = values[i];
392                     values[i] = value;
393                     return oldValue;
394                 }
395             }
396         }
397         if (states[i] == EMPTY)
398             used++;
399         states[i] = OCCUPIED;
400         keys[i] = key;
401         values[i] = value;
402         size++;
403         ensureCapacity(used);
404         return MapDefaults.defaultShort();
405     }
406
407     public ShortCollection values() {
408         if (cvalues == null)
409             cvalues = new ValueCollection();
410         return cvalues;
411     }
412
413     /**
414      * Returns a clone of this hash map.
415      *
416      * @return a clone of this hash map.
417      *
418      * @since 1.1
419      */
420     public Object clone() {
421         try {
422             ObjectKeyShortOpenHashMap c = (ObjectKeyShortOpenHashMap)super.clone();
423             c.keys = new Object [keys.length];
424             System.arraycopy(keys, 0, c.keys, 0, keys.length);
425             c.values = new short[values.length];
426             System.arraycopy(values, 0, c.values, 0, values.length);
427             c.states = new byte[states.length];
428             System.arraycopy(states, 0, c.states, 0, states.length);
429             // The views should not refer to this map's views
430 c.cvalues = null;
431             c.ckeys = null;
432             return c;
433         } catch (CloneNotSupportedException e) {
434             Exceptions.cloning(); return null;
435         }
436     }
437
438     public ObjectKeyShortMapIterator entries() {
439         return new ObjectKeyShortMapIterator() {
440             int nextEntry = nextEntry(0);
441             int lastEntry = -1;
442
443             int nextEntry(int index) {
444                 while (index < keys.length && states[index] != OCCUPIED)
445                     index++;
446                 return index;
447             }
448
449             public boolean hasNext() {
450                 return nextEntry < keys.length;
451             }
452
453             public void next() {
454                 if (!hasNext())
455                     Exceptions.endOfIterator();
456                 lastEntry = nextEntry;
457                 nextEntry = nextEntry(nextEntry+1);
458             }
459
460             public void remove() {
461                 if (lastEntry == -1)
462                     Exceptions.noElementToRemove();
463                 states[lastEntry] = REMOVED;
464                 size--;
465                 lastEntry = -1;
466             }
467
468             public Object getKey() {
469                 if (lastEntry == -1)
470                     Exceptions.noElementToGet();
471                 return keys[lastEntry];
472             }
473
474             public short getValue() {
475                 if (lastEntry == -1)
476                     Exceptions.noElementToGet();
477                 return values[lastEntry];
478             }
479         };
480     }
481
482     private class KeySet extends AbstractSet {
483
484         public void clear()
485         { ObjectKeyShortOpenHashMap.this.clear(); }
486
487         public boolean contains(Object v) {
488             return containsKey(v);
489         }
490
491         public Iterator iterator() {
492             return new Iterator() {
493                 int nextEntry = nextEntry(0);
494                 int lastEntry = -1;
495
496                 int nextEntry(int index) {
497                     while (index < keys.length && states[index] != OCCUPIED)
498                         index++;
499                     return index;
500                 }
501
502                 public boolean hasNext() {
503                     return nextEntry < keys.length;
504                 }
505
506                 public Object next() {
507                     if (!hasNext())
508                         Exceptions.endOfIterator();
509                     lastEntry = nextEntry;
510                     nextEntry = nextEntry(nextEntry+1);
511                     return keys[lastEntry];
512                 }
513
514                 public void remove() {
515                     if (lastEntry == -1)
516                         Exceptions.noElementToRemove();
517                     states[lastEntry] = REMOVED;
518                     keys[lastEntry] = null; // GC
519 size--;
520                     lastEntry = -1;
521                 }
522             };
523         }
524
525         public boolean remove(Object v) {
526             boolean result = containsKey(v);
527             if (result)
528                 ObjectKeyShortOpenHashMap.this.remove(v);
529             return result;
530         }
531
532         public int size()
533         { return size; }
534
535     }
536
537
538     private class ValueCollection extends AbstractShortCollection {
539
540         public void clear()
541         { ObjectKeyShortOpenHashMap.this.clear(); }
542
543         public boolean contains(short v) {
544             return containsValue(v);
545         }
546
547         public ShortIterator iterator() {
548             return new ShortIterator() {
549                 int nextEntry = nextEntry(0);
550                 int lastEntry = -1;
551
552                 int nextEntry(int index) {
553                     while (index < keys.length && states[index] != OCCUPIED)
554                         index++;
555                     return index;
556                 }
557
558                 public boolean hasNext() {
559                     return nextEntry < keys.length;
560                 }
561
562                 public short next() {
563                     if (!hasNext())
564                         Exceptions.endOfIterator();
565                     lastEntry = nextEntry;
566                     nextEntry = nextEntry(nextEntry+1);
567                     return values[lastEntry];
568                 }
569
570                 public void remove() {
571                     if (lastEntry == -1)
572                         Exceptions.noElementToRemove();
573                     states[lastEntry] = REMOVED;
574                     size--;
575                     lastEntry = -1;
576                 }
577             };
578         }
579
580         public int size()
581         { return size; }
582
583     }
584
585     // ---------------------------------------------------------------
586 // Operations overwritten for efficiency
587 // ---------------------------------------------------------------
588
589     public void clear() {
590         java.util.Arrays.fill(states, EMPTY);
591         java.util.Arrays.fill(keys, null); // GC
592 size = 0;
593         used = 0;
594     }
595
596     public boolean containsKey(Object key) {
597         int h = Math.abs(hash(key));
598         int i = h % keys.length;
599         if (states[i] != EMPTY) {
600             if (states[i] == OCCUPIED && keyeq(keys[i], key)) {
601                 hasLastValue = true;
602                 lastValue = values[i];
603                 return true;
604             }
605             // second hash
606
607             int c = 1 + (h % (keys.length - 2));
608             for (;;) {
609                 i -= c;
610                 if (i < 0)
611                     i += keys.length;
612                 if (states[i] == EMPTY) {
613                     hasLastValue = false;
614                     return false;
615                 }
616                 if (states[i] == OCCUPIED && keyeq(keys[i], key)) {
617                     hasLastValue = true;
618                     lastValue = values[i];
619                     return true;
620                 }
621             }
622         }
623         hasLastValue = false;
624         return false;
625     }
626
627     public boolean containsValue(short value) {
628         for (int i = 0; i < states.length; i++)
629             if (states[i] == OCCUPIED && values[i] == value)
630                 return true;
631         return false;
632     }
633
634     public short get(Object key) {
635         int h = Math.abs(hash(key));
636         int i = h % keys.length;
637         if (states[i] != EMPTY) {
638             if (states[i] == OCCUPIED && keyeq(keys[i], key))
639                 return values[i];
640             // second hash
641
642             int c = 1 + (h % (keys.length - 2));
643             for (;;) {
644                 i -= c;
645                 if (i < 0)
646                     i += keys.length;
647                 if (states[i] == EMPTY)
648                     return MapDefaults.defaultShort();
649                 if (states[i] == OCCUPIED && keyeq(keys[i], key))
650                     return values[i];
651             }
652         }
653         return MapDefaults.defaultShort();
654     }
655
656     public boolean isEmpty()
657     { return size == 0; }
658
659     public short remove(Object key) {
660         int h = Math.abs(hash(key));
661         int i = h % keys.length;
662         if (states[i] != EMPTY) {
663             if (states[i] == OCCUPIED && keyeq(keys[i], key)) {
664                 short oldValue = values[i];
665                 states[i] = REMOVED;
666                 keys[i] = null; // GC
667 size--;
668                 return oldValue;
669             }
670             // second hash
671 int c = 1 + (h % (keys.length - 2));
672             for (;;) {
673                 i -= c;
674                 if (i < 0)
675                     i += keys.length;
676                 if (states[i] == EMPTY) {
677                     return MapDefaults.defaultShort();
678                 }
679                 if (states[i] == OCCUPIED && keyeq(keys[i], key)) {
680                     short oldValue = values[i];
681                     states[i] = REMOVED;
682                     keys[i] = null; // GC
683 size--;
684                     return oldValue;
685                 }
686             }
687         }
688         return MapDefaults.defaultShort();
689     }
690
691     public int size()
692     { return size; }
693
694     public short tget(Object key) {
695         int h = Math.abs(hash(key));
696         int i = h % keys.length;
697         if (states[i] != EMPTY) {
698             if (states[i] == OCCUPIED && keyeq(keys[i], key))
699                 return values[i];
700             // second hash
701
702             int c = 1 + (h % (keys.length - 2));
703             for (;;) {
704                 i -= c;
705                 if (i < 0)
706                     i += keys.length;
707                 if (states[i] == EMPTY)
708                     Exceptions.noSuchMapping(key);
709                 if (states[i] == OCCUPIED && keyeq(keys[i], key))
710                     return values[i];
711             }
712         }
713         Exceptions.noSuchMapping(key); throw new RuntimeException ();
714     }
715
716     // ---------------------------------------------------------------
717 // Serialization
718 // ---------------------------------------------------------------
719
720     /**
721      * @serialData Default fields; the capacity of the
722      * map (<tt>int</tt>); the maps's entries
723      * (<tt>short</tt>, <tt><S></tt>).
724      */
725     private void writeObject(ObjectOutputStream s) throws IOException {
726         s.defaultWriteObject();
727         s.writeInt(keys.length);
728         ObjectKeyShortMapIterator i = entries();
729         while (i.hasNext()) {
730             i.next();
731             s.writeObject(i.getKey());
732             s.writeShort(i.getValue());
733         }
734     }
735
736     private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException {
737         s.defaultReadObject();
738         keys = new Object [s.readInt()];
739         states = new byte[keys.length];
740         values = new short[keys.length];
741         used = size;
742
743         for (int n = 0; n < size; n++) {
744             Object key = s.readObject();
745             short value = s.readShort();
746
747             // first hash
748 int h = Math.abs(hash(key));
749             int i = h % keys.length;
750             if (states[i] != EMPTY) {
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                         break;
759                 }
760             }
761             states[i] = OCCUPIED;
762             keys[i] = key;
763             values[i] = value;
764         }
765     }
766
767 }

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags