Open Addressing

Open Addressing is a #collition resolution strategy for 202112122035 where alternative cells are tried until an empty cell is found.

Analysis

Attention

  • Only Lazy Deletion is practical for Deletion strategy in Open Addressing
  • Use 202112141313# when the Table reached half full

Implementation

There are different strategies for Open Addressing:

The general implementation is the same: 

#ifndef _HashOpen_H

typedef unsigned int Index;
typedef Index Position;

struct HashTbl;
typedef struct HashTbl *HashTable;

HashTable InitializeTable(int TableSize);
void DestroyTable(HashTable H);
Position Find(ElementType Key, HashTable H);
void Insert(ElementType Key, HashTable H);
ElementType Retrieve(Position P, HashTable H);
HashTable Rehash(HashTable H);
// Delete
// Make Empty

#endif  // _HashOpen_H
enum KindOfEntry { Legitimate, Empty, Deleted };

struct HashEntry {
  ElementType       Element;
  enum KindOfEntry  Info;
};

typedef struct HashEntry Cell;

/**
 *  Cell *TheCells will be an array of
 *  HashEntry cells, allocated later
 */
struct HashTbl {
  int   TableSize;
  Cell *TheCells;
};

HashTable InitializeTable(int TableSize) {
  HashTable H;

  if (TableSize < MinTableSize) {
    Error("Table size too small");
    return NULL;
  }

  // Allocate table
  H = malloc(sizeof(struct HashTbl));
  if (H == NULL)
    FatalError("Out of space!!!");

  H->TableSize = NextPrime(TableSize);

  // Allocate array of Cells
  H->TheCells = malloc(sizeof(Cell) * H->TableSize);
  if (H->TheCells == NULL)
    FatalError("Out of space!!!");

  for (int i = 0; i < H->TableSize; i++)
    H->TheCells[i].Info = Empty;
  
  return H;
}

Position Find(ElementType Key, HashTable H) {
  Position CurrentPos;
  int CollisionNum;

  CollisionNum = 0;
  CurrentPos = Hash(Key, H->TableSize);
  while (H->TheCells[CurrentPos].Info != Empty &&
         H->TheCells[CurrentPos].Element != Key)
  {
    // Linear Probing
    CurrentPos++;
    // Quadradic Probing
    CurrentPos += 2 * ++CollisionNum - 1;
    // Double Hashing
    CurrentPos += Hash2(Key, H->TableSize);
    if (CurrentPos >= H->TableSize)
      CurrentPos -= H->TableSize;
  }

  return CurrentPos;
}

void Insert(ElementType Key, HashTable H) {
  Position Pos;

  Pos = Find(Key, H);
  if (H->TheCells[Pos].Info != Legitimate) {  // Ok to insert here
    H->TheCells[Pos].Info = Legitimate;
    H->TheCells[Pos].Element = Key;
  }
}
Links to this page
#data-structure #hash-table