موضوع مقاله: کاوش خطی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کاوش خطی | مقدمه: کاوش خطی یک طرح در برنامه‌نویسی کامپیوتری برای حل برخورد در جداول هش می‌باشد، این ساختار داده برای نگهداری مجموعه ای از جفت‌های کلید-مقدار و دنبال کردن مقدار مربوط به یک کلید داده‌است. | ## بخش 1: کاوش خطی | این روش در سال ۱۹۵۴ توسط جین امدال و ایلینا ام مک گرو و آرتور لی ساموئل اختراع شد؛ و اولین بار در سال ۱۹۶۳ توسط دونالد کنوث تجزیه و تحلیل شد. هنگامی که تابع هش باعث ایجاد یک برخورد با نقشه‌برداری از یک کلید جدید به یک سلول از جدول هش که قبلاً توسط یکی دیگر اشغال شده‌است، کاوش خطی جدول را برای نزدیکترین مکان آزاد دنبال می‌کند و کلید جدید آن را وارد می‌کند. مراجعه به همان شیوه انجام می‌شود، با جستجو در جدول به ترتیب شروع در موقعیت ارائه شده توسط تابع هش، تا زمانی که یک سلول با یک کلید تطبیق پیدا کند یا یک سلول خالی پیدا شود ادامه پیدا می‌کند. و همچنین کاوش خطی یکی از سریعترین استراتژی‌های درهم سازی می‌باشد که علت ان موارد زیر می‌باشد: سربار حافظه پایین که ناشی از پیاده‌سازی آن می‌باشد که تنها به یک آرایه و تابع درهم ساز نیاز داریم. مزیت از نظر موقعیت مکانی، زمانی که برخورد اتفاق می‌افتد تنها خانه‌های مجاور را جستجو می‌کنیم. کاوش خطی یک جزء از برنامه‌های آدرس دهی باز برای استفاده از یک جدول درهم ساز برای حل مشکل فرهنگ لغت است. در مشکل فرهنگ لغت، داده ساختار باید بتواند یک مجموعه ای از کلید-مقدار را که عملیات اضافه و حذف را روی جفت موضوع‌ها هم کلید و هم مقدار حفظ کند و جستجو را برای مقدار مرتبط با یک کلید داده شده برقرار کند. در راه حل‌های آدرس دهی باز برای این مشکل، داده ساختار یک آرایه T (جدول درهم ساز) است که سلول‌های [ T [ i (هنگام غیر خالی) هر یک از جفت کلید-مقدار را ذخیره می‌کنند. | ## بخش 2: کاوش خطی | یک تابع درهم ساز برای نشان دادن هر کلید به سلول T استفاده می‌شود که این کلید باید ذخیره شود، به‌طور کلی کلیدهای کلاسیک را کپی می‌کند تا کلیدهایی با مقادیر مشابه در کنار یکدیگر در جدول قرار نداشته باشند. هنگامی که تابع درهم ساز یک کلید را به یک سلول که قبلاً توسط یک کلید دیگر اشغال شده‌است نگاشت می‌کند، یک برخورد هش به‌ وجود می‌آید. کاوش خطی راه حلی برای حل این برخوردها می‌باشد.که با قرار دادن کلید جدید در نزدیک‌ترین سلول خالی زیرین، این برخورد و تصادفات را حل می‌کند. جستجو کردن برای جستجوی یک کلید داده شده x، سلول‌های T مورد بررسی قرار می‌گیرند، با شروع از سلول در شاخص h (x) (که در آن h تابع هش است) و به سلول‌های مجاور h(x) +1 h2(x)+2,... در غیر این صورت، اگر یک سلول خالی پیدا شود، کلید را نمی‌توان در جدول قرار داد، زیرا در سلول قرار داده شده در اولویت هر سلول بعدی که هنوز جستجو نشده‌است قرار می‌گیرد. درج برای قرار دادن یک جفت کلید-مقدار (x, v) در جدول (احتمالاً جایگزین هر جفت موجود با همان کلید)، الگوریتم درج همان دنباله ای از سلول‌هایی است که برای جستجو دنبال می‌شوند تا زمانی که یک سلول خالی پیدا شود یا یک سلول که کلید ذخیره شده x است. اگر این درج باعث شود عامل بار جدول (کسری از سلول‌های اشغال شده) به بالاتر از یک آستانه از پیش تعیین شده رشد کند، کل جدول ممکن است با یک جدول جدید جایگزین شود، که با یک عامل ثابت بزرگتر، با عملکرد جدید هش، همان‌طور که در یک آرایه پویا تنظیم این آستانه نزدیک به صفر و استفاده از یک نرخ رشد بالا برای اندازه جدول موجب عملیات سریعتر درهم سازی می‌شود، اما استفاده از حافظه بیشتر از مقدار آستانه نزدیک به یک و نرخ رشد پایین است. یک انتخاب رایج می‌تواند دو برابر کردن جدول باشد، وقتی که ضریب بار بیش از ۱/۲ باشد، ضریب بار را بین ۱/۴ و ۱/۲ قرار می‌دهد. | ## بخش 3: کاوش خطی | این کار می‌تواند بر جستجوهایی برای کلیدهای دیگر که دارای مقدار درهم ساز نزدیکتر از سلول خالی است تأثیر بگذارد، اما در مکان بعدی سلول خالی ذخیره می‌شود. در عوض، زمانی که سلول i خالی می‌شود، لازم است از طریق سلول‌های پایینی جدول به جلو به دنبال پیدا کردن یا یک سلول خالی دیگر یا یک کلید است که می‌تواند به سلول i منتقل (یعنی یک کلید که مقدار هش آن برابر است یا زودتر از i)شود. هنگامی که یک سلول خالی پیدا می‌شود، سپس تخلیه سلول i بی خطر است و فرایند حذف منقضی می‌شود. اما، هنگامی که عمل جستجو یک کلید را پیدا می‌کند که می‌تواند به سلول i منتقل شود، این عمل را انجام می‌دهد. این باعث می‌شود تا جستجوهای بعدی برای کلید منتقل شده سریع تر شود، اما سلول دیگری نیز بعد از آن در همان بلوک سلول‌های اشغال شده از بین می‌رود. جستجو برای یک کلید متحرک همچنان برای سلول خالی جدید ادامه می‌یابد، به همان شیوه، تا زمانی که آن را با رسیدن به یک سلول که قبلاً خالی بود، پایان می‌دهد. در این فرایند انتقال کلید به سلول‌های پیشین، هر کلید تنها یک بار مورد بررسی قرار می‌گیرد؛ بنابراین، زمان کامل تمام فرایند، متناسب با طول بلوک سلولهای اشغال شده حاوی کلید حذف شده، متناسب با زمان اجرا سایر عملیات جدول هش است. به جای آن، می‌توان از استراتژی حذف تنبل گونه استفاده کرد که در آن جفت ارزش، کلید-مقدار با جایگزینی ارزش با یک مقدار پرچم ویژه که نشان دهنده یک کلید حذف شده‌است حذف می‌شود. | ## جمع‌بندی | با استفاده از این روش ممکن است لازم باشد ارزشهای پرچم را از آرایه پاک کنیم و دوباره تمام جفتهای کلیدی باقیمانده را بارگذاری کنیم، که کسر زیادی از آرایه توسط کلیدهای حذف شده اشغال می‌شود.