Timeline for Is it possible to speed up a hash table by using binary search trees for separate chaining?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 2, 2015 at 19:51 | comment | added | user22815 | @Steve314 right, essentially if the hash table cannot effectively limit the number of elements in each bucket, the asymptotic performance degrades into whatever sub-data structure is used in each bucket. I added a paragraph to my answer to make this clear. | |
| May 2, 2015 at 19:49 | comment | added | user8709 | Good point - e.g. for a constant-sized hash table with unbounded data, the asymptotic performance of the hash table is the same as the asymptotic performance of the collision handling - the hash table only changes the constant factors. | |
| May 2, 2015 at 19:48 | history | edited | user22815 | CC BY-SA 3.0 |
Updated terminology to be more consistent, added note about why a BST is desireable in this specific case.
|
| May 2, 2015 at 19:45 | comment | added | user22815 | @Steve314 Keep in mind that the problem is there are a lot of collisions, so he expects a bucket to contain more items than a hash table normally would. | |
| May 2, 2015 at 19:43 | comment | added | user8709 | In asymptotic terms, using a binary tree for collision handling doesn't change expected performance of a hash table provided that the hash table already did the usual tricks to achieve amortized O(1) performance anyway. Resizing the hashtable to ensure good performance means that the expected items per bucket (the size of binary trees) is expected to be small too, so you end up with the same expected amortized O(1) either way. Even for worst case - without any balancing constraint specified, worst case performance for a binary tree is that it ends up behaving like a linked list anyway. | |
| May 2, 2015 at 18:41 | history | answered | user22815 | CC BY-SA 3.0 |