handling collisions in associative array implemented using self-balancing tree

Question

How are collisions handled in associative arrays implemented using self-balanced tree? If two objects have same hash are they stored in a linked list attached to a tree node or two nodes are created? In it's the former, then how it is O(log n) and if latter, how binary search tree can handle same keys (hashes)?

Answer 1

Search trees can definitely not handle two nodes with the same key, so you do need to store the entries with colliding keys in a separate data structure (typically, as you say, a linked list attached to a tree node). You will indeed not have a worst-case complexity of O(log n), just as an associative array implemented as a hash table will not have worst-case O(1) operations.

As epitaph notes, one thing to try is increasing the length of your hash keys, so as to not get collisions. You can't guarantee that you won't, though, and do need to make some sort of provision for two objects with the same hash. If you choose your hashing algorithm properly, though, this should be a rare case, and your average time complexity for lookups will be O(log n), even though it can degrade to O(n) in the degenerate case of everything having the same hash key.