[icholy]

Yeah, who needs O(1) deletes anyway? /s

[lifthrasiir]

In case you haven't realized yet, a hash table that maintains the insertion order can be still do O(1) deletes as long as the key order doesn't change arbitrarily after the initial insertion.

[icholy]

I'm commenting on the proposed implementation of using an array to keep track of insertion order.

[lifthrasiir]

An array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)

[icholy]

> An array can be used to efficiently simulate a linked list

That's obviously not what the OP meant. Also, I don't think there's an efficient way of implementing deletes with an array backed linked list.

[mjevans]

That depends on what someone is willing to compromise. Extra space to point back at exactly that key (but that also needs to be updated each compaction?); personally I'd normally rather pay the lookup or key sort on iterator snapshot fee. An 'insert, or re-sorted order' side index which allows for nodes to be marked as 'deleted' (maybe nil / null, maybe a sentinel value meaning skip?); I might propose that to see if it fit the requirements well enough.

[icholy]

... or just use a normal linked list with the existing entries like a sane person.