حل تشریحی سوال شماره 38 دروس مشترک

وضعیت جدول درهم سازی $H\left[\mathrm{0..9}\right]$ بعد از درج هفت عدد $S_1,\dots ,S_7$ به‌صورت زیر است:

$H\left[\mathrm{0..9}\right]=\left[S_7,S_2,◯,S_4,S_2,S_5,◯,S_6,S_3\right]$

که $◯$ نشان‌دهنده خانه خالی است. برای درهم‌سازی از روش درهم‌سازی باز با وارسی خطی استفاده شده است. برای جستجوی عنصری که در جدول نیست حداکثر چند مقایسه باید انجام شود؟ (دقت کنید چک کردن آن‌که یک خانه خالی است خود به یک مقایسه نیاز دارد.)