       (array-copy arr (+ 2 idx-old) dst idx-old (- idx-new idx-old))
       (aset dst idx-new node)
       (array-copy arr (+ idx-new 2) dst (inc idx-new) (- (alength arr) idx-new 2))
-      (BitmapIndexedNode. e (bit-or datamap bit) (bit-xor nodemap bit) dst)))
+      (BitmapIndexedNode. e (bit-xor datamap bit) (bit-or nodemap bit) dst)))
+
+  (merge-two-kv-pairs [inode medit shift key1 val1 key2hash key2 val2]
+    (let [key1hash (hash key1)]
+      (if (and (< shift 32) (== key1hash key2hash))
+        (HashCollisionNode. medit key1hash 2 (array key1 val1 key2 val2))
+        (let [mask1 (mask key1hash shift)
+              mask2 (mask key2hash shift)]
+          (if (== mask1 mask2)
+            (let [new-node (.merge-two-kv-pairs inode medit (+ shift 5) key1 val1 key2hash key2 val2)]
+              (BitmapIndexedNode. medit 0 (bitpos key1hash shift) (array new-node)))
+            (let [new-datamap (bit-or (bitpos key1hash shift) (bitpos key2hash shift))]
+              (if (< mask1 mask2)
+                (BitmapIndexedNode. medit new-datamap 0 (array key1 val1 key2 val2))
+                (BitmapIndexedNode. medit new-datamap 0 (array key2 val2 key1 val1)))))))))
 
   (inode-seq [inode]
     (NodeSeq. nil arr (* 2 (bit-count datamap)) (bit-count nodemap) 0 nil nil))

            (.copy-and-set-node inode aedit bit sub-node-new)
            inode))
        :else
        (let [n (bit-count datamap)
              idx (bitmap-indexed-node-index datamap bit)
              new-arr (make-array (* 2 (inc n)))]
          (array-copy arr 0 new-arr 0 (* 2 idx))
          (aset new-arr (* 2 idx) key)
          (aset new-arr (inc (* 2 idx)) val)
          (array-copy arr (* 2 idx) new-arr (* 2 (inc idx)) (* 2 (- n idx)))
          (set! (.-added changed?) true)
          (BitmapIndexedNode. aedit (bit-or datamap bit) nodemap new-arr)))))


              k (aget arr (* 2 idx))]
          (set! (.-modified changed?) true)
          (if (= k key)
            (.copy-and-set-value inode aedit bit val)
            (let [v (aget arr (inc (* 2 idx)))
                  new-node (.merge-two-kv-pairs inode aedit (+ shift 5) k v hash key val)]
              (set! (.-added changed?) true)
              (.copy-and-migrate-to-node inode aedit bit new-node))))
        (not (zero? (bit-and nodemap bit)))
        (let [sub-node (node-at arr nodemap bit)
