Performance improvements by replacing hash depth calculation with shifting, improving code quality.

+ formatting

4 files changed, 193 insertions, 147 deletions

diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
index 9397dede..e437aceb 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/ImmutableNode.java
@@ -42,8 +42,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
          *              available.
          * @return an immutable version of the input node.
          */
-        static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node,
-                        Map<Node<K, V>, ImmutableNode<K, V>> cache) {
+        static <K, V> ImmutableNode<K, V> constructImmutable(MutableNode<K, V> node, Map<Node<K, V>, ImmutableNode<K, V>> cache) {
                 // 1. try to return from cache
                 if (cache != null) {
                         ImmutableNode<K, V> cachedResult = cache.get(node);
@@ -75,8 +74,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                 resultContent[datas * 2 + 1] = node.content[i * 2 + 1];
                                 datas++;
                         } else {
-                                @SuppressWarnings("unchecked")
-                                var subnode = (Node<K, V>) node.content[i * 2 + 1];
+                                @SuppressWarnings("unchecked") var subnode = (Node<K, V>) node.content[i * 2 + 1];
                                 if (subnode != null) {
                                         ImmutableNode<K, V> immutableSubnode = subnode.toImmutable(cache);
                                         resultNodeMap |= bitposition;
@@ -107,11 +105,9 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 // If the key is stored as a data
                 if ((dataMap & bitposition) != 0) {
                         int keyIndex = 2 * index(dataMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        K keyCandidate = (K) content[keyIndex];
+                        @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex];
                         if (keyCandidate.equals(key)) {
-                                @SuppressWarnings("unchecked")
-                                V value = (V) content[keyIndex + 1];
+                                @SuppressWarnings("unchecked") V value = (V) content[keyIndex + 1];
                                 return value;
                         } else {
                                 return defaultValue;
@@ -120,9 +116,8 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 // the key is stored as a node
                 else if ((nodeMap & bitposition) != 0) {
                         int keyIndex = content.length - 1 - index(nodeMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        var subNode = (ImmutableNode<K, V>) content[keyIndex];
-                        int newDepth = depth + 1;
+                        @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex];
+                        int newDepth = incrementDepth(depth);
                         int newHash = newHash(hashProvider, key, hash, newDepth);
                         return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth);
                 }
@@ -133,14 +128,12 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue, int hash, int depth) {
+        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValue, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
                 int bitposition = 1 << selectedHashFragment;
                 if ((dataMap & bitposition) != 0) {
                         int keyIndex = 2 * index(dataMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        K keyCandidate = (K) content[keyIndex];
+                        @SuppressWarnings("unchecked") K keyCandidate = (K) content[keyIndex];
                         if (keyCandidate.equals(key)) {
                                 if (value == defaultValue) {
                                         // delete
@@ -151,7 +144,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                         oldValue.setOldValue(value);
                                         return this;
                                 } else {
-                                        // update existing nodeId
+                                        // update existing value
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.updateValue(value, oldValue, selectedHashFragment);
                                 }
@@ -161,16 +154,15 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                         oldValue.setOldValue(defaultValue);
                                         return this;
                                 } else {
-                                        // add new key + nodeId
+                                        // add new key + value
                                         MutableNode<K, V> mutable = this.toMutable();
                                         return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
                                 }
                         }
                 } else if ((nodeMap & bitposition) != 0) {
                         int keyIndex = content.length - 1 - index(nodeMap, bitposition);
-                        @SuppressWarnings("unchecked")
-                        var subNode = (ImmutableNode<K, V>) content[keyIndex];
-                        int newDepth = depth + 1;
+                        @SuppressWarnings("unchecked") var subNode = (ImmutableNode<K, V>) content[keyIndex];
+                        int newDepth = incrementDepth(depth);
                         int newHash = newHash(hashProvider, key, hash, newDepth);
                         var newsubNode = subNode.putValue(key, value, oldValue, hashProvider, defaultValue, newHash, newDepth);
 
@@ -179,10 +171,11 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                                 return this;
                         } else {
                                 MutableNode<K, V> mutable = toMutable();
-                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode, value.equals(defaultValue));
+                                return mutable.updateWithSubNode(selectedHashFragment, newsubNode,
+                                                (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
                         }
                 } else {
-                        // add new key + nodeId
+                        // add new key + value
                         MutableNode<K, V> mutable = this.toMutable();
                         return mutable.putValue(key, value, oldValue, hashProvider, defaultValue, hash, depth);
                 }
@@ -192,8 +185,7 @@ public class ImmutableNode<K, V> extends Node<K, V> {
         public long getSize() {
                 int result = Integer.bitCount(this.dataMap);
                 for (int subnodeIndex = 0; subnodeIndex < Integer.bitCount(this.nodeMap); subnodeIndex++) {
-                        @SuppressWarnings("unchecked")
-                        var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
+                        @SuppressWarnings("unchecked") var subnode = (ImmutableNode<K, V>) this.content[this.content.length - 1 - subnodeIndex];
                         result += subnode.getSize();
                 }
                 return result;
@@ -289,10 +281,9 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                 int nodeMask = 1;
                 for (int i = 0; i < FACTOR; i++) {
                         if ((nodeMask & nodeMap) != 0) {
-                                @SuppressWarnings("unchecked")
-                                Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)];
+                                @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[content.length - 1 - index(nodeMap, nodeMask)];
                                 builder.append("\n");
-                                subNode.prettyPrint(builder, depth + 1, i);
+                                subNode.prettyPrint(builder, incrementDepth(depth), i);
                         }
                         nodeMask <<= 1;
                 }
@@ -310,12 +301,11 @@ public class ImmutableNode<K, V> extends Node<K, V> {
 
                 // check subnodes
                 for (int i = 0; i < Integer.bitCount(nodeMap); i++) {
-                        @SuppressWarnings("unchecked")
-                        var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
+                        @SuppressWarnings("unchecked") var subnode = (Node<K, V>) this.content[this.content.length - 1 - i];
                         if (!(subnode instanceof ImmutableNode<?, ?>)) {
                                 throw new IllegalStateException("Immutable node contains mutable subnodes!");
                         } else {
-                                subnode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                                subnode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth));
                         }
                 }
         }
@@ -327,13 +317,10 @@ public class ImmutableNode<K, V> extends Node<K, V> {
 
         @Override
         public boolean equals(Object obj) {
-                if (this == obj)
-                        return true;
-                if (obj == null)
-                        return false;
+                if (this == obj) return true;
+                if (obj == null) return false;
                 if (obj instanceof ImmutableNode<?, ?> other) {
-                        return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap
-                                        && Arrays.deepEquals(content, other.content);
+                        return precalculatedHash == other.precalculatedHash && dataMap == other.dataMap && nodeMap == other.nodeMap && Arrays.deepEquals(content, other.content);
                 } else if (obj instanceof MutableNode<?, ?> mutableObj) {
                         return ImmutableNode.compareImmutableMutable(this, mutableObj);
                 } else {
@@ -351,12 +338,10 @@ public class ImmutableNode<K, V> extends Node<K, V> {
                         if (key != null) {
                                 // Check whether a new Key-Value pair can fit into the immutable container
                                 if (datas * 2 + nodes + 2 <= immutableLength) {
-                                        if (!immutable.content[datas * 2].equals(key)
-                                                        || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
+                                        if (!immutable.content[datas * 2].equals(key) || !immutable.content[datas * 2 + 1].equals(mutable.content[i * 2 + 1])) {
                                                 return false;
                                         }
-                                } else
-                                        return false;
+                                } else return false;
                                 datas++;
                         } else {
                                 var mutableSubnode = (Node<?, ?>) mutable.content[i * 2 + 1];
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
index 7c3cf7e8..9d15a0d7 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/MutableNode.java
@@ -7,15 +7,15 @@ import tools.refinery.store.map.ContinousHashProvider;
 
 public class MutableNode<K, V> extends Node<K, V> {
         int cachedHash;
+        protected boolean cachedHashValid;
         protected Object[] content;
 
         protected MutableNode() {
                 this.content = new Object[2 * FACTOR];
-                updateHash();
+                invalidateHash();
         }
 
-        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue) {
+        public static <K, V> MutableNode<K, V> initialize(K key, V value, ContinousHashProvider<? super K> hashProvider, V defaultValue) {
                 if (value == defaultValue) {
                         return null;
                 } else {
@@ -24,7 +24,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                         MutableNode<K, V> res = new MutableNode<>();
                         res.content[2 * fragment] = key;
                         res.content[2 * fragment + 1] = value;
-                        res.updateHash();
+                        res.invalidateHash();
                         return res;
                 }
         }
@@ -32,7 +32,7 @@ public class MutableNode<K, V> extends Node<K, V> {
         /**
          * Constructs a {@link MutableNode} as a copy of an {@link ImmutableNode}
          *
-         * @param node
+         * @param node to be transformed
          */
         protected MutableNode(ImmutableNode<K, V> node) {
                 this.content = new Object[2 * FACTOR];
@@ -49,27 +49,24 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 nodeUsed++;
                         }
                 }
-                this.cachedHash = node.hashCode();
+                this.cachedHashValid = false;
         }
 
         @Override
         public V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
-                @SuppressWarnings("unchecked")
-                K keyCandidate = (K) this.content[2 * selectedHashFragment];
+                @SuppressWarnings("unchecked") K keyCandidate = (K) this.content[2 * selectedHashFragment];
                 if (keyCandidate != null) {
                         if (keyCandidate.equals(key)) {
-                                @SuppressWarnings("unchecked")
-                                V value = (V) this.content[2 * selectedHashFragment + 1];
+                                @SuppressWarnings("unchecked") V value = (V) this.content[2 * selectedHashFragment + 1];
                                 return value;
                         } else {
                                 return defaultValue;
                         }
                 } else {
-                        @SuppressWarnings("unchecked")
-                        var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
                         if (nodeCandidate != null) {
-                                int newDepth = depth + 1;
+                                int newDepth = incrementDepth(depth);
                                 int newHash = newHash(hashProvider, key, hash, newDepth);
                                 return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth);
                         } else {
@@ -79,11 +76,9 @@ public class MutableNode<K, V> extends Node<K, V> {
         }
 
         @Override
-        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider,
-                        V defaultValue, int hash, int depth) {
+        public Node<K, V> putValue(K key, V value, OldValueBox<V> oldValueBox, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth) {
                 int selectedHashFragment = hashFragment(hash, shiftDepth(depth));
-                @SuppressWarnings("unchecked")
-                K keyCandidate = (K) content[2 * selectedHashFragment];
+                @SuppressWarnings("unchecked") K keyCandidate = (K) content[2 * selectedHashFragment];
                 if (keyCandidate != null) {
                         // If has key
                         if (keyCandidate.equals(key)) {
@@ -107,18 +102,17 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 }
                         }
                 } else {
-                        // If it does not have key, check for nodeId
-                        @SuppressWarnings("unchecked")
-                        var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
+                        // If it does not have key, check for value
+                        @SuppressWarnings("unchecked") var nodeCandidate = (Node<K, V>) content[2 * selectedHashFragment + 1];
                         if (nodeCandidate != null) {
-                                // If it has nodeId, it is a subnode -> upate that
-                                var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue,
-                                                newHash(hashProvider, key, hash, depth + 1), depth + 1);
-                                return updateWithSubNode(selectedHashFragment, newNode, value.equals(defaultValue));
+                                // If it has value, it is a subnode -> upate that
+                                int newDepth = incrementDepth(depth);
+                                var newNode = nodeCandidate.putValue(key, value, oldValueBox, hashProvider, defaultValue, newHash(hashProvider, key, hash, newDepth), newDepth);
+                                return updateWithSubNode(selectedHashFragment, newNode, (value == null && defaultValue == null) || (value != null && value.equals(defaultValue)));
                         } else {
-                                // If it does not have nodeId, put it in the empty place
+                                // If it does not have value, put it in the empty place
                                 if (value == defaultValue) {
-                                        // dont need to add new key-nodeId pair
+                                        // dont need to add new key-value pair
                                         oldValueBox.setOldValue(defaultValue);
                                         return this;
                                 } else {
@@ -133,30 +127,31 @@ public class MutableNode<K, V> extends Node<K, V> {
                 content[2 * selectedHashFragment] = key;
                 oldValueBox.setOldValue(defaultValue);
                 content[2 * selectedHashFragment + 1] = value;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         /**
-         * Updates an entry in a selected hash-fragment to a non-default nodeId.
+         * Updates an entry in a selected hash-fragment to a non-default value.
          *
-         * @param value
-         * @param selectedHashFragment
-         * @return
+         * @param value new value
+         * @param selectedHashFragment position of the value
+         * @return updated node
          */
         @SuppressWarnings("unchecked")
         Node<K, V> updateValue(V value, OldValueBox<V> oldValue, int selectedHashFragment) {
                 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
                 content[2 * selectedHashFragment + 1] = value;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         /**
+         * Updates an entry in a selected hash-fragment with a subtree.
          *
-         * @param selectedHashFragment
-         * @param newNode
-         * @return
+         * @param selectedHashFragment position of the value
+         * @param newNode the subtree
+         * @return updated node
          */
         Node<K, V> updateWithSubNode(int selectedHashFragment, Node<K, V> newNode, boolean deletionHappened) {
                 if (deletionHappened) {
@@ -164,7 +159,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                                 // Check whether this node become empty
                                 content[2 * selectedHashFragment + 1] = null; // i.e. the new node
                                 if (hasContent()) {
-                                        updateHash();
+                                        invalidateHash();
                                         return this;
                                 } else {
                                         return null;
@@ -178,7 +173,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                                                 // orphan subnode data is replaced with data
                                                 content[2 * selectedHashFragment] = immutableNewNode.content[orphaned * 2];
                                                 content[2 * selectedHashFragment + 1] = immutableNewNode.content[orphaned * 2 + 1];
-                                                updateHash();
+                                                invalidateHash();
                                                 return this;
                                         }
                                 }
@@ -186,15 +181,13 @@ public class MutableNode<K, V> extends Node<K, V> {
                 }
                 // normal behaviour
                 content[2 * selectedHashFragment + 1] = newNode;
-                updateHash();
+                invalidateHash();
                 return this;
-
         }
 
         private boolean hasContent() {
                 for (Object element : this.content) {
-                        if (element != null)
-                                return true;
+                        if (element != null) return true;
                 }
                 return false;
         }
@@ -221,23 +214,20 @@ public class MutableNode<K, V> extends Node<K, V> {
         }
 
         @SuppressWarnings("unchecked")
-        private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue,
-                        K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
+        private Node<K, V> moveDownAndSplit(ContinousHashProvider<? super K> hashProvider, K newKey, V newValue, K previousKey, int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) {
                 V previousValue = (V) content[2 * selectedHashFragmentOfCurrentDepth + 1];
 
-                MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue,
-                                hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, depth + 1);
+                MutableNode<K, V> newSubNode = newNodeWithTwoEntries(hashProvider, previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), newKey, newValue, hashOfNewKey, incrementDepth(depth));
 
                 content[2 * selectedHashFragmentOfCurrentDepth] = null;
                 content[2 * selectedHashFragmentOfCurrentDepth + 1] = newSubNode;
-                updateHash();
+                invalidateHash();
                 return this;
         }
 
         // Pass everything as parameters for performance.
         @SuppressWarnings("squid:S107")
-        private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1,
-                        int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
+        private MutableNode<K, V> newNodeWithTwoEntries(ContinousHashProvider<? super K> hashProvider, K key1, V value1, int oldHash1, K key2, V value2, int oldHash2, int newdepth) {
                 int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth);
                 int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth);
                 int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth));
@@ -251,11 +241,10 @@ public class MutableNode<K, V> extends Node<K, V> {
                         subNode.content[newFragment2 * 2] = key2;
                         subNode.content[newFragment2 * 2 + 1] = value2;
                 } else {
-                        MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2,
-                                        newHash2, newdepth + 1);
+                        MutableNode<K, V> subSubNode = newNodeWithTwoEntries(hashProvider, key1, value1, newHash1, key2, value2, newHash2, incrementDepth(newdepth));
                         subNode.content[newFragment1 * 2 + 1] = subSubNode;
                 }
-                subNode.updateHash();
+                subNode.invalidateHash();
                 return subNode;
         }
 
@@ -265,7 +254,7 @@ public class MutableNode<K, V> extends Node<K, V> {
                 oldValue.setOldValue((V) content[2 * selectedHashFragment + 1]);
                 content[2 * selectedHashFragment + 1] = null;
                 if (hasContent()) {
-                        updateHash();
+                        invalidateHash();
                         return this;
                 } else {
                         return null;
@@ -374,10 +363,9 @@ public class MutableNode<K, V> extends Node<K, V> {
                 // print subnodes
                 for (int i = 0; i < FACTOR; i++) {
                         if (content[2 * i] == null && content[2 * i + 1] != null) {
-                                @SuppressWarnings("unchecked")
-                                Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
+                                @SuppressWarnings("unchecked") Node<K, V> subNode = (Node<K, V>) content[2 * i + 1];
                                 builder.append("\n");
-                                subNode.prettyPrint(builder, depth + 1, i);
+                                subNode.prettyPrint(builder, incrementDepth(depth), i);
                         }
                 }
         }
@@ -394,57 +382,69 @@ public class MutableNode<K, V> extends Node<K, V> {
                 // check the place of data
                 for (int i = 0; i < FACTOR; i++) {
                         if (this.content[2 * i] != null) {
-                                @SuppressWarnings("unchecked")
-                                K key = (K) this.content[2 * i];
-                                @SuppressWarnings("unchecked")
-                                V value = (V) this.content[2 * i + 1];
+                                @SuppressWarnings("unchecked") K key = (K) this.content[2 * i];
+                                @SuppressWarnings("unchecked") V value = (V) this.content[2 * i + 1];
 
                                 if (value == defaultValue) {
-                                        throw new IllegalStateException("Node contains default nodeId!");
+                                        throw new IllegalStateException("Node contains default value!");
                                 }
                                 int hashCode = hashProvider.getHash(key, hashDepth(depth));
                                 int shiftDepth = shiftDepth(depth);
                                 int selectedHashFragment = hashFragment(hashCode, shiftDepth);
                                 if (i != selectedHashFragment) {
-                                        throw new IllegalStateException("Key " + key + " with hash code " + hashCode
-                                                        + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
+                                        throw new IllegalStateException("Key " + key + " with hash code " + hashCode + " is in bad place! Fragment=" + selectedHashFragment + ", Place=" + i);
                                 }
                         }
                 }
                 // check subnodes
                 for (int i = 0; i < FACTOR; i++) {
                         if (this.content[2 * i + 1] != null && this.content[2 * i] == null) {
-                                @SuppressWarnings("unchecked")
-                                var subNode = (Node<K, V>) this.content[2 * i + 1];
-                                subNode.checkIntegrity(hashProvider, defaultValue, depth + 1);
+                                @SuppressWarnings("unchecked") var subNode = (Node<K, V>) this.content[2 * i + 1];
+                                subNode.checkIntegrity(hashProvider, defaultValue, incrementDepth(depth));
                         }
                 }
                 // check the hash
-                int oldHash = this.cachedHash;
-                updateHash();
-                int newHash = this.cachedHash;
-                if (oldHash != newHash) {
-                        throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
+                if (cachedHashValid) {
+                        int oldHash = this.cachedHash;
+                        invalidateHash();
+                        int newHash = hashCode();
+                        if (oldHash != newHash) {
+                                throw new IllegalStateException("Hash code was not up to date! (old=" + oldHash + ",new=" + newHash + ")");
+                        }
                 }
         }
 
-        protected void updateHash() {
-                this.cachedHash = Arrays.hashCode(content);
+        protected void invalidateHash() {
+                this.cachedHashValid = false;
         }
 
         @Override
         public int hashCode() {
-                return this.cachedHash;
+                if (this.cachedHashValid) {
+                        return this.cachedHash;
+                } else {
+                        this.cachedHash = Arrays.hashCode(content);
+                        this.cachedHashValid = true;
+                        return this.cachedHash;
+                }
         }
 
         @Override
         public boolean equals(Object obj) {
-                if (this == obj)
-                        return true;
-                if (obj == null)
-                        return false;
+                if (this == obj) return true;
+                if (obj == null) return false;
                 if (obj instanceof MutableNode<?, ?> mutableObj) {
-                        return Arrays.deepEquals(this.content, mutableObj.content);
+                        if (obj.hashCode() != this.hashCode()) {
+                                return false;
+                        } else {
+                                for (int i = 0; i < FACTOR * 2; i++) {
+                                        Object thisContent = this.content[i];
+                                        if (thisContent != null && !thisContent.equals(mutableObj.content[i])) {
+                                                return false;
+                                        }
+                                }
+                                return true;
+                        }
                 } else if (obj instanceof ImmutableNode<?, ?> immutableObj) {
                         return ImmutableNode.compareImmutableMutable(immutableObj, this);
                 } else {
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
index 2260cd5b..c49be280 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/Node.java
@@ -4,82 +4,121 @@ import java.util.Map;
 
 import tools.refinery.store.map.ContinousHashProvider;
 
-public abstract class Node<K,V>{
+public abstract class Node<K, V> {
         public static final int BRANCHING_FACTOR_BITS = 5;
-        public static final int FACTOR = 1<<BRANCHING_FACTOR_BITS;
+        public static final int FACTOR = 1 << BRANCHING_FACTOR_BITS;
         protected static final int NUMBER_OF_FACTORS = Integer.SIZE / BRANCHING_FACTOR_BITS;
-        protected static final int FACTOR_MASK = FACTOR-1;
+        protected static final int FACTOR_MASK = FACTOR - 1;
         public static final int EFFECTIVE_BITS = BRANCHING_FACTOR_BITS * NUMBER_OF_FACTORS;
+        public static final int FACTOR_SELECTION_BITS = 32 - Integer.numberOfLeadingZeros(NUMBER_OF_FACTORS);
+        public static final int FACTOR_SELECTION_MASK = (1 << FACTOR_SELECTION_BITS) - 1;
+        public static final int INCREMENT_BIG_STEP = (1 << FACTOR_SELECTION_BITS) - NUMBER_OF_FACTORS;
+
+        /**
+         * Increments the depth of the search in the tree. The depth parameter has two
+         * components: the least few bits selects the fragment of the hashcode, the
+         * other part selects the continuous hash.
+         *
+         * @param depth parameter encoding the fragment and the depth
+         * @return new depth.
+         */
+        protected int incrementDepth(int depth) {
+                int newDepth = depth + 1;
+                if ((newDepth & FACTOR_SELECTION_MASK) == NUMBER_OF_FACTORS) {
+                        newDepth += INCREMENT_BIG_STEP;
+                }
+                return newDepth;
+        }
 
         /**
          * Calculates the index for the continuous hash.
+         *
          * @param depth The depth of the node in the tree.
          * @return The index of the continuous hash.
          */
         protected static int hashDepth(int depth) {
-                return depth/NUMBER_OF_FACTORS;
+                return depth >> FACTOR_SELECTION_BITS;
         }
 
         /**
          * Calculates the which segment of a single hash should be used.
+         *
          * @param depth The depth of the node in the tree.
          * @return The segment of a hash code.
          */
         protected static int shiftDepth(int depth) {
-                return depth%NUMBER_OF_FACTORS;
+                return depth & FACTOR_SELECTION_MASK;
         }
+
         /**
          * Selects a segments from a complete hash for a given depth.
-         * @param hash A complete hash.
+         *
+         * @param hash       A complete hash.
          * @param shiftDepth The index of the segment.
          * @return The segment as an integer.
          */
         protected static int hashFragment(int hash, int shiftDepth) {
-                if(shiftDepth<0 || Node.NUMBER_OF_FACTORS<shiftDepth) throw new IllegalArgumentException("Invalid shift depth! valid intervall=[0;5], input="+shiftDepth);
-                return (hash >>> shiftDepth*BRANCHING_FACTOR_BITS) & FACTOR_MASK;
+                if (shiftDepth < 0 || Node.NUMBER_OF_FACTORS < shiftDepth)
+                        throw new IllegalArgumentException("Invalid shift depth! valid interval=[0;5], input=" + shiftDepth);
+                return (hash >>> shiftDepth * BRANCHING_FACTOR_BITS) & FACTOR_MASK;
         }
 
         /**
-         * Returns the hash code for a given depth. It may calculate new hash code, or reuse a hash code calculated for depth-1.
-         * @param key The key.
-         * @param hash Hash code for depth-1
+         * Returns the hash code for a given depth. It may calculate new hash code, or
+         * reuse a hash code calculated for depth-1.
+         *
+         * @param key   The key.
+         * @param hash  Hash code for depth-1
          * @param depth The depth.
          * @return The new hash code.
          */
         protected int newHash(final ContinousHashProvider<? super K> hashProvider, K key, int hash, int depth) {
-                final int hashDepth = hashDepth(depth);
-                if(hashDepth>=ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
-                        throw new IllegalArgumentException("Key "+key+" have the clashing hashcode over the practical depth limitation ("+ContinousHashProvider.MAX_PRACTICAL_DEPTH+")!");
+                final int shiftDepth = shiftDepth(depth);
+                if (shiftDepth == 0) {
+                        final int hashDepth = hashDepth(depth);
+                        if (hashDepth >= ContinousHashProvider.MAX_PRACTICAL_DEPTH) {
+                                throw new IllegalArgumentException(
+                                                "Key " + key + " have the clashing hashcode over the practical depth limitation ("
+                                                                + ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
+                        }
+                        return hashProvider.getHash(key, hashDepth);
+                } else {
+                        return hash;
                 }
-                return depth%NUMBER_OF_FACTORS == 0?
-                                hashProvider.getHash(key, hashDepth) :
-                                hash;
         }
 
+        public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash,
+                                                           int depth);
+
+        public abstract Node<K, V> putValue(K key, V value, OldValueBox<V> old,
+                                                                                ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
 
-        public abstract V getValue(K key, ContinousHashProvider<? super K> hashProvider, V defaultValue,  int hash, int depth);
-        public abstract Node<K,V> putValue(K key, V value, OldValueBox<V> old, ContinousHashProvider<? super K> hashProvider, V defaultValue, int hash, int depth);
         public abstract long getSize();
 
         abstract MutableNode<K, V> toMutable();
-        public abstract ImmutableNode<K, V> toImmutable(
-                        Map<Node<K, V>,ImmutableNode<K, V>> cache);
+
+        public abstract ImmutableNode<K, V> toImmutable(Map<Node<K, V>, ImmutableNode<K, V>> cache);
+
         protected abstract MutableNode<K, V> isMutable();
+
         /**
          * Moves a {@link MapCursor} to its next position.
+         *
          * @param cursor the cursor
-         * @return Whether there was a next nodeId to move on.
+         * @return Whether there was a next value to move on.
          */
-        abstract boolean moveToNext(MapCursor<K,V> cursor);
+        abstract boolean moveToNext(MapCursor<K, V> cursor);
 
         ///////// FOR printing
         public abstract void prettyPrint(StringBuilder builder, int depth, int code);
+
         @Override
         public String toString() {
                 StringBuilder stringBuilder = new StringBuilder();
                 prettyPrint(stringBuilder, 0, -1);
                 return stringBuilder.toString();
         }
-        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {}
 
+        public void checkIntegrity(ContinousHashProvider<? super K> hashProvider, V defaultValue, int depth) {
+        }
 }
diff --git a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
index 301bcb95..57256472 100644
--- a/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
+++ b/subprojects/store/src/main/java/tools/refinery/store/map/internal/VersionedMapImpl.java
@@ -18,7 +18,6 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
         protected final VersionedMapStoreImpl<K, V> store;
 
         protected final ContinousHashProvider<K> hashProvider;
-
         protected final V defaultValue;
         protected Node<K, V> root;
 
@@ -109,6 +108,7 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
 
         @Override
         public DiffCursor<K, V> getDiffCursor(long toVersion) {
+
                 Cursor<K, V> fromCursor = this.getAll();
                 VersionedMap<K, V> toMap = this.store.createMap(toVersion);
                 Cursor<K, V> toCursor = toMap.getAll();
@@ -131,13 +131,35 @@ public class VersionedMapImpl<K, V> implements VersionedMap<K, V> {
                 root = this.store.revert(state);
         }
 
-        public void prettyPrint() {
-                StringBuilder s = new StringBuilder();
+        @Override
+        public int hashCode() {
+                final int prime = 31;
+                int result = 1;
+                result = prime * result + ((root == null) ? 0 : root.hashCode());
+                return result;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+                if (this == obj)
+                        return true;
+                if (obj == null)
+                        return false;
+                if (getClass() != obj.getClass())
+                        return false;
+                VersionedMapImpl<?, ?> other = (VersionedMapImpl<?, ?>) obj;
+                if (root == null) {
+                        return other.root == null;
+                } else return root.equals(other.root);
+        }
+
+        public String prettyPrint() {
                 if (this.root != null) {
+                        StringBuilder s = new StringBuilder();
                         this.root.prettyPrint(s, 0, -1);
-                        System.out.println(s.toString());
+                        return s.toString();
                 } else {
-                        System.out.println("empty tree");
+                        return "empty tree";
                 }
         }