موضوع مقاله: آدرس‌دهی باز | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آدرس‌دهی باز | مقدمه: در این روش با بررسی، یا جستجوی متناوب در میان خانه‌های آرایه تا زمانی که هدف یا یک خانه خالی بیابیم ادامه می‌یابد، رسیدن به خانهٔ خالی در جستجو برای یک کلید به معنای نبود این کلید در جدول می‌باشد. | ## بخش 1: آدرس‌دهی باز | روش‌های شناخته شده برای ترتیب بررسی شامل موارد زیر است: بررسی خطی روشی که در آن ترتیب بررسی ثابت و معمولاً با قدم‌های به اندازه ۱ می‌باشد. اگر بخواهیم تابعی برای آن در نظر بگیریم به شکلی که i نشانگر تعداد دفعات حرکت جستجوگر برای یافتن کلید باشد و (H1(k یک تابع درهم‌ساز باشد و m نشانگر تعداد خانه‌های جدول باشد، درهم‌ساز H را می‌توان به شکل زیر در نظر گرفت : H(k,i)=(H1(k)+i) mod m بررسی درجه دوم روشی که در آن ترتیب بررسی تابعی از درجه دوم می‌باشد، اگر H1(k) , m , i را مانند بررسی خطی تعریف کنیم و a , b دو عدد دلخواه باشند برای بررسی درجه دوم تابعی مانند تابع زیر خواهیم داشت : H(k,i)=(H1(k)+ai2+bi) mod m درهم‌سازی مضاعف حالتی که توالی جستجو برای هر کلید ثابت است اما به وسیله یک درهم‌ساز دیگر محاسبه می‌شود. , اگر H1(k) , m , i را مانند بررسی خطی تعریف کنیم و (h2(k نیز یک تابع درهم‌ساز باشد برای درهم‌سازی مضاعف تابعی مانند تابع زیر خواهیم داشت : H(k,i)=(H1(k)+iH2(k mod m در بررسی بین این سه روش، بررسی خطی بهترین عملکرد کش را دارد ولی وقوع تصادم در آن معمول‌تر است، درحالی که درهم‌سازی مضاعف عملکرد کش ضعیفی دارد ولی به‌طور تقریبی هیچ تصادمی در آن اتفاق نمی‌افتد و بررسی درجه دوم در ناحیه‌ای بین این دو حالت قرار می‌گیرد. در تعدادی دیگر از روش‌های آدرس‌دهی باز، فرایند کلیدهای موجود در جدول را جابه‌جا کرده و یک خانهٔ خالی برای کلید جدید ایجاد می‌کنند. این روش‌ها حداکثر زمان جستجوی کمتری نسبت به روش‌های بر مبنای بررسی (مانند روش‌های بالا) ارائه می‌دهند. یک عامل بحرانی در مورد درهم‌سازی‌های با آدرس‌دهی باز ضریب بار (یا عامل بار) است. | ## بخش 2: آدرس‌دهی باز | باید توجه داشت که منظور از ضریب بار، نسبت تعداد خانه‌های پر جدول به تعداد کل خانه‌های جدول می‌باشد. هنگامی که ضریب بار افزایش می‌یابد و به ۱۰۰٪ نزدیک می‌شود، تعداد بررسی‌های مورد نیاز برای پیدا کردن یا درج یک کلید به شکل چشمگیری افزایش می‌یابد. هنگامی که جدول کاملاً پر می‌شود، ممکن است الگوریتم‌های بررسی نتوانند درست کار کنند. یک درهم‌ساز ضعیف حتی در حالی که بسیاری از جدول خالی است در نتیجه ضریب بار پایین است با تولید تعداد قابل توجهی تصادم کارایی بسیار پایینی نشان می‌دهد. بررسی ضریب بار در آدرس‌دهی باز در آدرس‌دهی باز با توجه به اینکه حداکثر به اندازهٔ تعداد خانه‌های جدول عنصر وجود دارد ضریب بار که معمولاً به اختصار آن را با نشان می‌دهند همواره از ۱ کوچکتر است. همچنین می‌توان ثابت کرد در یک درهم‌سازی یکنواخت با آدرس‌دهی باز تعداد مورد انتظار جستجوی ناموفق برابر با می‌باشد، در حالی که برای جستجوی موفق برابر با است. | ## بخش 3: آدرس‌دهی باز | شبه‌کد شبه‌کد زیر یک پیاده‌سازی مربوط به یک درهم‌سازی با آدرس‌دهی باز و بررسی خطی با قدم‌های به اندازه یک می‌باشد. یافتن_خانه، خانه‌ای را که شامل کلید داده‌شده یا خانه‌ای که در صورت موجود بودن، این کلید در آن قرار می‌گرفت را پیدا می‌کند. به‌طور معمول اندازه آرایه دارای رشد نمایی می‌باشد، به‌طور مثال اندازه جدید را دو برابر اندازه آرایه قبلی در نظر می‌گیریم. هرچند این روش سرانجام نیازمند دوباره ساختن جدول فقط برای پاک کردن داده‌های پاک شده می‌باشد (توجه شود منظور زمانی است که بخواهیم هیچ خانه‌ای علامت گذاری نشده باشد). این روش انجام بروز رسانی و حذف در پیچیدگی زمانی (O(1 برای داده‌های موجود را ممکن می‌کند، با دوباره ساختن گاه‌به‌گاه جدول در صورتی که تعداد خانه‌های علامت گذاری زیاد باشد. روش حذف گفته شده در پیچیدگی زمانی (O(1 فقط در بررسی خطی با قدم‌های واحد ممکن است. | ## جمع‌بندی | در حالتی که بخواهیم تعداد زیادی داده را به صورت هم‌زمان حذف کنیم، علامت گذاری خانه‌ها برای حذف شدن و دوباره ساختن جدول می‌تواند کاراتر باشد.