在LinkedHashMap中以O(1)检查两个不同键的顺序。

huangapple
go评论125阅读模式
英文:

Check the ordering of 2 different keys in LinkedHashMap in O(1)

问题

在LinkedHashMap中，键的顺序是根据它们插入到映射中的时间来排序的。

例如，考虑以下映射。

  1. LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
  2. map.put(1, 1);
  3. map.put(2, 3);
  4. map.put(7, 4);
  5. map.put(5, 6);

所以，我对LinkedHashMap的理解是，键以双向链表的形式存储。

因此，在这个示例中，键的顺序将是1<->2<->7<->5。

现在，我的需求是这样的。给定来自这个映射的两个键，是否可以检查哪一个先插入，哪一个后插入？

例如，一个像下面这样的函数：

  1. public boolean isFirst(int key1, int key2) {
  2.     // 用于计算key1是否在key2之前的逻辑
  3. }

现在，可以轻松地通过维护另一个映射以获取顺序并进行比较来在O(n)中完成上述函数。

我想在O(1)中执行此操作。如果可能的话，我应该维护一些其他数据结构来处理映射中键的插入、删除和更新吗？

英文:

In a LinkedHashMap, the keys are ordered by when they were inserted into the map.

For example, consider the following map.

  1. LinkedHashMap&lt;Integer,Integer&gt; map = new LinkedHashMap&lt;&gt;();
  2. map.put(1, 1);
  3. map.put(2, 3);
  4. map.put(7, 4);
  5. map.put(5, 6);

So, my understanding of LinkedHashMap is that the keys are stored in the form a Doubly Linked List.

So, in this example, the keys would be ordered as 1&lt;-&gt;2&lt;-&gt;7&lt;-&gt;5

Now, my requirement is this. Given 2 keys from this map, is it possible to check which one came first or last?

For example, a function like the following

  1. public boolean isFirst(int key1,int key2){
  2. // logic to compute if key1 is first
  3. }

Now, the above function can be done in O(n) easily by maintaining another map to get the order and compare it.

I want to do this operation in O(1). If it is possible, then should I maintain some other data structure to handle insertion, removal and updation of keys in the map ?

答案1

得分: 2

你可以创建一个自定义类，它扩展了 LinkedHashMap，并添加了自定义方法 isFirst。在内部，我们保留了一个单独的映射，就像你已经分析过的那样，其中有一个 timestamp 变量，它充当了时间戳，表示键添加的秒数。

如果第一个键的时间戳小于第二个键的时间戳，我们返回 true，否则返回 false。

类片段:

  1. class CustomMap<K,V> extends LinkedHashMap<K,V>{
  2.     private Map<K,Integer> ord_map;
  3.     private int timestamp = 0;
  4.     CustomMap(){
  5.         super();
  6.         ord_map = new HashMap<>();
  7.     }
  8.     
  9.     public V put(K key,V val){
  10.         ord_map.put(key,timestamp++);
  11.         return super.put(key,val);
  12.     }
  13.     
  14.     public V remove(Object key){
  15.         ord_map.remove(key);
  16.         return super.remove(key);
  17.     }
  18.     
  19.     public boolean isFirst(K key1,K key2) throws Exception{
  20.         if(!ord_map.containsKey(key1)) throw new Exception(key1 + " 不存在。");
  21.         if(!ord_map.containsKey(key2)) throw new Exception(key2 + " 不存在。");
  22.         
  23.         return ord_map.get(key1) < ord_map.get(key2);
  24.     }
  25. }

驱动代码:

  1. public class Solution{
  2.     public static void main(String[] args) {
  3.         CustomMap<Integer,Integer> cmap = new CustomMap<>();
  4.         try{
  5.             cmap.put(1, 1);
  6.             cmap.put(5, 6);
  7.             cmap.put(2, 3);
  8.             cmap.put(7, 4);
  9.             System.out.println(cmap.isFirst(5,2));    
  10.             cmap.remove(5);
  11.             cmap.put(5,99);
  12.             System.out.println(cmap.isFirst(5,2));  
  13.         }catch(Exception e){
  14.             System.out.println(e.getMessage());
  15.         }
  16.     }
  17. }
英文:

You can create a custom class that extends LinkedHashMap and add the custom method isFirst. Internally, we keep a separate map as you already analyzed with a timestamp variable which acts like a timestamp for us(the second at which the key was added).

If the first key's timestamp is less than the second ones, we return true , else we return false.

Class Snippet:

  1. class CustomMap&lt;K,V&gt; extends LinkedHashMap&lt;K,V&gt;{
  2.     private Map&lt;K,Integer&gt; ord_map;
  3.     private int timestamp = 0;
  4.     CustomMap(){
  5.         super();
  6.         ord_map = new HashMap&lt;&gt;();
  7.     }
  8.     
  9.     public V put(K key,V val){
  10.         ord_map.put(key,timestamp++);
  11.         return super.put(key,val);
  12.     }
  13.     
  14.     public V remove(Object key){
  15.         ord_map.remove(key);
  16.         return super.remove(key);
  17.     }
  18.     
  19.     public boolean isFirst(K key1,K key2) throws Exception{
  20.         if(!ord_map.containsKey(key1)) throw new Exception(key1 + &quot; does not exist.&quot;);
  21.         if(!ord_map.containsKey(key2)) throw new Exception(key2 + &quot; does not exist.&quot;);
  22.         
  23.         return ord_map.get(key1) &lt; ord_map.get(key2);
  24.     }
  25. }

Driver Code:

  1. public class Solution{
  2.     public static void main(String[] args) {
  3.         CustomMap&lt;Integer,Integer&gt; cmap = new CustomMap&lt;&gt;();
  4.         try{
  5.             cmap.put(1, 1);
  6.             cmap.put(5, 6);
  7.             cmap.put(2, 3);
  8.             cmap.put(7, 4);
  9.             System.out.println(cmap.isFirst(5,2));    
  10.             cmap.remove(5);
  11.             cmap.put(5,99);
  12.             System.out.println(cmap.isFirst(5,2));  
  13.         }catch(Exception e){
  14.             System.out.println(e.getMessage());
  15.         }
  16.         
  17.     }
  18. }

答案2

得分: 1

以下是翻译好的部分：

有一种基于HashMap的索引解决方案，但在填充索引映射时，它的时间和内存复杂度都是O(N)。

  1. import java.util.*;
  3. public class Solution {
  4.     static int index = 0;
  5.     
  6.     static Map<Integer, Integer> indexMap = new HashMap<>();
  7.     
  8.     static void initIndexes(LinkedHashMap<Integer, Integer> map) {
  9.         indexMap.clear();
  10.         index = 0;
  11.         map.keySet().forEach(x -> {indexMap.put(x, index++);});
  12.     }
  13.     
  14.     static boolean isKeyBefore(int key1, int key2) {
  15.         return indexMap.getOrDefault(key1, Integer.MAX_VALUE) < 
  16.         indexMap.getOrDefault(key2, -1);
  17.     }
  19.     public static void main(String []args) {
  20.         LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
  21.         map.put(1, 1);
  22.         map.put(2, 3);
  23.         map.put(7, 4);
  24.         map.put(5, 6);
  25.         
  26.         initIndexes(map);
  27.             
  28.         System.out.println(indexMap);
  29.         
  30.         System.out.println(isKeyBefore(2, 5)); // true
  31.         System.out.println(isKeyBefore(7, 1)); // false
  32.         System.out.println(isKeyBefore(5, 3)); // key2 is not in the indexMap
  33.         System.out.println(isKeyBefore(4, 2)); // key1 is not in the indexMap
  34.         System.out.println(isKeyBefore(6, 8)); // both keys are not in the indexMap
  35.         
  36.     }
  37. }
英文:

There could be a solution based on HashMap for indexes, but it has O(N) complexity both in time and memory to populate the index map.

  1. import java.util.*;
  2. public class Solution {
  3. static int index = 0;
  4. static Map&lt;Integer, Integer&gt; indexMap = new HashMap&lt;&gt;();
  5. static void initIndexes(LinkedHashMap&lt;Integer, Integer&gt; map) {
  6. indexMap.clear();
  7. index = 0;
  8. map.keySet().forEach(x -&gt; {indexMap.put(x, index++);});
  9. }
  10. static boolean isKeyBefore(int key1, int key2) {
  11. return indexMap.getOrDefault(key1, Integer.MAX_VALUE) &lt; 
  12. indexMap.getOrDefault(key2, -1);
  13. }
  14. public static void main(String []args) {
  15. LinkedHashMap&lt;Integer,Integer&gt; map = new LinkedHashMap&lt;&gt;();
  16. map.put(1, 1);
  17. map.put(2, 3);
  18. map.put(7, 4);
  19. map.put(5, 6);
  20. initIndexes(map);
  21. System.out.println(indexMap);
  22. System.out.println(isKeyBefore(2, 5)); // true
  23. System.out.println(isKeyBefore(7, 1)); // false
  24. System.out.println(isKeyBefore(5, 3)); // key2 is not in the indexMap
  25. System.out.println(isKeyBefore(4, 2)); // key1 is not in the indexMap
  26. System.out.println(isKeyBefore(6, 8)); // both keys are not in the indexMap
  27. }
  28. }

huangapple
  • 本文由 发表于 2020年7月23日 02:11:20
  • 转载请务必保留本文链接：https://go.coder-hub.com/63040638.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定