 It is worth noting that a self-balancing binary search tree can be used to implement the buckets for a hash table that uses separate chaining.This allows for average-case constant lookup, but assures a worst-case performance of O(log "n").However, this introduces extra complexity into the implementation, and may cause even worse performance for smaller hash tables, where the time spent inserting into and balancing the tree is greater than the time needed to perform a linear search on all of the elements of a linked list or similar data structure.