جدول هش
Hash TableHash Table با استفاده از تابع Hash، یک key را به محل ذخیره‌سازی یا bucket تبدیل می‌کند و هدفش lookup، insertion و deletion بسیار سریع در حالت متوسط است.
اول این مفهوم را در ذهن نگه دار
Hash Table با استفاده از تابع Hash، یک key را به محل ذخیره‌سازی یا bucket تبدیل می‌کند و هدفش lookup، insertion و deletion بسیار سریع در حالت متوسط است.
چطور کار می‌کند؟ ساده و مرحله‌ای
تابع Hash کلید را به یک مقدار قابل استفاده برای پیدا کردن bucket تبدیل می‌کند.
دو key مختلف ممکن است به یک bucket برسند؛ پس باید collision را مثلاً با chaining یا open addressing مدیریت کنیم.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
کلید را hash کن.
Hash را به bucket نگاشت کن.
collision را حل کن و در نهایت خود key را مقایسه کن.
مثلاً userId hash می‌شود تا bucket پیدا شود و سپس entry واقعی کاربر در همان bucket بررسی می‌شود.
class HashTable {
constructor(size = 16) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let h = 0;
for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
return h % this.buckets.length;
}
}syntax را حفظ نکن. stateای را که در هر خط تغییر می‌کند دنبال کن و آن را به invariant توضیح‌داده‌شده در بالا وصل کن.
avg O(1), worst O(n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- O(1) متوسط را با O(1) تضمین‌شده اشتباه نکن.
- collision و مقایسه واقعی keyها را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
در جواب حرفه‌ای علاوه بر O(1) متوسط، collision، load factor و resize شدن جدول را توضیح بده؛ این‌ها Hash Table را از یک تعریف سطحی key-value جدا می‌کنند.
جدول هش چه مسئله‌ای را حل می‌کند؟
Hash Table با استفاده از تابع Hash، یک key را به محل ذخیره‌سازی یا bucket تبدیل می‌کند و هدفش lookup، insertion و deletion بسیار سریع در حالت متوسط است.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا avg O(1), worst O(n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
O(1) متوسط را با O(1) تضمین‌شده اشتباه نکن.