1998年中国科学院软件研究所 · 哈希表 · 考研题

假定有K个关键字互为同义词,若用线性探测法把这K个关键字存入散列表中,至少要进行【 】次探测。

A、K-1次

B、K次

C、K+1次

D、K(K+1)/2次

分析

因为K个关键字互为同义词,只有在存入第一个关键字的情况下不发生冲突,所以至少需要进行1+2+...+K=K(K+1)/2次探测。

笔记