2011/6/6 Simone Tripodi <simonetrip...@apache.org> > 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
