- #1

- 160

- 3

## Main Question or Discussion Point

I came across "Data Structures and Algorithms with Object-Oriented Design Patterns in C++" by Bruno R. Preiss on the internet. I'm very confused with the theory on a Hashing method called the middle square method.

Link to the topic in the book

The author states that for a given key x, the Hash function is ##h(x) = \frac{M}{W}(x^2 \mod W)## where W=2

What I don't get is how is this hash function not supposed to return 0 for every key x? I tried it myself on a program and it didn't work! The reason stated in the book also doesn't make sense, that h(x) = 0 for the sets

## \{ x \in\mathbb Z : x< \sqrt{\frac{W}{M}} \} ##

and ## \{ x\in\mathbb Z^+ : x=n\sqrt{W}, n\in\mathbb Z^+ \} ##

WHY?!? Somebody please help. :)

Link to the topic in the book

The author states that for a given key x, the Hash function is ##h(x) = \frac{M}{W}(x^2 \mod W)## where W=2

^{w}where w=word size of the machine, and M is the hash table size. He goes on to say that this can be implemented by**bit shifting**the square of the key to the**right w-k times**, since W/M = 2^{w-k}, which gives us the middle bits of the square of the key. How is that?What I don't get is how is this hash function not supposed to return 0 for every key x? I tried it myself on a program and it didn't work! The reason stated in the book also doesn't make sense, that h(x) = 0 for the sets

## \{ x \in\mathbb Z : x< \sqrt{\frac{W}{M}} \} ##

and ## \{ x\in\mathbb Z^+ : x=n\sqrt{W}, n\in\mathbb Z^+ \} ##

WHY?!? Somebody please help. :)