com.limegroup.gnutella.util
Class WeightBasedHashMap

java.lang.Object
  extended bycom.limegroup.gnutella.util.WeightBasedHashMap

public class WeightBasedHashMap
extends java.lang.Object

It stores only fixed number of entries as specified while constructing an instance of this class. It stores HashMap of Object => Weighable As it is of fixed size, it might need to remove some entry while inserting another one. The victim entry to be removed, when the hashmap is full, is found using an approximation algorithm, that doesnt weigh much. To be specific, the entry removed is the one that has weight which is less than k * (average weight in the map) (which is equivalent to average-weight-in-the map + (k-1)*average-weight-in-the-map), where k > 1 (ideal value of k lies in the range (1,2]). Its better to choose it more towards 1. We have chosen in this implementation, value of k as 1.1 This assures that the entries which are important (relatively more weighted) will not get chosen as the victim entry. Although its more complex than the actual HashMap class, but still all the supported operations in the class are O(1). This has been achieved by amortizing the operation to find victim. And the time complexity can be proved easily. Note: The instances of this class are not thread safe. Therefore access to it should be externally snchronized, if required

See Also:
Weighable

Constructor Summary
WeightBasedHashMap(int maxSize)
          Allocate space to store sufficient number of entries
 
Method Summary
 java.lang.Object add(java.lang.Object key, Weighable value)
          stores the given key-value.
 java.util.Set entrySet()
          Returns a collection view of the mappings contained in this map.
 Weighable get(java.lang.Object key)
          Returns the value to which this map maps the specified key Note: The weight associated with the returned Weighable value shouldnt be altered externally
 boolean incrementWeight(java.lang.Object key)
          Increment the weight corresponding to the given key by 1
 boolean isFull()
          checks if the hash Map is full or not
 boolean isWeightedEnough(Weighable value)
          Checks if the given query is frequent enough
 Weighable remove(java.lang.Object key)
          Removes the mapping for this key from this map if present.
 java.lang.String toString()
          Returns the string representation of mapping
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

WeightBasedHashMap

public WeightBasedHashMap(int maxSize)
Allocate space to store sufficient number of entries

Parameters:
maxSize - maximum number of entries to be stored in the underlying datastructure
Throws:
java.lang.IllegalArgumentException - if maxSize is less < 1,
Method Detail

incrementWeight

public boolean incrementWeight(java.lang.Object key)
Increment the weight corresponding to the given key by 1

Parameters:
key - The key for which the count to be incremented
Returns:
true, if the entry was present as count got incremented, false otherwise

get

public Weighable get(java.lang.Object key)
Returns the value to which this map maps the specified key Note: The weight associated with the returned Weighable value shouldnt be altered externally

Parameters:
key - key whose associated value is to be returned
Returns:
the value to which this map maps the specified key

remove

public Weighable remove(java.lang.Object key)
Removes the mapping for this key from this map if present.

Parameters:
key - The key whose mapping to be removed
Returns:
previous value associated with specified key, or null if there was no mapping for key.

add

public java.lang.Object add(java.lang.Object key,
                            Weighable value)
stores the given key-value. It might remove some other entry from the underlying data structure to make space for that.

Parameters:
key - The key for the mapping
value - The weighable value
Returns:
The entry(key) removed to make space for this new key, null otherwise

isWeightedEnough

public boolean isWeightedEnough(Weighable value)
Checks if the given query is frequent enough

Parameters:
value - The Weighable to be tested for weight
Returns:
true, if the object has enough weigh (more than average + some constant), false otherwise

isFull

public boolean isFull()
checks if the hash Map is full or not

Returns:
true if the map is full, false otherwise

entrySet

public java.util.Set entrySet()
Returns a collection view of the mappings contained in this map. Each element in the returned collection is a Map.Entry

Returns:
A collection view of the mappings contained in this map.

toString

public java.lang.String toString()
Returns the string representation of mapping

Returns:
The string representation of this