A weak hash map makes most sense when the keys doesn't override the
* equals method: If there is no other reference to the
* key nobody can ever look up the key in this table and so the entry
* can be removed. This table also works when the equals
* method is overloaded, such as String keys, but you should be prepared
* to deal with some entries disappearing spontaneously.
*
*
Other strange behaviors to be aware of: The size of this map may
* spontaneously shrink (even if you use a synchronized map and synchronize
* it); it behaves as if another thread removes entries from this table
* without synchronization. The entry set returned by entrySet
* has similar phenomenons: The size may spontaneously shrink, or an
* entry, that was in the set before, suddenly disappears.
*
*
A weak hash map is not meant for caches; use a normal map, with * soft references as values instead, or try {@link LinkedHashMap}. * *
The weak hash map supports null values and null keys. The null key * is never deleted from the map (except explictly of course). The * performance of the methods are similar to that of a hash map. * *
The value objects are strongly referenced by this table. So if a
* value object maintains a strong reference to the key (either direct
* or indirect) the key will never be removed from this map. According
* to Sun, this problem may be fixed in a future release. It is not
* possible to do it with the jdk 1.2 reference model, though.
*
* @author Jochen Hoenicke
* @author Eric Blake (ebb9@email.byu.edu)
* @author Tom Tromey (tromey@redhat.com)
* @author Andrew John Hughes (gnu_andrew@member.fsf.org)
*
* @see HashMap
* @see WeakReference
* @see LinkedHashMap
* @since 1.2
* @status updated to 1.4 (partial 1.5)
*/
public class WeakHashMaprehash().
*/
private int threshold;
/**
* The number of structural modifications. This is used by
* iterators, to see if they should fail. This doesn't count
* the silent key removals, when a weak reference is cleared
* by the garbage collection. Instead the iterators must make
* sure to have strong references to the entries they rely on.
*/
// Package visible for use by nested classes.
int modCount;
/**
* The entry set. There is only one instance per hashmap, namely
* theEntrySet. Note that the entry set may silently shrink, just
* like the WeakHashMap.
*/
private final class WeakEntrySet extends AbstractSet
{
/**
* Non-private constructor to reduce bytecode emitted.
*/
WeakEntrySet()
{
}
/**
* Returns the size of this set.
*
* @return the set size
*/
public int size()
{
return size;
}
/**
* Returns an iterator for all entries.
*
* @return an Entry iterator
*/
public Iterator iterator()
{
return new Iterator()
{
/**
* The entry that was returned by the last
* next() call. This is also the entry whose
* bucket should be removed by the remove call.
*
* It is null, if the next method wasn't
* called yet, or if the entry was already removed.
*
* Remembering this entry here will also prevent it from
* being removed under us, since the entry strongly refers
* to the key.
*/
WeakBucket.WeakEntry lastEntry;
/**
* The entry that will be returned by the next
* next() call. It is null if there
* is no further entry.
*
* Remembering this entry here will also prevent it from
* being removed under us, since the entry strongly refers
* to the key.
*/
WeakBucket.WeakEntry nextEntry = findNext(null);
/**
* The known number of modification to the list, if it differs
* from the real number, we throw an exception.
*/
int knownMod = modCount;
/**
* Check the known number of modification to the number of
* modifications of the table. If it differs from the real
* number, we throw an exception.
* @throws ConcurrentModificationException if the number
* of modifications doesn't match.
*/
private void checkMod()
{
// This method will get inlined.
cleanQueue();
if (knownMod != modCount)
throw new ConcurrentModificationException();
}
/**
* Get a strong reference to the next entry after
* lastBucket.
* @param lastEntry the previous bucket, or null if we should
* get the first entry.
* @return the next entry.
*/
private WeakBucket.WeakEntry findNext(WeakBucket.WeakEntry lastEntry)
{
int slot;
WeakBucket nextBucket;
if (lastEntry != null)
{
nextBucket = lastEntry.getBucket().next;
slot = lastEntry.getBucket().slot;
}
else
{
nextBucket = buckets[0];
slot = 0;
}
while (true)
{
while (nextBucket != null)
{
WeakBucket.WeakEntry entry = nextBucket.getEntry();
if (entry != null)
// This is the next entry.
return entry;
// Entry was cleared, try next.
nextBucket = nextBucket.next;
}
slot++;
if (slot == buckets.length)
// No more buckets, we are through.
return null;
nextBucket = buckets[slot];
}
}
/**
* Checks if there are more entries.
* @return true, iff there are more elements.
* @throws ConcurrentModificationException if the hash map was
* modified.
*/
public boolean hasNext()
{
checkMod();
return nextEntry != null;
}
/**
* Returns the next entry.
* @return the next entry.
* @throws ConcurrentModificationException if the hash map was
* modified.
* @throws NoSuchElementException if there is no entry.
*/
public Object next()
{
checkMod();
if (nextEntry == null)
throw new NoSuchElementException();
lastEntry = nextEntry;
nextEntry = findNext(lastEntry);
return lastEntry;
}
/**
* Removes the last returned entry from this set. This will
* also remove the bucket of the underlying weak hash map.
* @throws ConcurrentModificationException if the hash map was
* modified.
* @throws IllegalStateException if next() was
* never called or the element was already removed.
*/
public void remove()
{
checkMod();
if (lastEntry == null)
throw new IllegalStateException();
modCount++;
internalRemove(lastEntry.getBucket());
lastEntry = null;
knownMod++;
}
};
}
}
/**
* A bucket is a weak reference to the key, that contains a strong
* reference to the value, a pointer to the next bucket and its slot
* number.
*
* It would be cleaner to have a WeakReference as field, instead of
* extending it, but if a weak reference gets cleared, we only get
* the weak reference (by queue.poll) and wouldn't know where to
* look for this reference in the hashtable, to remove that entry.
*
* @author Jochen Hoenicke
*/
private static class WeakBucketMath.abs(key.hashCode() % buckets.length).
*
* But since the key may be silently removed we have to remember
* the slot number.
*
* If this bucket was removed the slot is -1. This marker will
* prevent the bucket from being removed twice.
*/
int slot;
/**
* Creates a new bucket for the given key/value pair and the specified
* slot.
* @param key the key
* @param queue the queue the weak reference belongs to
* @param value the value
* @param slot the slot. This must match the slot where this bucket
* will be enqueued.
*/
public WeakBucket(K key, ReferenceQueue queue, V value,
int slot)
{
super(key, queue);
this.value = value;
this.slot = slot;
}
/**
* This class gives the Entry representation of the
* current bucket. It also keeps a strong reference to the
* key; bad things may happen otherwise.
*/
class WeakEntry implements Map.EntryentrySet().
*/
private final WeakEntrySet theEntrySet;
/**
* The hash buckets. These are linked lists. Package visible for use in
* nested classes.
*/
WeakBucket[] buckets;
/**
* Creates a new weak hash map with default load factor and default
* capacity.
*/
public WeakHashMap()
{
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* Creates a new weak hash map with default load factor and the given
* capacity.
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if initialCapacity is negative
*/
public WeakHashMap(int initialCapacity)
{
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Creates a new weak hash map with the given initial capacity and
* load factor.
* @param initialCapacity the initial capacity.
* @param loadFactor the load factor (see class description of HashMap).
* @throws IllegalArgumentException if initialCapacity is negative, or
* loadFactor is non-positive
*/
public WeakHashMap(int initialCapacity, float loadFactor)
{
// Check loadFactor for NaN as well.
if (initialCapacity < 0 || ! (loadFactor > 0))
throw new IllegalArgumentException();
if (initialCapacity == 0)
initialCapacity = 1;
this.loadFactor = loadFactor;
threshold = (int) (initialCapacity * loadFactor);
theEntrySet = new WeakEntrySet();
queue = new ReferenceQueue();
buckets = new WeakBucket[initialCapacity];
}
/**
* Construct a new WeakHashMap with the same mappings as the given map.
* The WeakHashMap has a default load factor of 0.75.
*
* @param m the map to copy
* @throws NullPointerException if m is null
* @since 1.3
*/
public WeakHashMap(Map m)
{
this(m.size(), DEFAULT_LOAD_FACTOR);
putAll(m);
}
/**
* Simply hashes a non-null Object to its array index.
* @param key the key to hash
* @return its slot number
*/
private int hash(Object key)
{
return Math.abs(key.hashCode() % buckets.length);
}
/**
* Cleans the reference queue. This will poll all references (which
* are WeakBuckets) from the queue and remove them from this map.
* This will not change modCount, even if it modifies the map. The
* iterators have to make sure that nothing bad happens.
*
* Currently the iterator maintains a strong reference to the key, so
* that is no problem.
*/
// Package visible for use by nested classes.
void cleanQueue()
{
Object bucket = queue.poll();
while (bucket != null)
{
internalRemove((WeakBucket) bucket);
bucket = queue.poll();
}
}
/**
* Rehashes this hashtable. This will be called by the
* add() method if the size grows beyond the threshold.
* It will grow the bucket size at least by factor two and allocates
* new buckets.
*/
private void rehash()
{
WeakBucket[] oldBuckets = buckets;
int newsize = buckets.length * 2 + 1; // XXX should be prime.
threshold = (int) (newsize * loadFactor);
buckets = new WeakBucket[newsize];
// Now we have to insert the buckets again.
for (int i = 0; i < oldBuckets.length; i++)
{
WeakBucket bucket = oldBuckets[i];
WeakBucket nextBucket;
while (bucket != null)
{
nextBucket = bucket.next;
Object key = bucket.get();
if (key == null)
{
// This bucket should be removed; it is probably
// already on the reference queue. We don't insert it
// at all, and mark it as cleared.
bucket.slot = -1;
size--;
}
else
{
// Add this bucket to its new slot.
int slot = hash(key);
bucket.slot = slot;
bucket.next = buckets[slot];
buckets[slot] = bucket;
}
bucket = nextBucket;
}
}
}
/**
* Finds the entry corresponding to key. Since it returns an Entry
* it will also prevent the key from being removed under us.
* @param key the key, may be null
* @return The WeakBucket.WeakEntry or null, if the key wasn't found.
*/
private WeakBucket.WeakEntry internalGet(Object key)
{
if (key == null)
key = NULL_KEY;
int slot = hash(key);
WeakBucket bucket = buckets[slot];
while (bucket != null)
{
WeakBucket.WeakEntry entry = bucket.getEntry();
if (entry != null && key.equals(entry.key))
return entry;
bucket = bucket.next;
}
return null;
}
/**
* Adds a new key/value pair to the hash map.
* @param key the key. This mustn't exists in the map. It may be null.
* @param value the value.
*/
private void internalAdd(Object key, Object value)
{
if (key == null)
key = NULL_KEY;
int slot = hash(key);
WeakBucket bucket = new WeakBucket(key, queue, value, slot);
bucket.next = buckets[slot];
buckets[slot] = bucket;
size++;
}
/**
* Removes a bucket from this hash map, if it wasn't removed before
* (e.g. one time through rehashing and one time through reference queue).
* Package visible for use in nested classes.
*
* @param bucket the bucket to remove.
*/
void internalRemove(WeakBucket bucket)
{
int slot = bucket.slot;
if (slot == -1)
// This bucket was already removed.
return;
// Mark the bucket as removed. This is necessary, since the
// bucket may be enqueued later by the garbage collection, and
// internalRemove will be called a second time.
bucket.slot = -1;
if (buckets[slot] == bucket)
buckets[slot] = bucket.next;
else
{
WeakBucket prev = buckets[slot];
/* This may throw a NullPointerException. It shouldn't but if
* a race condition occurred (two threads removing the same
* bucket at the same time) it may happen.
* But with race condition many much worse things may happen
* anyway.
*/
while (prev.next != bucket)
prev = prev.next;
prev.next = bucket.next;
}
size--;
}
/**
* Returns the size of this hash map. Note that the size() may shrink
* spontaneously, if the some of the keys were only weakly reachable.
* @return the number of entries in this hash map.
*/
public int size()
{
cleanQueue();
return size;
}
/**
* Tells if the map is empty. Note that the result may change
* spontanously, if all of the keys were only weakly reachable.
* @return true, iff the map is empty.
*/
public boolean isEmpty()
{
cleanQueue();
return size == 0;
}
/**
* Tells if the map contains the given key. Note that the result
* may change spontanously, if the key was only weakly
* reachable.
* @param key the key to look for
* @return true, iff the map contains an entry for the given key.
*/
public boolean containsKey(Object key)
{
cleanQueue();
return internalGet(key) != null;
}
/**
* Gets the value the key is mapped to.
* @return the value the key was mapped to. It returns null if
* the key wasn't in this map, or if the mapped value was
* explicitly set to null.
*/
public V get(Object key)
{
cleanQueue();
WeakBucket