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