Asterisk - The Open Source Telephony Project  18.5.0
Hash Table support in Asterisk

A hash table is a structure that allows for an exact-match search in O(1) (or close to that) time.

The method: given: a set of {key,val} pairs. (at a minimum). given: a hash function, which, given a key, will return an integer. Ideally, each key in the set will have its own unique associated hash value. This hash number will index into an array. "buckets" are what the elements of this array are called. To handle possible collisions in hash values, buckets can form a list.

The key for a value must be contained in the value, or we won't be able to find it in the bucket list.

This implementation is pretty generic, because:

  1. The value and key are expected to be in a structure (along with other data, perhaps) and it's address is a "void *".
  2. The pointer to a compare function must be passed in at the time of creation, and is stored in the hashtable.
  3. The pointer to a resize function, which returns 1 if the hash table is to be grown. A default routine is provided if the pointer is NULL, and uses the java hashtable metric of a 75% load factor.
  4. The pointer to a "new size" function, which returns a preferable new size for the hash table bucket array. By default, a function is supplied which roughly doubles the size of the array, is provided. This size should ideally be a prime number.
  5. The hashing function pointer must also be supplied. This function must be written by the user to access the keys in the objects being stored. Some helper functions that use a simple "mult by prime, add the next char", sort of string hash, or a simple modulus of the hash table size for ints, is provided; the user can use these simple algorithms to generate a hash, or implement any other algorithms they wish.
  6. Recently updated the hash routines to use Doubly-linked lists for buckets, and added a doubly-linked list that threads thru every bucket in the table. The list of all buckets is on the HashTab struct. The Traversal was modified to go thru this list instead of searching the bucket array for buckets. This also should make it safe to remove a bucket during the traversal. Removal and destruction routines will work faster.