|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectcom.limegroup.gnutella.util.WeightBasedHashMap
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
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 |
public WeightBasedHashMap(int maxSize)
maxSize
- maximum number of entries to be stored in the underlying
datastructure
java.lang.IllegalArgumentException
- if maxSize is less < 1,Method Detail |
public boolean incrementWeight(java.lang.Object key)
key
- The key for which the count to be incremented
public Weighable get(java.lang.Object key)
key
- key whose associated value is to be returned
public Weighable remove(java.lang.Object key)
key
- The key whose mapping to be removed
public java.lang.Object add(java.lang.Object key, Weighable value)
key
- The key for the mappingvalue
- The weighable value
public boolean isWeightedEnough(Weighable value)
value
- The Weighable to be tested for weight
public boolean isFull()
public java.util.Set entrySet()
public java.lang.String toString()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |