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.(adsbygoogle = window.adsbygoogle || []).push({});

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 bybit shiftingthe square of the key to theright 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. :)

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Question about a Hash Function

Loading...

Similar Threads - Question Hash Function | Date |
---|---|

Big-O Notation Question | Feb 20, 2018 |

C/++/# Question about input format file (for creating a net) | Dec 13, 2017 |

Latex article template question | Dec 2, 2017 |

C/++/# Question about a specific class method in C++ | Nov 7, 2017 |

C/++/# Why isn't my hash set doing a good job? | Apr 8, 2016 |

**Physics Forums - The Fusion of Science and Community**