با بزرگ شدن LF باید slotهای بیشتری به hash tableمون اضافه کنیم که بهش میگن resizing. منطقیه که سایز آرایه رو دو برابر کنیم. بعدش تمام آیتم‌های موجود رو با hash function دوباره توی hash table جدید وارد می‌کنیم. هرچی LF کمتر، تعداد collisionها هم کمتر. قانون کلیش هم اینه که وقتی LF بزرگتر از 0.7 شد resize کنیم. resizing هم هزینه‌بره؛ اما اغلب اوقات لازم نمیشه که resize کنیم و بطور متوسط resizing هم پیچیدگی O(1) داره.
یه hash function خوب هم مقادیر رو بطور مساوی داخل آرایه توزیع می‌کنه.
(2/2)
#Grokking_Algorithms #algorithm
@techstuff100
Post #344
685
Tech Stuff پرفورمنس hash table پرفورمنس hash tableها بطور متوسط (average case) پیچیدگی زمانی O(1) داره. هم توی سرچ، هم insert و هم حذف. اما توی worst case به O(n) می‌رسه که اصلا چیز خوبی نیست. یعنی توی بدترین حالت مثل آرایه‌ست توی insert و delete و مثل linked list توی…
- ❤ 5