http://www.programcreek.com/2013/03/hashmap-vs-treemap-vs-hashtable-vs-linkedhashmap/
complexity
╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║ Property ║ HashMap ║ TreeMap ║ LinkedHashMap ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ ║ no guarantee order ║ sorted according ║ ║
║ Order ║ will remain constant║ to the natural ║ insertion-order ║
║ ║ over time ║ ordering ║ ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Get/put ║ ║ ║ ║
║ remove ║ O(1) ║ O(log(n)) ║ O(1) ║
║ containsKey ║ ║ ║ ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ ║ ║ NavigableMap ║ ║
║ Interfaces ║ Map ║ Map ║ Map ║
║ ║ ║ SortedMap ║ ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ ║ ║ ║ ║
║ Null ║ allowed ║ only values ║ allowed ║
║ values/keys ║ ║ ║ ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║ ║ Fail-fast behavior of an iterator cannot be guaranteed ║
║ Fail-fast ║ impossible to make any hard guarantees in the presence of ║
║ behavior ║ unsynchronized concurrent modification ║
╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣
║ ║ ║ ║ ║
║Implementation║ buckets ║ Red-Black Tree ║ double-linked ║
║ ║ ║ ║ buckets ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║ Is ║ ║
║ synchronized ║ implementation is not synchronized ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
Find Right Interval
设计的一道很好的简单题。撸了一个treemap，注意treemap.higherKey()只能得到key，还需要map.get(). 每次search实际上是binaryTree Search，complexity是O(nlogn).
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int idx = 0;
for(Interval i : intervals){
map.put(i.start, idx++);
}
int[] ans = new int[intervals.length];
idx = 0;
System.out.println(map.higherKey(3));
for(Interval i : intervals){
if(map.containsKey(i.end)) ans[idx++]=map.get(i.end);
else if(map.higherKey(i.end)==null) ans[idx++]=-1;
else ans[idx++] = map.get(map.higherKey(i.end));
}
return ans;
}
}