I understand hash function and inverted page table, but then the book I read describes something called hashed inverted page table (use hash to accelerate the finding because IPT is large), with TLB used. I don't understand why there is an arrow point to itself inside the hash table? Could anyone explain the mechanism?

my h-IPT

  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – D.W. Dec 9 '18 at 21:18

From your picture, one definitely see a hash table collision solution. If one carefully examine it, will see that the table uses itself to solve the collision, that is Open Addressing.

In open addressing, the collision can be resolved by many methods;

  • Linear Probing
  • Quadratic Probing
  • Double hashing.

It might be Double Hashing or Quadratic Probing but the information is not enough to resolve.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.