6 ms·
Actually, in a closed bucket hash table why would you use a linked list and not some kind of tree structure in the leaves?
by ma2rten 5y ago
Actually, in a closed bucket hash table why would you use a linked list and not some kind of tree structure in the leaves?
- xxs 5y agoIt requires not only a hashing function but a comparing one. Also it's not beneficial at lower size as 'compare' might fully derefences the keys (esp. if they are composite) and it's log2N is not that lower than just N. So dynamically switching between a linked list and a rb tree (or a trie) is quite practical and done in the real world, e.g. Java's HashMap