• Immutable Page
  • Info
  • Attachments

FAQ/HashTables

What is it ? Mechanics and mechanisms

Usage Patterns

Usage sample

Internals

Data Structure

Major Operations

Reference Usages in the Linux Kernel

Experience – what worked and more importantly what didn’t work & gotchas

  • For tables less than 50 elements or so, binary search will give more performance than hash tables

  • Collision and how to handle collisions is an important factor in designing around hash tables

  • There are schemes that generate a perfect hash function, given a set of elements

  • While there is no clear size, from my experience, 16 bit hashes that give 65536 elements is a good start

  • You can have global and local hash tables ie smaller hash tables than a big hash tables that contains all the elements

Discussions & Notes

<KS 8 Feb, 07> I have started the template and am slowly filling in the details. Please contribute as you see fit. Cheers  </KS> 

Tell others about this page:

last edited 2007-02-09 00:15:58 by dhcp-171-71-29-102