[GitHub] [iotdb] lancelly commented on a diff in pull request #6986: [IOTDB-4126] Optimize cache implementation using HashMap to find Node instead of traversal with a for loop

[GitBox <gi...@apache.org>]

lancelly commented on code in PR #6986:
URL: https://github.com/apache/iotdb/pull/6986#discussion_r946428152


##########
server/src/main/java/org/apache/iotdb/db/mpp/transformation/datastructure/Cache.java:
##########
@@ -64,33 +69,37 @@ protected Cache(int capacity) {
       cachedNodes[i] = new Node();
     }
 
+    valueToNode = new HashMap<>();
+
     cacheCapacity = capacity;
     cacheSize = 0;
   }
 
   protected boolean removeFirstOccurrence(int value) {
-    for (Node node = head.succeeding; node != tail; node = node.succeeding) {
-      if (node.value == value) {
-        cachedNodes[--cacheSize] = node.remove();
-        return true;
-      }
+    if (valueToNode.containsKey(value)) {
+      cachedNodes[--cacheSize] = valueToNode.get(value).remove();
+      return true;
     }
     return false;
   }
 
   protected int removeLast() {
     Node last = tail.previous.remove();
     cachedNodes[--cacheSize] = last;
+    valueToNode.remove(last.value);
     return last.value;
   }
 
   protected void addFirst(int value) {
-    cachedNodes[cacheSize++].set(head, value, head.succeeding);
+    cachedNodes[cacheSize].set(head, value, head.succeeding);
+    valueToNode.put(value, cachedNodes[cacheSize]);

Review Comment:
   Does this work well when encounters duplicate keys? 



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: reviews-unsubscribe@iotdb.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org