پرفورمنس hash table

پرفورمنس hash tableها بطور متوسط (average case) پیچیدگی زمانی O(1) داره. هم توی سرچ، هم insert و هم حذف. اما توی worst case به O(n) می‌رسه که اصلا چیز خوبی نیست. یعنی توی بدترین حالت مثل آرایه‌ست توی insert و delete و مثل linked list توی سرچ. برای اینکه به worst case نخوریم باید از collisionها جلوگیری کنیم و برای این کار به load factor (LF) و hash function خوب نیاز داریم.

برای ذخیره آیتم‌های hash table از آرایه استفاده می‌کنیم. LF اینطور محاسبه میشه: تعداد آیتم‌های ذخیره شده در hash table تقسیم بر تعداد کل slotها. برای مثال اگه آرایه‌مون ۵ تا slot داشته باشه و ۲ تا آیتم ذخیره کرده باشه، LFمون میشه 0.4.

(1/2)

#Grokking_Algorithms #algorithm


@techstuff100