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

• Kruse 8
• Standish 11
• Langsam 7.4
• Sedgewick 16

• A method which resolves what to do when there is a collision.
• We consider two methods: Linear Probing and Chaining.

• Is a linear search through the hash table, starting at where the collision occurred.
• As the table becomes half full, there is a tendency for clustering to occur.
• Deletion of records is difficult.

• Clustering is when records start to appear in long groups of adjacent positions.

• Uses a Linked List at each point of the Hash Table.

• It allows simply and efficient handling of collisions.
• Deletions of records are easy.
• Allows more records to be stored in a Hash Table

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