981. Time Based Key-Value Store

Key idea: efficient dataframe to do (map + binary search)

核心：高效的数据结构来完成（HashMap＋二分查找法）

Map each key and store value in the order of timestamp

Solution 1:

Store "key, timestamp, value" as HashMap<String, ArrayList<Pair<Integer, String>>>. Call Collections.binarySearch( ) to support get operation

Time complexity of set operation is $O(1)$ and get operation is $O(lg N)$

存储为 HashMap<String, ArrayList<Pair<Integer, String>>> 的数据结构，对应为 key: (timestamp, value)。 调用 Collections.binarySearch( ) 完成 get 操作。set 时间复杂度是O(1)，get 时间复杂度为 O(lg N)。

Solution 2:

Store "key, timestamp, value" as HashMap<String, TreeMap<Integer, String>>.

Time complexity of set operation is $O(lg N)$ and get operation is $O(lg N)$

存储为 HashMap<String, TreeMap<Integer, String>> 的数据结构，对应为 key: (timestamp: value)。set 和 get 的时间复杂度都是 O(lg N)。

English

Learning

• Map is an interface that should be instantiated before using. Two main implementation are HashMap and TreeMap. The main difference is that TreeMap sorts elements in binary tree when adding new element.

• List is an interface. ArrayList, LinkedList, Stack and Vector are its implementation. ArrayList and LinkedList are the most common used. ArrayList accesses element quickly but add and delete element slowly. LinkedList accesses element slowly but add and delete element quickly. https://docs.oracle.com/javase/7/docs/api/java/util/List.html

• Collections.binarySearch(List, key). Search an element in a sorted List sorted in ascending order by binary search. If key exists, return its index. If key doesn't exist, return (-(insertion point)-1). If search an element in a decending sorted List, we can use collections.binarySearch(List, Key, collections.reverseOrder()).https://www.geeksforgeeks.org/collections-binarysearch-java-examples/

Chinese