Java > Open Source Codes > com > jofti > util > OpenHashMap


1 package com.jofti.util;
2
3 import java.util.Arrays ;
4 import java.util.Collection ;
5 import java.util.Collections ;
6 import java.util.HashSet ;
7 import java.util.List ;
8 import java.util.Map ;
9 import java.util.Set ;
10
11 /*
12
13 Copyright � 1999 CERN - European Organization for Nuclear Research.
14
15 Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
16
17 is hereby granted without fee, provided that the above copyright notice appear in all copies and
18
19 that both that copyright notice and this permission notice appear in supporting documentation.
20
21 CERN makes no representations about the suitability of this software for any purpose.
22
23 It is provided "as is" without expressed or implied warranty.
24
25 */
26
27
28 /**
29
30 Hash map holding (key,value) associations of type <tt>(int-->Object)</tt>; Automatically grows and shrinks as needed; Implemented using open addressing with double hashing.
31
32 First see the <a HREF="package-summary.html">package summary</a> and javadoc <a HREF="package-tree.html">tree view</a> to get the broad picture.
33
34
35
36 Overrides many methods for performance reasons only.
37
38
39 @author steve Woodcock
40 @author wolfgang.hoschek@cern.ch
41
42 @version 1.0, 09/24/99
43
44 @see java.util.HashMap
45
46 */
47
48 public class OpenHashMap extends AbstractMap implements Map {
49
50      /**
51
52      * The hash table keys.
53
54      * @serial
55
56      */
57
58     protected Object table[];
59
60
61
62      /**
63
64      * The hash table values.
65
66      * @serial
67
68      */
69
70     protected Object values[];
71
72
73
74     /**
75
76      * The state of each hash table entry (FREE, FULL, REMOVED).
77
78      * @serial
79
80      */
81
82     protected byte state[];
83
84     
85
86     /**
87
88      * The number of table entries in state==FREE.
89
90      * @serial
91
92      */
93
94     protected int freeEntries;
95
96
97
98     
99
100     protected static final byte FREE = 0;
101
102     protected static final byte FULL = 1;
103
104     protected static final byte REMOVED = 2;
105
106
107
108 /**
109
110  * Constructs an empty map with default capacity and default load factors.
111
112  */
113
114 public OpenHashMap() {
115
116     this(defaultCapacity);
117
118 }
119
120 /**
121
122  * Constructs an empty map with the specified initial capacity and default load factors.
123
124  *
125
126  * @param initialCapacity the initial capacity of the map.
127
128  * @throws IllegalArgumentException if the initial capacity is less
129
130  * than zero.
131
132  */
133
134 public OpenHashMap(int initialCapacity) {
135
136     this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
137
138 }
139
140 /**
141
142  * Constructs an empty map with
143
144  * the specified initial capacity and the specified minimum and maximum load factor.
145
146  *
147
148  * @param initialCapacity the initial capacity.
149
150  * @param minLoadFactor the minimum load factor.
151
152  * @param maxLoadFactor the maximum load factor.
153
154  * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
155
156  */
157
158 public OpenHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
159
160     setUp(initialCapacity,minLoadFactor,maxLoadFactor);
161
162 }
163
164
165 public OpenHashMap(double minLoadFactor, double maxLoadFactor) {
166
167     setUp(defaultCapacity,minLoadFactor,maxLoadFactor);
168
169 }
170
171 /**
172
173  * Removes all (key,value) associations from the receiver.
174
175  * Implicitly calls <tt>trimToSize()</tt>.
176
177  */
178
179 public void clear() {
180
181     for (int i=0;i<state.length;i++){
182         state[i] =FREE;
183     }
184   
185     for (int i=0;i<values.length;i++){
186         values[i] =null;
187     }
188  
189
190
191     this.distinct = 0;
192
193     this.freeEntries = table.length; // delta
194
195     trimToSize();
196
197 }
198
199 /**
200
201  * Returns a deep copy of the receiver.
202
203  *
204
205  * @return a deep copy of the receiver.
206
207  */
208
209 public Object clone() {
210
211     OpenHashMap copy = new OpenHashMap();
212
213     copy.table = (Object []) copy.table.clone();
214
215     copy.values = (Object []) copy.values.clone();
216
217     copy.state = (byte[]) copy.state.clone();
218
219     return copy;
220
221 }
222
223 /**
224
225  * Returns <tt>true</tt> if the receiver contains the specified key.
226
227  *
228
229  * @return <tt>true</tt> if the receiver contains the specified key.
230
231  */
232
233 public boolean containsKey(Object key) {
234
235     return indexOfKey(key) >= 0;
236
237 }
238
239 /**
240
241  * Returns <tt>true</tt> if the receiver contains the specified value.
242
243  *
244
245  * @return <tt>true</tt> if the receiver contains the specified value.
246
247  */
248
249 public boolean containsValue(Object value) {
250
251     return indexOfValue(value) >= 0;
252
253 }
254
255 /**
256
257  * Ensures that the receiver can hold at least the specified number of associations without needing to allocate new internal memory.
258
259  * If necessary, allocates new internal memory and increases the capacity of the receiver.
260
261  * <p>
262
263  * This method never need be called; it is for performance tuning only.
264
265  * Calling this method before <tt>put()</tt>ing a large number of associations boosts performance,
266
267  * because the receiver will grow only once instead of potentially many times and hash collisions get less probable.
268
269  *
270
271  * @param minCapacity the desired minimum capacity.
272
273  */
274
275 public void ensureCapacity(int minCapacity) {
276
277     if (this.highWaterMark < minCapacity) {
278
279         int newCapacity = nextPrime(minCapacity);
280
281         rehash(newCapacity);
282
283     }
284
285 }
286
287 /**
288
289  * Applies a procedure to each key of the receiver, if any.
290
291  * Note: Iterates over the keys in no particular order.
292
293  * Subclasses can define a particular order, for example, "sorted by key".
294
295  * All methods which <i>can</i> be expressed in terms of this method (most methods can) <i>must guarantee</i> to use the <i>same</i> order defined by this method, even if it is no particular order.
296
297  * This is necessary so that, for example, methods <tt>keys</tt> and <tt>values</tt> will yield association pairs, not two uncorrelated lists.
298
299  *
300
301  * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise continues.
302
303  * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
304
305  */
306
307 public boolean forEachKey(ObjectProcedure procedure) {
308
309     for (int i = table.length ; i-- > 0 ;) {
310
311         if (state[i]==FULL) if (! procedure.apply(table[i])) return false;
312
313     }
314
315     return true;
316
317 }
318
319 /**
320
321  * Applies a procedure to each (key,value) pair of the receiver, if any.
322
323  * Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
324
325  *
326
327  * @param procedure the procedure to be applied. Stops iteration if the procedure returns <tt>false</tt>, otherwise continues.
328
329  * @return <tt>false</tt> if the procedure stopped before all keys where iterated over, <tt>true</tt> otherwise.
330
331  */
332
333 public boolean forEachPair(final ObjectProcedure procedure) {
334
335     for (int i = table.length ; i-- > 0 ;) {
336
337         if (state[i]==FULL) if (! procedure.apply(table[i],values[i])) return false;
338
339     }
340
341     return true;
342
343 }
344
345 /**
346
347  * Returns the value associated with the specified key.
348
349  * It is often a good idea to first check with {@link #containsKey(int)} whether the given key has a value associated or not, i.e. whether there exists an association for the given key or not.
350
351  *
352
353  * @param key the key to be searched for.
354
355  * @return the value associated with the specified key; <tt>null</tt> if no such key is present.
356
357  */
358
359 public Object get(Object key) {
360
361     if (key ==null){
362         return null;
363     }
364     int i = indexOfKey(key);
365
366     if (i<0) return null; //not contained
367
368     return values[i];
369
370 }
371
372 /**
373
374  * @param key the key to be added to the receiver.
375
376  * @return the index where the key would need to be inserted, if it is not already contained.
377
378  * Returns -index-1 if the key is already contained at slot index.
379
380  * Therefore, if the returned index < 0, then it is already contained at slot -index-1.
381
382  * If the returned index >= 0, then it is NOT already contained and should be inserted at slot index.
383
384  */
385
386 protected int indexOfInsertion(Object key) {
387
388     final Object tab[] = table;
389
390     final byte stat[] = state;
391
392     final int length = tab.length;
393
394
395
396     final int hash = key.hashCode() & 0x7FFFFFFF;
397
398     int i = hash % length;
399
400     int decrement = hash % (length-2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
401
402     //int decrement = (hash / length) % length;
403
404     if (decrement == 0) decrement = 1;
405
406
407
408     // stop if we find a removed or free slot, or if we find the key itself
409
410     // do NOT skip over removed slots (yes, open addressing is like that...)
411
412     while (stat[i] == FULL && (!tab[i].equals(key))) {
413    // while (stat[i] == FULL && tab[i]!=key) {
414
415         i -= decrement;
416
417         //hashCollisions++;
418
419         if (i<0) i+=length;
420
421     }
422
423     
424
425     if (stat[i] == REMOVED) {
426
427         // stop if we find a free slot, or if we find the key itself.
428
429         // do skip over removed slots (yes, open addressing is like that...)
430
431         // assertion: there is at least one FREE slot.
432
433         int j = i;
434
435         while (stat[i] != FREE && (stat[i] == REMOVED || (!tab[i].equals(key)))) {
436       // while (stat[i] != FREE && (stat[i] == REMOVED || tab[i]!=key)) {
437 i -= decrement;
438
439             //hashCollisions++;
440
441             if (i<0) i+=length;
442
443         }
444
445         if (stat[i] == FREE) i = j;
446
447     }
448
449     
450
451     
452
453     if (stat[i] == FULL) {
454
455         // key already contained at slot i.
456
457         // return a negative number identifying the slot.
458
459         return -i-1;
460
461     }
462
463     // not already contained, should be inserted at slot i.
464
465     // return a number >= 0 identifying the slot.
466
467     return i;
468
469 }
470
471 /**
472
473  * @param key the key to be searched in the receiver.
474
475  * @return the index where the key is contained in the receiver, returns -1 if the key was not found.
476
477  */
478
479 protected int indexOfKey(Object key) {
480
481     final Object tab[] = table;
482
483     final byte stat[] = state;
484
485     final int length = tab.length;
486
487
488
489     final int hash = key.hashCode() & 0x7FFFFFFF;
490
491     int i = hash % length;
492
493     int decrement = hash % (length-2); // double hashing, see http://www.eece.unm.edu/faculty/heileman/hash/node4.html
494
495     //int decrement = (hash / length) % length;
496
497     if (decrement == 0) decrement = 1;
498
499
500
501     // stop if we find a free slot, or if we find the key itself.
502
503     // do skip over removed slots (yes, open addressing is like that...)
504
505     while (stat[i] != FREE && (stat[i] == REMOVED || !(tab[i].equals(key)))) {
506    // while (stat[i] != FREE && (stat[i] == REMOVED || tab[i] != key)) {
507
508         i -= decrement;
509
510         //hashCollisions++;
511
512         if (i<0) i+=length;
513
514     }
515
516     
517
518     if (stat[i] == FREE) return -1; // not found
519
520     return i; //found, return index where key is contained
521
522 }
523
524 /**
525
526  * @param value the value to be searched in the receiver.
527
528  * @return the index where the value is contained in the receiver, returns -1 if the value was not found.
529
530  */
531
532 protected int indexOfValue(Object value) {
533
534     final Object val[] = values;
535
536     final byte stat[] = state;
537
538
539
540     for (int i=stat.length; --i >= 0;) {
541
542         if (stat[i]==FULL && val[i].equals(value)) return i;
543
544     }
545
546
547
548     return -1; // not found
549
550 }
551
552 /**
553
554  * Returns the first key the given value is associated with.
555
556  * It is often a good idea to first check with {@link #containsValue(Object)} whether there exists an association from a key to this value.
557
558  * Search order is guaranteed to be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
559
560  *
561
562  * @param value the value to search for.
563
564  * @return the first key for which holds <tt>get(key) == value</tt>;
565
566  * returns <tt>Integer.MIN_VALUE</tt> if no such key exists.
567
568  */
569
570 public Object keyOf(Object value) {
571
572     //returns the first key found; there may be more matching keys, however.
573
574     int i = indexOfValue(value);
575
576     if (i<0) return null;
577
578     return table[i];
579
580 }
581
582 /**
583
584  * Fills all keys contained in the receiver into the specified list.
585
586  * Fills the list, starting at index 0.
587
588  * After this call returns the specified list has a new size that equals <tt>this.size()</tt>.
589
590  * Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
591
592  * <p>
593
594  * This method can be used to iterate over the keys of the receiver.
595
596  *
597
598  * @param list the list to be filled, can have any size.
599
600  */
601
602 public void keys(Object [] array) {
603
604    
605     
606     
607
608     Object [] tab = table;
609
610     byte[] stat = state;
611
612     
613
614     int j=0;
615
616     for (int i = tab.length ; i-- > 0 ;) {
617
618         if (stat[i]==FULL) array[j++]=tab[i];
619
620     }
621
622 }
623
624
625
626 /**
627
628  * Associates the given key with the given value.
629
630  * Replaces any old <tt>(key,someOtherValue)</tt> association, if existing.
631
632  *
633
634  * @param key the key the value shall be associated with.
635
636  * @param value the value to be associated.
637
638  * @return <tt>true</tt> if the receiver did not already contain such a key;
639
640  * <tt>false</tt> if the receiver did already contain such a key - the new value has now replaced the formerly associated value.
641
642  */
643
644 public Object put(Object key, Object value) {
645
646     int i = indexOfInsertion(key);
647
648     if (i<0) { //already contained
649
650         i = -i -1;
651
652         Object temp = values[i];
653         this.values[i]=value;
654
655         return temp;
656
657     }
658
659
660
661     if (this.distinct > this.highWaterMark) {
662
663         int newCapacity = chooseGrowCapacity(this.distinct+1,this.minLoadFactor, this.maxLoadFactor);
664
665         rehash(newCapacity);
666
667         return put(key, value);
668
669     }
670
671
672
673     this.table[i]=key;
674
675     this.values[i]=value;
676
677     if (this.state[i]==FREE) this.freeEntries--;
678
679     this.state[i]=FULL;
680
681     this.distinct++;
682
683
684
685     if (this.freeEntries < 1) { //delta
686
687         int newCapacity = chooseGrowCapacity(this.distinct+1,this.minLoadFactor, this.maxLoadFactor);
688
689         rehash(newCapacity);
690
691     }
692
693
694
695     return null;
696
697 }
698
699 /**
700
701  * Rehashes the contents of the receiver into a new table
702
703  * with a smaller or larger capacity.
704
705  * This method is called automatically when the
706
707  * number of keys in the receiver exceeds the high water mark or falls below the low water mark.
708
709  */
710
711 protected void rehash(int newCapacity) {
712
713     int oldCapacity = table.length;
714
715     //if (oldCapacity == newCapacity) return;
716
717     
718
719     Object oldTable[] = table;
720
721     Object oldValues[] = values;
722
723     byte oldState[] = state;
724
725
726
727     Object newTable[] = new Object [newCapacity];
728
729     Object newValues[] = new Object [newCapacity];
730
731     byte newState[] = new byte[newCapacity];
732
733
734
735     this.lowWaterMark = chooseLowWaterMark(newCapacity,this.minLoadFactor);
736
737     this.highWaterMark = chooseHighWaterMark(newCapacity,this.maxLoadFactor);
738
739
740
741     this.table = newTable;
742
743     this.values = newValues;
744
745     this.state = newState;
746
747     this.freeEntries = newCapacity-this.distinct; // delta
748
749     
750
751     for (int i = oldCapacity ; i-- > 0 ;) {
752
753         if (oldState[i]==FULL) {
754
755             Object element = oldTable[i];
756
757             int index = indexOfInsertion(element);
758
759             if (index <0){
760                 throw new RuntimeException ("equals and hashCode not implemented correctly - clash when rehashing: "+ element + " and "+ newTable[(Math.abs(index)-1)] + " are equal");
761             }
762             newTable[index]=element;
763
764             newValues[index]=oldValues[i];
765
766             newState[index]=FULL;
767
768         }
769
770     }
771
772 }
773
774 /**
775
776  * Removes the given key with its associated element from the receiver, if present.
777
778  *
779
780  * @param key the key to be removed from the receiver.
781
782  * @return <tt>true</tt> if the receiver contained the specified key, <tt>false</tt> otherwise.
783
784  */
785
786 public Object remove(Object key) {
787
788     int i = indexOfKey(key);
789
790     if (i<0) return null; // key not contained
791
792
793
794     this.state[i]=REMOVED;
795
796     Object temp =this.values[i];
797     this.values[i]=null; // delta
798
799     this.distinct--;
800
801
802
803     if (this.distinct < this.lowWaterMark) {
804
805         int newCapacity = chooseShrinkCapacity(this.distinct,this.minLoadFactor, this.maxLoadFactor);
806
807         rehash(newCapacity);
808
809     }
810
811     
812
813     return temp;
814
815 }
816
817
818 public Object removeNoReHash(Object key) {
819
820     int i = indexOfKey(key);
821
822     if (i<0) return null; // key not contained
823
824
825
826     this.state[i]=REMOVED;
827
828     Object temp =this.values[i];
829     this.values[i]=null; // delta
830
831     this.distinct--;
832
833     
834
835     return temp;
836
837 }
838 /**
839
840  * Initializes the receiver.
841
842  *
843
844  * @param initialCapacity the initial capacity of the receiver.
845
846  * @param minLoadFactor the minLoadFactor of the receiver.
847
848  * @param maxLoadFactor the maxLoadFactor of the receiver.
849
850  * @throws IllegalArgumentException if <tt>initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor)</tt>.
851
852  */
853
854 protected void setUp(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
855
856     int capacity = initialCapacity;
857
858     super.setUp(capacity, minLoadFactor, maxLoadFactor);
859
860     capacity = nextPrime(capacity);
861
862     if (capacity==0) capacity=1; // open addressing needs at least one FREE slot at any time.
863
864     
865
866     this.table = new Object [capacity];
867
868     this.values = new Object [capacity];
869
870     this.state = new byte[capacity];
871
872
873
874     // memory will be exhausted long before this pathological case happens, anyway.
875
876     this.minLoadFactor = minLoadFactor;
877
878     if (capacity == PrimeFinder.largestPrime) this.maxLoadFactor = 1.0;
879
880     else this.maxLoadFactor = maxLoadFactor;
881
882
883
884     this.distinct = 0;
885
886     this.freeEntries = capacity; // delta
887
888     
889
890     // lowWaterMark will be established upon first expansion.
891
892     // establishing it now (upon instance construction) would immediately make the table shrink upon first put(...).
893
894     // After all the idea of an "initialCapacity" implies violating lowWaterMarks when an object is young.
895
896     // See ensureCapacity(...)
897
898     this.lowWaterMark = 0;
899
900     this.highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
901
902 }
903
904 /**
905
906  * Trims the capacity of the receiver to be the receiver's current
907
908  * size. Releases any superfluous internal memory. An application can use this operation to minimize the
909
910  * storage of the receiver.
911
912  */
913
914 public void trimToSize() {
915
916     // * 1.2 because open addressing's performance exponentially degrades beyond that point
917
918     // so that even rehashing the table can take very long
919
920     int newCapacity = nextPrime((int)(1 + 1.2*size()));
921
922     if (table.length > newCapacity) {
923
924         rehash(newCapacity);
925
926     }
927
928 }
929
930 /**
931
932  * Fills all values contained in the receiver into the specified list.
933
934  * Fills the list, starting at index 0.
935
936  * After this call returns the specified list has a new size that equals <tt>this.size()</tt>.
937
938  * Iteration order is guaranteed to be <i>identical</i> to the order used by method {@link #forEachKey(IntProcedure)}.
939
940  * <p>
941
942  * This method can be used to iterate over the values of the receiver.
943
944  *
945
946  * @param list the list to be filled, can have any size.
947
948  */
949
950 public void values(Object [] array) {
951
952    
953
954     
955
956     Object [] val = values;
957
958     byte[] stat = state;
959
960     
961
962     int j=0;
963
964     for (int i = stat.length ; i-- > 0 ;) {
965
966         if (stat[i]==FULL) array[j++]=val[i];
967
968     }
969
970 }
971
972
973
974 public void putAll(Map t)
975 {
976     throw new UnsupportedOperationException ("operation not supported");
977     
978 }
979
980 public Set keySet()
981 {
982     
983     throw new UnsupportedOperationException ("operation not supported");
984 }
985
986 public List keyList()
987 {
988     
989       Object [] temp =new Object [state.length - freeEntries];
990         keys(temp);
991         return Arrays.asList(temp);
992 }
993
994 public Collection values()
995 {
996     
997     Object [] temp =new Object [state.length - freeEntries];
998     values(temp);
999     return Arrays.asList(temp);
1000}
1001
1002public Set entrySet()
1003{
1004    throw new UnsupportedOperationException ("operation not supported");
1005}
1006
1007}
1008
1009
1010

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags