Why does Python use hash table to implement dict, but not Red-Black Tree?
What is the key? Performance?
Software Engineering Stack Exchange is a question and answer site for professionals, academics, and students working within the systems development life cycle. It only takes a minute to sign up.Sign up to join this community
This is a general, non-Python-specific answer.
| Hash Table | Red-Black Tree | -------+-------------+---------------------+ Space | O(n) : O(n) | O(n) : O(n) | Insert | O(1) : O(n) | O(log n) : O(log n) | Fetch | O(1) : O(n) | O(log n) : O(log n) | Delete | O(1) : O(n) | O(log n) : O(log n) | | avg :worst | average : worst |
The problem with hash tables is that hashes can collide. There are various mechanisms to resolve collisions, e.g. open addressing or separate chaining. The absolute worst case is that all keys have the same hash code, in which case a hash table will degrade into a linked list.
In all other cases, a hash table is a great data structure that's easy to implement and delivers good performance. A downside is that implementations that can quickly grow the table and redistribute their entries will likely waste nearly as much memory as is actually being used.
RB-Trees are self-balancing and do not change their algorithmic complexity in a worst case. However, they are more difficult to implement. Their average complexities are also worse than that of a hash table.
All keys in a hash table must be hashable and comparable for equality among each other. This is especially easy for strings or integers, but is also fairly straightforward to extend to user-defined types. In some languages like Java these properties are guaranteed by definition.
Keys in an RB-Tree must have a total order: each key must be comparable with any other key, and the two keys must either compare smaller, greater, or equal. This ordering equality must be equivalent to semantic equality. This is straightforward for integers and other numbers, also fairly easy for strings (the order need only be consistent and not externally observable, so the order does not need to consider locales), but difficult for other types that have no inherent order. It is absolutely impossible to have keys of different types unless some comparison between them is possible.
: Actually, I'm wrong here. Two strings may not be byte-equal but still be equivalent according to the rules of some language. See e.g. Unicode normalizations for one example where two equal strings are encoded differently. Whether Unicode character composition matters for your hash key is something that a hash table implementation cannot know.
One might think that a cheap solution for RB-Tree keys would be to first test for equality, then compare identity (i.e. compare pointers). However, this ordering would not be transitive: If
a == b and
id(a) > id(c), then it must follow that
id(b) > id(c) as well, which is not guaranteed here. So instead, we might use the hash code of keys as the lookup keys. Here, the ordering works correctly, but we might end up with multiple distinct keys with the same hash code, which will be assigned to the same node in the RB tree. To solve these hash collisions we can use separate chaining just like with hash tables, but this also inherits the worst case behaviour for hash tables – the worst of both worlds.
I expect to a hash table to have better memory locality than a tree, because a hash table is essentially just an array.
Entries in both data structures have a fairly high overhead:
Insertions and deletions in an RB-tree involve tree rotations. These aren't really costly, but do involve an overhead. In a hash, insertion and deletion are no more expensive than a simple access (although resizing a hash table upon insertion is an
Hash tables are inherently mutable, whereas an RB-tree could also be implemented in an immutable fashion. However, this is rarely useful.
There are a whole range of reasons that might be true, but the key ones are likely to be:
Easier to write/maintain, and a performance winner in typical use cases? Sign me up, please!