Various hashtable facts and findings

The N value (number of buckets) given in /hmake is increased with one if the given value is even, meaning all hashtables have an odd number of buckets.

The range of the N value as specified with /hmake is 1..10000, making the possible hashtable sizes all odd numbers from 1 to 10001 inclusive.

Each hashtable bucket uses exactly 4 bytes. Therefore, memory consumption for the buckets part of the hashtable (excluding storage of the hashtable name etc, and all of the items), is 4*N bytes.

Hashtable names are limited to 90 characters.

The hash function used by mIRC for hashtable items is the following piece of C code (posted on the old message boards by Khaled, saved by qwerty):

u_int r, i;
r = 0;
while (*string) {
  i = *string;
  r ^= i;
  r <<= 1;
  string++;
}
return r;

The resulting value is taken modulo N to determine which bucket to use for the given item. Note that item comparison is case insensitive: in mIRC 6.x, the input string is first converted to lowercase; in mIRC 7.x, it is first converted to uppercase.

The set of items associated with each bucket is a simple linked list; using hashtable size 1 therefore results in a linked list data structure. New items are added at the head of the list, i.e. $hget(size1hashtable,1).item will always return the last added item, if any. Changing the value of an existing item does not change its position in the linked list; deleting an item does not affect the order of the other items.

hashtables.txt · Last modified: 2011/10/17 23:51 (external edit)
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki