Hey, I know you.
reply> all the operations are O(n)
Not true, fortunately!
The cat-gets pattern for insertion is clearly just an O(1) append. Similar for the replicate-gets in the deletion.
Finding the deletion mask might be O(n) or O(log n), depending[0] on the size of your search space.
Key is effectively just a radix sort, which is indeed O(n) on the keys, but a trad hashmap doesn't get any better in this case.
[0]:https://help.dyalog.com/19.0/#Language/Defined%20Functions%2...
The append is the only thing that is O(1), finding the deletion mask is linear (≠ is linear, isn't it?) and the actual deletion is also linear (⌿ is also linear).
reply ]runtime -repeat=1s 'v←k1 ⋄ v⌿⍨←v≠2'
\* Benchmarking "v←k1 ⋄ v⌿⍨←v≠2", repeat=1s
┌──────────┬──────────────┐
│ │(ms) │
├──────────┼──────────────┤
│CPU (avg):│0.008491847826│
├──────────┼──────────────┤
│Elapsed: │0.008466372283│
└──────────┴──────────────┘
]runtime -repeat=1s 'v←k2 ⋄ v⌿⍨←v≠2'
\* Benchmarking "v←k2 ⋄ v⌿⍨←v≠2", repeat=1s
┌──────────┬────────────┐
│ │(ms) │
├──────────┼────────────┤
│CPU (avg):│0.8333333333│
├──────────┼────────────┤
│Elapsed: │0.83 │
└──────────┴────────────┘