Ordered Sets and Maps

Hashtables are fantastic at what they do (which is why Python has chosen them for their implementation of sets and maps). They are \(O(1)\) (amortized) at insertion and \(O(1)\) at accessing. They are easy to implement. There really aren’t many downsides.

There is one big downside though, which is that hashtables can really only be used for these Set and Map applications, and there are many related operations that they can’t do. To illustrate these, we introduce the “Ordered Set or Map”.

It is pretty common that we want to iterate through the elements of a set or map in some sort of organized order. Let’s think about iterating through the elements of a Set implemented with a hashtable. The easiest way would be to start at index 0, and (if implemented with separate chaining) list everything in index 0, then everything in index 1, then index 2, etc. However, since a good hash function destroys any patterns in incoming data, they’ll come out in a random-seeming order. This is in fact what we see when we use Python sets or dictionaries. We illustrate below with a Python set of some of my daughter’s favorite things:

>>> favorite = {'bunny','mommy','daddy','playground','grandma','puddles'}
>>> for thing in favorite:
...   print(thing)
... 
puddles
playground
grandma
bunny
mommy
daddy

If we want these to be in sorted order, or if we want to execute a range() operation (like we discussed for B+ Trees, or, give me everything my daughter likes that starts with ‘p’), we still have to iterate through everything, because a thing that starts with ‘p’ could be anywhere in the array. On the other hand, if the set is implemented in a Tree, these types of operations are much easier, as they are organized in a sorted manner.

In an Ordered Set or Map, we add the following functions to the typical set/map functions:

• first(): Return the smallest element of the set or smallest key

• last(): Return the largest element of the set or largest key

• next(k): Return the element or key which comes immediately after key k

• previous(k): Return the element or key which comes immediate before key k

In a set/map implemented with a sorted array or linked list, first and last are \(O(1)\), because they’re right on the ends. previous and next involve finding k, and then getting the next/previous one. This takes the same amount of time as finding k.

In an unsorted array or linked list, you have no choice but to iterate through all elements of the data structure to perform these operations. \(O(n)\).

In a tree, these are all \(O(\log(n))\). The smallest and largest are the leftmost/rightmost elements, and once you’ve found k, the previous and next are no more than \(\log(n)\) away.

In a hashtable, though they are highly organized, they’re not organized in this way, and you must treat them the same as unsorted data structures.

The final Ordered Set/Map runtime table

	UA	SA	ULL	SLL	Tree	HT
insert(e)	1A	n	1	n	log(n)	1A
contains(e)	n	log(n)	n	n	log(n)	1
remove(e)	n	log(n)*	n	n	log(n)	1
first()/last()	n	1	n	1	log(n)	n
prev(k)/next(k)	n	log(n)	n	n	log(n)	n

* Recall that for this removal runtime, we assume removal is rare, and we simply mark elements as removed, rather than physically taking them out. If this gets too unwieldy, we can run the occasional \(O(n)\) removal operation which rebuilds the data structure without all the removed elements (which would make this an amortized runtime). Something similar is often done with Trees. There is an \(O(\log(n))\) algorithm for physically removing elements from a BST which keeps the tree balanced, but it is complex to implement, and so sometimes they are just marked as removed out of coder laziness.