2011/6/6 Simone Tripodi
> my today's topic is about internal cache, that can be IMHO improved in
> therms of performance; its implementation is a multi-value map alike,
> based on a fixed-size array, a function is applied to each key to
> calculate the array index, each array element is a Collection of
> element.
> Even if getting the list of element related to a general key 'k' has
> complexity of O(1), which is fine, insert/search operations are not
> the best because their complexity is O(m) where m is the size of list
> related to the key.
>
Pretty naive, i suppose.
> Follow below my proposal: there's no need to reinvent the wheel, so
> the array implementation can be replaced with the already provided
> HashMap, where each map value is a simple implementation of balanced
> binary heap (AFAIK commons-collections already provides an
> implementation), that allows us reducing insert/search complexity to
> O(log m).
>
Probably you are referring to TreeMap, HashMap uses a fixed array with
collisions lists.
The "problem" with TreeMap is that any inserted key must implement
Comparable, or a Comparator must be supported.
Since it is a "cache", wouldn't an LRUMap be more useful?
http://commons.apache.org/collections/api-release/org/apache/commons/collections/map/LRUMap.html
WDYT? Is is a worth or trivial added value? I know that maybe cache
> dimension is relatively small, but linear search sounds too basic,
> isn't it?
>
I think you can go on. Surely a Map should be used, the implementation of
that Map could be considered at a later stage.
Antonio