一个哈希表,使用链地址法解决冲突,现有键值分别为 12, 25, 37, 49, 60, 73,假设哈希函数为 H(key) = key % 10。若该哈希表包含10个桶(索引从0到9),则哈希表中第3个桶(索引为2的桶)的链表包含的键值数量是多少?
答案解析
核心考点说明:本题考察哈希表的链地址法解决冲突,重点是计算哈希值并根据结果确定键值在哈希表中的位置。难点在于需要对所有键值进行哈希计算并统计特定桶中的元素个数。
解题思路分析:首先对每个键值计算其哈希值,然后根据哈希值确定键值应该存储在哪个桶中。根据哈希函数 H(key) = key % 10,可以得出以下哈希值:
12 % 10 = 2
25 % 10 = 5
37 % 10 = 7
49 % 10 = 9
60 % 10 = 0
73 % 10 = 3
然后统计哈希值为2的键值个数。哈希值为2的只有12,所以第三个桶的链表只包含一个元素。
选项分析:
A. 错误。经过哈希计算,键值12存储在第3个桶中。
B. 正确。只有一个键值12的哈希值是2,应该被插入到第3个桶的链表中。
C. 错误。没有其他键值被散列到第3个桶。
D. 错误。没有其他键值被散列到第3个桶。
易错点提醒:容易将桶的索引与哈希值混淆。必须明确每个键值通过哈希函数计算得出哈希值,哈希值决定了键值应该放入哪个桶。
正确答案的关键依据:根据给定的哈希函数计算每个键值的哈希值,统计哈希值为2的键值的个数。
正确答案:B