کاوش خطی
برای تأییدپذیری کامل این مقاله به منابع بیشتری نیاز است. (ژوئن ۲۰۱۹) |
کاوش خطی یک طرح در برنامه‌نویسی کامپیوتری برای حل برخورد در جداول هش می‌باشد، این ساختار داده برای نگهداری مجموعه ای از جفتهای کلید-مقدار و دنبال کردن مقدار مربوط به یک کلید داده‌است. این روش در سال ۱۹۵۴ توسط جین امدال و ایلینا ام مک گرو و آرتور لی ساموئل اختراع شد؛ و اولین بار در سال ۱۹۶۳ توسط دونالد کنوث تجزیه و تحلیل شد. به همراه درهم سازی دوگانه و کاوش دوگانه کاوش خطی شکلی از آدرس دهی باز است. در این طرح‌ها، هر سلول از یک جدول هش یک جفت واحد کلید - مقدار را ذخیره می‌کند. هنگامی که تابع هش باعث ایجاد یک برخورد با نقشه‌برداری از یک کلید جدید به یک سلول از جدول هش که قبلاً توسط یکی دیگر اشغال شده‌است، کاوش خطی جدول را برای نزدیکترین مکان آزاد دنبال می‌کند و کلید جدید آن را وارد می‌کند. مراجعه به همان شیوه انجام می‌شود، با جستجو در جدول به ترتیب شروع در موقعیت ارائه شده توسط تابع هش، تا زمانی که یک سلول با یک کلید تطبیق پیدا کند یا یک سلول خالی پیدا شود ادامه پیدا می‌کند.
و همچنین کاوش خطی یکی از سریعترین استراتژی‌های درهم سازی می‌باشد که علت ان موارد زیر می‌باشد:
سربار حافظه پایین که ناشی از پیاده‌سازی آن می‌باشد که تنها به یک آرایه و تابع درهم ساز نیاز داریم.
مزیت از نظر موقعیت مکانی، زمانی که برخورد اتفاق می‌افتد تنها خانه‌های مجاور را جستجو می‌کنیم.
با ترکیب این دو عامل می‌توان به عملکرد بهتر حافظه نهان کمک کرد.[۱]
عملیات ویرایش
کاوش خطی یک جزء از برنامه‌های آدرس دهی باز برای استفاده از یک جدول درهم ساز برای حل مشکل فرهنگ لغت است. در مشکل فرهنگ لغت، داده ساختار باید بتواند یک مجموعه ای از کلید-مقدار را که عملیات اضافه و حذف را روی جفت موضوع‌ها هم کلید و هم مقدار حفظ کند و جستجو را برای مقدار مرتبط با یک کلید داده شده برقرار کند. در راه حل‌های آدرس دهی باز برای این مشکل، داده ساختار یک آرایه T (جدول درهم ساز) است که سلولهای [ T [ i (هنگام غیر خالی) هر یک از جفت کلید-مقدار را ذخیره می‌کنند. یک تابع درهم ساز برای نشان دادن هر کلید به سلول T استفاده می‌شود که این کلید باید ذخیره شود، به‌طور کلی کلیدهای کلاسیک را کپی می‌کند تا کلیدهایی با مقادیر مشابه در کنار یکدیگر در جدول قرار نداشته باشند. هنگامی که تابع درهم ساز یک کلید را به یک سلول که قبلاً توسط یک کلید دیگر اشغال شده‌است نگاشت می‌کند، یک برخورد هش به وجود می‌آید. کاوش خطی راه حلی برای حل این برخوردها می‌باشد.که با قرار دادن کلید جدید در نزدیکترین سلول خالی زیرین، این برخورد و تصادفات را حل می‌کند.[۲]
جستجو کردن ویرایش
برای جستجوی یک کلید داده شده x، سلولهای T مورد بررسی قرار می‌گیرند، با شروع از سلول در شاخص h (x) (که در آن h تابع هش است) و به سلولهای مجاور h(x) +1 h2(x)+2,... ، تا پیدا کردن یک سلول خالی یا یک سلول که کلید ذخیره آن x است. اگر یک سلول حاوی کلید یافت شود، نتیجه جستجو مقدار آن سلول را بازمی‌گرداند. در غیر این صورت، اگر یک سلول خالی پیدا شود، کلید را نمی‌توان در جدول قرار داد، زیرا در سلول قرار داده شده در اولویت هر سلول بعدی که هنوز جستجو نشده‌است قرار می‌گیرد. در این مورد، عملیات جستجو نتیجه می‌گیرد که کلید در فرهنگ لغت وجود ندارد.[۳][۴]
درج ویرایش
برای قرار دادن یک جفت کلید-مقدار (x, v) در جدول (احتمالاً جایگزین هر جفت موجود با همان کلید)، الگوریتم درج همان دنباله ای از سلول‌هایی است که برای جستجو دنبال می‌شوند تا زمانی که یک سلول خالی پیدا شود یا یک سلول که کلید ذخیره شده x است. سپس جفت کلید-مقدار جدید به آن سلول منتقل می‌شود.
اگر این درج باعث شود عامل بار جدول (کسری از سلولهای اشغال شده) به بالاتر از یک آستانه از پیش تعیین شده رشد کند، کل جدول ممکن است با یک جدول جدید جایگزین شود، که با یک عامل ثابت بزرگتر، با عملکرد جدید هش، همان‌طور که در یک آرایه پویا تنظیم این آستانه نزدیک به صفر و استفاده از یک نرخ رشد بالا برای اندازه جدول موجب عملیات سریعتر درهم سازی می‌شود، اما استفاده از حافظه بیشتر از مقدار آستانه نزدیک به یک و نرخ رشد پایین است. یک انتخاب رایج می‌تواند دو برابر کردن جدول باشد، وقتی که ضریب بار بیش از ۱/۲ باشد، ضریب بار را بین ۱/۴ و ۱/۲ قرار می‌دهد.[۳][۴]
حذف ویرایش
همچنین ممکن است یک جفت کلید-مقدار از فرهنگ لغت حذف شود. با این حال، به سادگی با تخلیه سلول آن کافی نمی‌باشد. این کار می‌تواند بر جستجوهایی برای کلیدهای دیگر که دارای مقدار درهم ساز نزدیکتر از سلول خالی است تأثیر بگذارد، اما در مکان بعدی سلول خالی ذخیره می‌شود. سلول خالی باعث می‌شود که این جستجوهای نادرست گزارش شوند که کلید موجود نیست.[۵]
در عوض، زمانی که سلول i خالی می‌شود، لازم است از طریق سلولهای پایینی جدول به جلو به دنبال پیدا کردن یا یک سلول خالی دیگر یا یک کلید است که می‌تواند به سلول i منتقل (یعنی یک کلید که مقدار هش آن برابر است یا زودتر از i)شود. هنگامی که یک سلول خالی پیدا می‌شود، سپس تخلیه سلول i بی خطر است و فرایند حذف منقضی می‌شود. اما، هنگامی که عمل جستجو یک کلید را پیدا می‌کند که می‌تواند به سلول i منتقل شود، این عمل را انجام می‌دهد. این باعث می‌شود تا جستجوهای بعدی برای کلید منتقل شده سریع تر شود، اما سلول دیگری نیز بعد از آن در همان بلوک سلولهای اشغال شده از بین می‌رود. جستجو برای یک کلید متحرک همچنان برای سلول خالی جدید ادامه می‌یابد، به همان شیوه، تا زمانی که آن را با رسیدن به یک سلول که قبلاً خالی بود، پایان می‌دهد. در این فرایند انتقال کلید به سلولهای پیشین، هر کلید تنها یک بار مورد بررسی قرار می‌گیرد؛ بنابراین، زمان کامل تمام فرایند، متناسب با طول بلوک سلولهای اشغال شده حاوی کلید حذف شده، متناسب با زمان اجرا سایر عملیات جدول هش است.
به جای آن، می‌توان از استراتژی حذف تنبل گونه استفاده کرد که در آن جفت ارزش، کلید-مقدار با جایگزینی ارزش با یک مقدار پرچم ویژه که نشان دهنده یک کلید حذف شده‌است حذف می‌شود. با این حال، این مقادیر پرچم به عامل بار در جدول درهم ساز کمک می‌کند. با استفاده از این روش ممکن است لازم باشد ارزشهای پرچم را از آرایه پاک کنیم و دوباره تمام جفتهای کلیدی باقیمانده را بارگذاری کنیم، که کسر زیادی از آرایه توسط کلیدهای حذف شده اشغال می‌شود.[۳][۴]
قطعه کد پیاده‌سازی جدول درهم ساز با استفاده از کاوش خطی[۶] ویرایش
class HashTable(object):
def __init__(self):
self.max_length = 8
self.max_load_factor = 0.75
self.length = 0
self.table = [None] * self.max_length
def __len__(self):
return self.length
def __setitem__(self, key, value):
self.length += 1
hashed_key = self._hash(key)
while self.table[hashed_key] is not None:
if self.table[hashed_key][0] == key:
self.length -= 1
break
hashed_key = self._increment_key(hashed_key)
tuple = (key, value)
self.table[hashed_key] = tuple
if self.length / float(self.max_length)>= self.max_load_factor:
self._resize()
def __getitem__(self, key):
index = self._find_item(key)
return self.table[index][1]
def __delitem__(self, key):
index = self._find_item(key)
self.table[index] = None
def _hash(self, key):
# TODO more robust
return hash(key) % self.max_length
def _increment_key(self, key):
return (key + 1) % self.max_length
def _find_item(self, key):
hashed_key = self._hash(key)
if self.table[hashed_key] is None:
raise KeyError
if self.table[hashed_key][0] != key:
original_key = hashed_key
while self.table[hashed_key][0] != key:
hashed_key = self._increment_key(hashed_key)
if self.table[hashed_key] is None:
raise KeyError
if hashed_key == original_key:
raise KeyError
return hashed_key
def _resize(self):
self.max_length *= 2
self.length = 0
old_table = self.table
self.table = [None] * self.max_length
for tuple in old_table:
if tuple is not None:
self[tuple[0]] = tuple[1]
جستارهای وابسته ویرایش
منابع ویرایش
- ↑ "linear probing" (PDF) (به انگلیسی).
- ↑ Navrat, Pavol (2004-06-01). "Review of "Algorithm design". ACM SIGACT News. 35 (2): 14. doi:10.1145/992287.992293. ISSN 0163-5700.
- ↑ ۳٫۰ ۳٫۱ ۳٫۲ «: LinearHashTable: Linear Probing». بایگانی‌شده از اصلی در 19 اكتبر 2017. دریافت‌شده در 10 ژوئن 2019. تاریخ وارد شده در
|archivedate=را بررسی کنید (کمک) - ↑ ۴٫۰ ۴٫۱ ۴٫۲ Li, J.; Lillis, J.; Cheng, C. -K. "Linear decomposition algorithm for VLSI design applications". Proceedings of IEEE International Conference on Computer Aided Design (ICCAD). IEEE Comput. Soc. Press. doi:10.1109/iccad.1995.480016. ISBN 0-8186-7213-7.
- ↑ Sedgewick Robert -Wayne Kevin. «algorithms».
- ↑ https://gist.github.com/scwood. «code».
- قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها
- مشارکت‌کنندگان ویکی‌پدیا. «Hash table». در دانشنامهٔ ویکی‌پدیای انگلیسی
- مشارکت‌کنندگان ویکی‌پدیا. «Hash key». در دانشنامهٔ ویکی‌پدیای انگلیسی
- مشارکت‌کنندگان ویکی‌پدیا. «Hash». در دانشنامهٔ ویکی‌پدیای انگلیسی