Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A15 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A15 notes: Hash Tables - Collision Resolution

In this lecture

Reading: Collision Resolution Linear Probing What is clustering? Chaining Advantages of Chaining

Algorithms for this lecture

/* insertion using linear probing */
module insert(item)
{
  count = 0
  position = hash(key of item)
  loop
  {
    if (count == hashTableSize) then
    {
        output "Table is Full"
        exit loop
    }

    if (hashTable[position] is empty) then
    {
        hashTable[position] = item
        exit loop
    }
    position = (position + 1) % hashTableSize
    count++
  }
}

/* searching using linear probing */
module search(target)
{
  count = 0
  position = hash(key of target)
  loop
  {
     if (count == hashTableSize) then
     {
        output "Target is not in the Hash Table"
        position = -1
        return -1
     }
     else if  (hashTable[position] is empty) then
     {
         output "Target is not in the Hash Table"
         return -1
     }
     else if  (key of hashTable[position] == target) then
     {
         return position
     }
     position = (position + 1) % hashTableSize
     count++
  }
}

* insertion, deletion, and  searching using chaining */
List hashTable[MAXTABLE];

module InsertChaining(item)
{
   posHash = hash(key of item)
   insert (hashTable[posHash], item);
}

module SearchChaining(item)
{
   posHash = hash(key of item)
   Node* found;

   found = searchList (hashTable[posHash], item);
   return found;
}

module DeleteChaining(item)
{
   posHash = hash(key of item)
   deleteList (hashTable[posHash], item);
}

[ Top | Home ]
Last Updated: Thursday 26 June 2003 11:05:50