Hash Tables

• Construct integer array index out of the (non-integer) key
  static
  Hash(char *string, int len)
  {
      int h;
  
      h = 0;
      while (len--)
          h = (h << 3) ^ *string++;
      if (h < 0)
          return -h;
      return h;
  }
  
• Hash function, converts key into an integer
• A modulo function limits the integer into the size of a table
• A scheme for handling collisions must be provided (unless this is a perfect hash function)
  Atom
  MakeAtom(string, len, makeit)
      char *string;
      unsigned len;
      int makeit;
  {
      AtomListPtr a;
      int         hash;
      int         h;
      int         r;
  
      hash = Hash (string, len);
      if (hashTable)
      {
          h = hash & hashMask;
          if (hashTable[h])
          {
              if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
                  NameEqual (hashTable[h]->name, string, len))
              {
                  return hashTable[h]->atom;
              }
              r = (hash % rehash) | 1;
              for (;;)
              {
                  h += r;
                  if (h >= hashSize)
                      h -= hashSize;
                  if (!hashTable[h])
                      break;
                  if (hashTable[h]->hash == hash && hashTable[h]->len == len &&
                      NameEqual (hashTable[h]->name, string, len))
                  {
                      return hashTable[h]->atom;
                  }
              }
          }
      }
  

• PreviousMaps
• Contents
• NextSets

 Last change: Sunday, March 28, 2004 6:24 pm
 Unless otherwise expressly stated, all original material on this page created by Diomidis Spinellis is licensed under a Creative Commons Attribution-Share Alike 3.0 Greece License.