Chapter 4.5, Problem 3E

A parking lot has 31 visitor space, numbered from 0 to 30. Visitors are assigned parking spaces using the hashing function $h\left(k\right)=k\text{ mod 31}$ , where k is the number formed from the first three digits on a visitor’s license plate.

a) Which spaces are assigned by the hashing function to cars that have these first three digits on their license plates: 317,918,007,100,111,310?

b) Describe a procedure visitors should follow to find a free parking space, when the space they are assigned is occupied.

Another way to resolve collisions in hashing is to use double hashing. We use an initial hashing function $h\left(k\right)=k\text{ mod }p$ , where p is prime. We also use a second hashing function $g\left(k\right)=(k+1)\text{ mod }(p-2)$ . When a collision occurs, we use a probing sequence $h(k,1)=(h(k)+i\cdot g(k))\mathrm{mod}p$ .