Hتابع درهم سازی است که دارای M خانه است و در آن N عنصر ذخیره می شود برای رفع برخورد این جدول از روش زنجیر استفاده شده متوسط و بدترین زمان برای یک جستجوی یک عنصر؟
جواب: تتا N , تتا N/M
چرا؟؟؟
خیلی ساده هستش.
اگه مثلا فرض کنی در بدترین حالت همه عناصر به صورت زنجیر به فقط یک مدخل نگاشت بشن میشه یک جستجوی خطی که باید N عنصر را جستجو کند.
ولی اگه با یک تابع توزیع به صورت a=N/M به هر گره کسری از داده‌ها نگاشت بشن میشه حالت متوسطش که میشه همون N/M برای مثال اگه ۱۰ عنصر داشته باشیم و ۵ مدخل میشه ۱۰/۵ یعنی همون ۲ که یک حالت متوسطه
حالت خوبش هم اینه که N=M باشه که برای هر مدخل یک عنصر نگاشت میشه.
امیدوارم درست بوده باشه