nextupprevious
Next:3.4.3 Another Example:Up:3.4 Closed HashingPrevious:3.4.1 Rehashing Methods

3.4.2 An Example:

Assume linear probing with the following hashing and rehashing functions:
h(x, 0) = x%7
h(x, i) = (h(x, 0) + i)%7  
Start with an empty table.
     
Insert (20, T) 0 14
Insert (30, T) 1 empty
Insert (9, T) 2 30
Insert (45, T) 3 9
Insert (14, T) 4 45
  5 empty
  6 20
     
Search (35, T) 0 14
Delete (9, T) 1 empty
  2 30
  3 deleted
  4 45
  5 empty
  6 20
     
Search (45, T) 0 14
Search (52, T) 1 empty
Search (9, T) 2 30
Insert (45, T) 3 10
Insert (10, T) 4 45
  5 empty
  6 20
     
Delete (45, T) 0 14
Insert (16, T) 1 empty
  2 30
  3 10
  4 16
  5 empty
  6 20

nextupprevious
Next:3.4.3 Another Example:Up:3.4 Closed HashingPrevious:3.4.1 Rehashing Methods
eEL,CSA_Dept,IISc,Bangalore