|
1
7
8 package java.util;
9
10 import java.lang.ref.WeakReference  ;
11 import java.lang.ref.ReferenceQueue ;
12
13
14
109 public class WeakHashMap<K,V>
110 extends AbstractMap <K,V>
111 implements Map <K,V> {
112
113
116 private static final int DEFAULT_INITIAL_CAPACITY = 16;
117
118
123 private static final int MAXIMUM_CAPACITY = 1 << 30;
124
125
128 private static final float DEFAULT_LOAD_FACTOR = 0.75f;
129
130
133 private Entry[] table;
134
135
138 private int size;
139
140
143 private int threshold;
144
145
148 private final float loadFactor;
149
150
153 private final ReferenceQueue <K> queue = new ReferenceQueue <K>();
154
155
162 private volatile int modCount;
163
164
173 public WeakHashMap(int initialCapacity, float loadFactor) {
174 if (initialCapacity < 0)
175 throw new IllegalArgumentException ("Illegal Initial Capacity: "+
176 initialCapacity);
177 if (initialCapacity > MAXIMUM_CAPACITY)
178 initialCapacity = MAXIMUM_CAPACITY;
179
180 if (loadFactor <= 0 || Float.isNaN(loadFactor))
181 throw new IllegalArgumentException ("Illegal Load factor: "+
182 loadFactor);
183 int capacity = 1;
184 while (capacity < initialCapacity)
185 capacity <<= 1;
186 table = new Entry[capacity];
187 this.loadFactor = loadFactor;
188 threshold = (int)(capacity * loadFactor);
189 }
190
191
198 public WeakHashMap(int initialCapacity) {
199 this(initialCapacity, DEFAULT_LOAD_FACTOR);
200 }
201
202
206 public WeakHashMap() {
207 this.loadFactor = DEFAULT_LOAD_FACTOR;
208 threshold = (int)(DEFAULT_INITIAL_CAPACITY);
209 table = new Entry[DEFAULT_INITIAL_CAPACITY];
210 }
211
212
222 public WeakHashMap(Map <? extends K, ? extends V> t) {
223 this(Math.max((int) (t.size() / DEFAULT_LOAD_FACTOR) + 1, 16),
224 DEFAULT_LOAD_FACTOR);
225 putAll(t);
226 }
227
228
230
233 private static final Object NULL_KEY = new Object ();
234
235
238 private static Object maskNull(Object key) {
239 return (key == null ? NULL_KEY : key);
240 }
241
242
245 private static <K> K unmaskNull(Object key) {
246 return (K) (key == NULL_KEY ? null : key);
247 }
248
249
253 static boolean eq(Object x, Object y) {
254 return x == y || x.equals(y);
255 }
256
257
260 static int indexFor(int h, int length) {
261 return h & (length-1);
262 }
263
264
267 private void expungeStaleEntries() {
268 Entry<K,V> e;
269 while ( (e = (Entry<K,V>) queue.poll()) != null) {
270 int h = e.hash;
271 int i = indexFor(h, table.length);
272
273 Entry<K,V> prev = table[i];
274 Entry<K,V> p = prev;
275 while (p != null) {
276 Entry<K,V> next = p.next;
277 if (p == e) {
278 if (prev == e)
279 table[i] = next;
280 else
281 prev.next = next;
282 e.next = null; e.value = null; size--;
285 break;
286 }
287 prev = p;
288 p = next;
289 }
290 }
291 }
292
293
296 private Entry[] getTable() {
297 expungeStaleEntries();
298 return table;
299 }
300
301
307 public int size() {
308 if (size == 0)
309 return 0;
310 expungeStaleEntries();
311 return size;
312 }
313
314
320 public boolean isEmpty() {
321 return size() == 0;
322 }
323
324
338 public V get(Object key) {
339 Object k = maskNull(key);
340 int h = HashMap.hash(k);
341 Entry[] tab = getTable();
342 int index = indexFor(h, tab.length);
343 Entry<K,V> e = tab[index];
344 while (e != null) {
345 if (e.hash == h && eq(k, e.get()))
346 return e.value;
347 e = e.next;
348 }
349 return null;
350 }
351
352
360 public boolean containsKey(Object key) {
361 return getEntry(key) != null;
362 }
363
364
368 Entry<K,V> getEntry(Object key) {
369 Object k = maskNull(key);
370 int h = HashMap.hash(k);
371 Entry[] tab = getTable();
372 int index = indexFor(h, tab.length);
373 Entry<K,V> e = tab[index];
374 while (e != null && !(e.hash == h && eq(k, e.get())))
375 e = e.next;
376 return e;
377 }
378
379
391 public V put(K key, V value) {
392 K k = (K) maskNull(key);
393 int h = HashMap.hash(k);
394 Entry[] tab = getTable();
395 int i = indexFor(h, tab.length);
396
397 for (Entry<K,V> e = tab[i]; e != null; e = e.next) {
398 if (h == e.hash && eq(k, e.get())) {
399 V oldValue = e.value;
400 if (value != oldValue)
401 e.value = value;
402 return oldValue;
403 }
404 }
405
406 modCount++;
407 Entry<K,V> e = tab[i];
408 tab[i] = new Entry<K,V>(k, value, queue, h, e);
409 if (++size >= threshold)
410 resize(tab.length * 2);
411 return null;
412 }
413
414
428 void resize(int newCapacity) {
429 Entry[] oldTable = getTable();
430 int oldCapacity = oldTable.length;
431 if (oldCapacity == MAXIMUM_CAPACITY) {
432 threshold = Integer.MAX_VALUE;
433 return;
434 }
435
436 Entry[] newTable = new Entry[newCapacity];
437 transfer(oldTable, newTable);
438 table = newTable;
439
440
445 if (size >= threshold / 2) {
446 threshold = (int)(newCapacity * loadFactor);
447 } else {
448 expungeStaleEntries();
449 transfer(newTable, oldTable);
450 table = oldTable;
451 }
452 }
453
454
455 private void transfer(Entry[] src, Entry[] dest) {
456 for (int j = 0; j < src.length; ++j) {
457 Entry<K,V> e = src[j];
458 src[j] = null;
459 while (e != null) {
460 Entry<K,V> next = e.next;
461 Object key = e.get();
462 if (key == null) {
463 e.next = null; e.value = null; size--;
466 } else {
467 int i = indexFor(e.hash, dest.length);
468 e.next = dest[i];
469 dest[i] = e;
470 }
471 e = next;
472 }
473 }
474 }
475
476
484 public void putAll(Map <? extends K, ? extends V> m) {
485 int numKeysToBeAdded = m.size();
486 if (numKeysToBeAdded == 0)
487 return;
488
489
498 if (numKeysToBeAdded > threshold) {
499 int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
500 if (targetCapacity > MAXIMUM_CAPACITY)
501 targetCapacity = MAXIMUM_CAPACITY;
502 int newCapacity = table.length;
503 while (newCapacity < targetCapacity)
504 newCapacity <<= 1;
505 if (newCapacity > table.length)
506 resize(newCapacity);
507 }
508
509 for (Iterator <? extends Map.Entry <? extends K, ? extends V>> i = m.entrySet().iterator(); i.hasNext(); ) {
510 Map.Entry <? extends K, ? extends V> e = i.next();
511 put(e.getKey(), e.getValue());
512 }
513 }
514
515
524 public V remove(Object key) {
525 Object k = maskNull(key);
526 int h = HashMap.hash(k);
527 Entry[] tab = getTable();
528 int i = indexFor(h, tab.length);
529 Entry<K,V> prev = tab[i];
530 Entry<K,V> e = prev;
531
532 while (e != null) {
533 Entry<K,V> next = e.next;
534 if (h == e.hash && eq(k, e.get())) {
535 modCount++;
536 size--;
537 if (prev == e)
538 tab[i] = next;
539 else
540 prev.next = next;
541 return e.value;
542 }
543 prev = e;
544 e = next;
545 }
546
547 return null;
548 }
549
550
551
552
553 Entry<K,V> removeMapping(Object o) {
554 if (!(o instanceof Map.Entry ))
555 return null;
556 Entry[] tab = getTable();
557 Map.Entry entry = (Map.Entry )o;
558 Object k = maskNull(entry.getKey());
559 int h = HashMap.hash(k);
560 int i = indexFor(h, tab.length);
561 Entry<K,V> prev = tab[i];
562 Entry<K,V> e = prev;
563
564 while (e != null) {
565 Entry<K,V> next = e.next;
566 if (h == e.hash && e.equals(entry)) {
567 modCount++;
568 size--;
569 if (prev == e)
570 tab[i] = next;
571 else
572 prev.next = next;
573 return e;
574 }
575 prev = e;
576 e = next;
577 }
578
579 return null;
580 }
581
582
585 public void clear() {
586 while (queue.poll() != null)
589 ;
590
591 modCount++;
592 Entry[] tab = table;
593 for (int i = 0; i < tab.length; ++i)
594 tab[i] = null;
595 size = 0;
596
597 while (queue.poll() != null)
601 ;
602 }
603
604
612 public boolean containsValue(Object value) {
613 if (value==null)
614 return containsNullValue();
615
616 Entry[] tab = getTable();
617 for (int i = tab.length ; i-- > 0 ;)
618 for (Entry e = tab[i] ; e != null ; e = e.next)
619 if (value.equals(e.value))
620 return true;
621 return false;
622 }
623
624
627 private boolean containsNullValue() {
628 Entry[] tab = getTable();
629 for (int i = tab.length ; i-- > 0 ;)
630 for (Entry e = tab[i] ; e != null ; e = e.next)
631 if (e.value==null)
632 return true;
633 return false;
634 }
635
636
640 private static class Entry<K,V> extends WeakReference <K> implements Map.Entry <K,V> {
641 private V value;
642 private final int hash;
643 private Entry<K,V> next;
644
645
648 Entry(K key, V value,
649 ReferenceQueue <K> queue,
650 int hash, Entry<K,V> next) {
651 super(key, queue);
652 this.value = value;
653 this.hash = hash;
654 this.next = next;
655 }
656
657 public K getKey() {
658 return WeakHashMap.<K>unmaskNull(get());
659 }
660
661 public V getValue() {
662 return value;
663 }
664
665 public V setValue(V newValue) {
666 V oldValue = value;
667 value = newValue;
668 return oldValue;
669 }
670
671 public boolean equals(Object o) {
672 if (!(o instanceof Map.Entry ))
673 return false;
674 Map.Entry e = (Map.Entry )o;
675 Object k1 = getKey();
676 Object k2 = e.getKey();
677 if (k1 == k2 || (k1 != null && k1.equals(k2))) {
678 Object v1 = getValue();
679 Object v2 = e.getValue();
680 if (v1 == v2 || (v1 != null && v1.equals(v2)))
681 return true;
682 }
683 return false;
684 }
685
686 public int hashCode() {
687 Object k = getKey();
688 Object v = getValue();
689 return ((k==null ? 0 : k.hashCode()) ^
690 (v==null ? 0 : v.hashCode()));
691 }
692
693 public String toString() {
694 return getKey() + "=" + getValue();
695 }
696 }
697
698 private abstract class HashIterator<T> implements Iterator <T> {
699 int index;
700 Entry<K,V> entry = null;
701 Entry<K,V> lastReturned = null;
702 int expectedModCount = modCount;
703
704
708 Object nextKey = null;
709
710
714 Object currentKey = null;
715
716 HashIterator() {
717 index = (size() != 0 ? table.length : 0);
718 }
719
720 public boolean hasNext() {
721 Entry[] t = table;
722
723 while (nextKey == null) {
724 Entry<K,V> e = entry;
725 int i = index;
726 while (e == null && i > 0)
727 e = t[--i];
728 entry = e;
729 index = i;
730 if (e == null) {
731 currentKey = null;
732 return false;
733 }
734 nextKey = e.get(); if (nextKey == null)
736 entry = entry.next;
737 }
738 return true;
739 }
740
741
742 protected Entry<K,V> nextEntry() {
743 if (modCount != expectedModCount)
744 throw new ConcurrentModificationException ();
745 if (nextKey == null && !hasNext())
746 throw new NoSuchElementException ();
747
748 lastReturned = entry;
749 entry = entry.next;
750 currentKey = nextKey;
751 nextKey = null;
752 return lastReturned;
753 }
754
755 public void remove() {
756 if (lastReturned == null)
757 throw new IllegalStateException ();
758 if (modCount != expectedModCount)
759 throw new ConcurrentModificationException ();
760
761 WeakHashMap.this.remove(currentKey);
762 expectedModCount = modCount;
763 lastReturned = null;
764 currentKey = null;
765 }
766
767 }
768
769 private class ValueIterator extends HashIterator<V> {
770 public V next() {
771 return nextEntry().value;
772 }
773 }
774
775 private class KeyIterator extends HashIterator<K> {
776 public K next() {
777 return nextEntry().getKey();
778 }
779 }
780
781 private class EntryIterator extends HashIterator<Map.Entry <K,V>> {
782 public Map.Entry <K,V> next() {
783 return nextEntry();
784 }
785 }
786
787
789 private transient Set <Map.Entry <K,V>> entrySet = null;
790
791
802 public Set <K> keySet() {
803 Set <K> ks = keySet;
804 return (ks != null ? ks : (keySet = new KeySet()));
805 }
806
807 private class KeySet extends AbstractSet <K> {
808 public Iterator <K> iterator() {
809 return new KeyIterator();
810 }
811
812 public int size() {
813 return WeakHashMap.this.size();
814 }
815
816 public boolean contains(Object o) {
817 return containsKey(o);
818 }
819
820 public boolean remove(Object o) {
821 if (containsKey(o)) {
822 WeakHashMap.this.remove(o);
823 return true;
824 }
825 else
826 return false;
827 }
828
829 public void clear() {
830 WeakHashMap.this.clear();
831 }
832
833 public Object [] toArray() {
834 Collection <K> c = new ArrayList <K>(size());
835 for (Iterator <K> i = iterator(); i.hasNext(); )
836 c.add(i.next());
837 return c.toArray();
838 }
839
840 public <T> T[] toArray(T[] a) {
841 Collection <K> c = new ArrayList <K>(size());
842 for (Iterator <K> i = iterator(); i.hasNext(); )
843 c.add(i.next());
844 return c.toArray(a);
845 }
846 }
847
848
859 public Collection <V> values() {
860 Collection <V> vs = values;
861 return (vs != null ? vs : (values = new Values()));
862 }
863
864 private class Values extends AbstractCollection <V> {
865 public Iterator <V> iterator() {
866 return new ValueIterator();
867 }
868
869 public int size() {
870 return WeakHashMap.this.size();
871 }
872
873 public boolean contains(Object o) {
874 return containsValue(o);
875 }
876
877 public void clear() {
878 WeakHashMap.this.clear();
879 }
880
881 public Object [] toArray() {
882 Collection <V> c = new ArrayList <V>(size());
883 for (Iterator <V> i = iterator(); i.hasNext(); )
884 c.add(i.next());
885 return c.toArray();
886 }
887
888 public <T> T[] toArray(T[] a) {
889 Collection <V> c = new ArrayList <V>(size());
890 for (Iterator <V> i = iterator(); i.hasNext(); )
891 c.add(i.next());
892 return c.toArray(a);
893 }
894 }
895
896
909 public Set <Map.Entry <K,V>> entrySet() {
910 Set <Map.Entry <K,V>> es = entrySet;
911 return (es != null ? es : (entrySet = new EntrySet()));
912 }
913
914 private class EntrySet extends AbstractSet <Map.Entry <K,V>> {
915 public Iterator <Map.Entry <K,V>> iterator() {
916 return new EntryIterator();
917 }
918
919 public boolean contains(Object o) {
920 if (!(o instanceof Map.Entry ))
921 return false;
922 Map.Entry e = (Map.Entry )o;
923 Object k = e.getKey();
924 Entry candidate = getEntry(e.getKey());
925 return candidate != null && candidate.equals(e);
926 }
927
928 public boolean remove(Object o) {
929 return removeMapping(o) != null;
930 }
931
932 public int size() {
933 return WeakHashMap.this.size();
934 }
935
936 public void clear() {
937 WeakHashMap.this.clear();
938 }
939
940 public Object [] toArray() {
941 Collection <Map.Entry <K,V>> c = new ArrayList <Map.Entry <K,V>>(size());
942 for (Iterator <Map.Entry <K,V>> i = iterator(); i.hasNext(); )
943 c.add(new AbstractMap.SimpleEntry <K,V>(i.next()));
944 return c.toArray();
945 }
946
947 public <T> T[] toArray(T[] a) {
948 Collection <Map.Entry <K,V>> c = new ArrayList <Map.Entry <K,V>>(size());
949 for (Iterator <Map.Entry <K,V>> i = iterator(); i.hasNext(); )
950 c.add(new AbstractMap.SimpleEntry <K,V>(i.next()));
951 return c.toArray(a);
952 }
953 }
954 }
955 |
Popular Tags |
Java API By Example, From Geeks To Geeks.