Ordered hash map or tree

Developers Language Support
1

Is there any support for an ordered hash map or tree or a hash array? If not, does anyone know of any libraries for such collections?

I want an array of objects that can be removed and inserted at any point in the collection. I want to be able to quickly lookup an object (I can’t use the index because the array could have been edited) and insert objects beside it in the collection.

2

I did a quick search and found this. It appears to provide SortedMap and SortedValueMap.

I think it was written by @quint, who might be able to say more about it.

3

Thanks I’ll give it a try.

4

I don’t think that lib is quite it. It doesn’t seem to allow insertions at a specific index. Or am I missing something?

So a use case I want to support is a large piece of text (so it needs ordering), quick look-ups to the characters (so it needs to be a tree or a map), and the ability to insert characters at any point (editing).

5

The backend just needs to make sure the text is ordered - the frontend can parse/transform it easily (JavaScript)

So use keys lexicographically sorted keys in a sorted data structure (Red-Black Trees/BTrees/AVL Trees) and then you just need the character before and after and can find the lexicographic midpoint between the 2 character positions and store that for insertions.

Break your text into chunks to reduce the size & operations involved in insertion/deletion