Hash Tables and Near-Constant Lookup · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.
به انگلیسی

Hash the key, then check for a match

Computing · Algorithms & Data Structures · ages 16-18
Name ______________________   Date ____________

  1. Use A = 1 through Z = 26. Add the letter values, then take the remainder after division by 5. What is the home slot for key CF in slots 0 through 4?

    • slot 1
    • slot 3
    • slot 4

  2. After hashing a key and taking the remainder for the table size, what have you calculated?

    • The key's home slot for starting lookup
    • The key's final place in alphabetical order
    • The slot that must hold the key despite any collisions

  3. With the hash rule and table size unchanged, the same key has the same home slot every time.

    Circle one:   True   False

  4. A five-slot table uses linear probing and has no deletions. A new key's home slot 4 holds a different key, but slot 0 is empty. What happens on insertion?

    • Remove the existing pair from slot 4 and store the new pair there.
    • Reject the new pair because the table has no slot numbered 5.
    • Wrap from slot 4 to slot 0 and insert the new pair there.

  5. Under chaining, distinct keys 19 and 29 both have home slot 9. Key 19 is already in its bucket. Where is the pair for key 29 stored?

    • In place of key 19, with that earlier pair removed
    • In the same bucket's linked list alongside key 19
    • In a separate table containing only the later key

  6. Five keys use ten slots under chaining. One bucket holds two keys; three other buckets hold one each. For a present key, what is the maximum number of key comparisons lookup needs within its bucket?

    • Five comparisons in the chosen bucket
    • Two comparisons in the chosen bucket
    • Ten comparisons in the chosen bucket

  7. In a seven-slot table using linear probing, K and R have home slot 4. K occupies 4 and R occupies 5. A lookup for R checks only 4 and reports it missing. What should it do?

    • Stop after checking slot 4 because every pair remains in its home slot.
    • Skip slot 4 and compare only keys in slots numbered above slot 5.
    • Compare at slot 4, then probe forward and compare at slot 5.

  8. A ten-slot table holds nine keys. Five share one chained bucket, where lookup is slow. Which conclusion is supported?

    • The long bucket adds checks; crowding and poor spreading can both matter.
    • Nine stored keys prove that every bucket contains the same number of keys.
    • The long bucket proves that no lookup anywhere in this table can be quick.
LightMySky · lightmysky.comW1-mt_7v94MJEdmJ-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Hash the key, then check for a match W1-mt_7v94MJEdmJ-s1

  1. slot 4 · C is 3 and F is 6, giving 9. Dividing 9 by 5 leaves remainder 4, so use home slot 4.
  2. The key's home slot for starting lookup · The result is a home slot. The collision rule determines which entries must then be checked.
  3. True · The unchanged hash rule produces the same number, and dividing by the same size produces the same remainder.
  4. Wrap from slot 4 to slot 0 and insert the new pair there. · The next slot after 4 wraps to 0. Since 0 is empty, it accepts the new pair.
  5. In the same bucket's linked list alongside key 19 · Chaining keeps distinct colliding keys in the same bucket. It does not replace one with the other.
  6. Two comparisons in the chosen bucket · The largest bucket contains two keys. Lookup checks only the chosen bucket, so at most two key comparisons are needed.
  7. Compare at slot 4, then probe forward and compare at slot 5. · The collision displaced R to slot 5. Lookup must follow the same probing route used to store it.
  8. The long bucket adds checks; crowding and poor spreading can both matter. · A five-key bucket can need several comparisons. The total occupancy alone does not explain why those keys share a slot.
Worksheet · LightMySky