IPA FE Subject A 2024 Question 2
A question IPA Japan published in 令和６年度 基本情報技術者試験 科目A 公開問題 問2, translated into English. ITPEC is based on the same exams.
Data whose key is one lowercase letter of the alphabet (any of a, b, …, z) is stored in a hash table of size 10. As the hash function, the digit in the ones place of the ASCII code of the letter expressed in decimal notation is used. Which of the following is the combination of keys that causes a collision? In ASCII code, consecutive binary numbers in ascending order are assigned as codes in alphabetical order.
Explanation
d and x — both have ASCII codes ending in 0 (100 and 120), so they hash to the same slot.
In ASCII the lowercase letters run consecutively from a = 97 (hexadecimal 61), so a letter’s code is 97 plus its position counted from 0. The hash value is the last decimal digit of that code.
Two keys collide when their codes differ by a multiple of 10, that is, when the letters are 10 or 20 places apart: d and x are 20 apart.
Answer (d)
Why not others:
- •(a) — a and i are 8 places apart, giving 7 and 5
- •(b) — b and r are 16 places apart, giving 8 and 4
- •(c) — c and l are 9 places apart, giving 9 and 8
Key rule: With a hash of “code mod m”, two keys collide exactly when their codes differ by a multiple of m; for consecutive codes, that is a gap of m, 2m, … places.
Algorithm and Programming · AI-written, may contain errors
This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.