News for hackers. Stuff that matters.
Re:Naggum Nugget by Psyonic on Tuesday November 02, 2010 @08:20PM (#1863017)
This exists, it's just generally not done because your buckets should be small enough that linear search is fastest.

From the wikipedia hash table article (http://en.wikipedia.org/wiki/Hash_table#Separate_chaining_wi...):

Instead of a list, one can use any other data structure that supports the required operations. By using a self-balancing tree, for example, the theoretical worst-case time of a hash table can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory cost if long delays must be avoided at all costs (e.g. in a real-time application), or if one expects to have many entries hashed to the same slot (e.g. if one expects extremely non-uniform or even malicious key distributions).

There are no comments on this comment yet.