کاوش خطی یک طرح در برنامه نویسی کامپیوتری برای حل برخورد در جداول هش می باشد، این ساختار داده برای نگهداری مجموعه ای از جفت های کلید - مقدار و دنبال کردن مقدار مربوط به یک کلید داده است. این روش در سال ۱۹۵۴ توسط جین امدال و ایلینا ام مک گرو و آرتور لی ساموئل اختراع شد؛ و اولین بار در سال ۱۹۶۳ توسط دونالد کنوث تجزیه و تحلیل شد. به همراه درهم سازی دوگانه و کاوش دوگانه کاوش خطی شکلی از آدرس دهی باز است. در این طرح ها، هر سلول از یک جدول هش یک جفت واحد کلید - مقدار را ذخیره می کند. هنگامی که تابع هش باعث ایجاد یک برخورد با نقشه برداری از یک کلید جدید به یک سلول از جدول هش که قبلاً توسط یکی دیگر اشغال شده است، کاوش خطی جدول را برای نزدیکترین مکان آزاد دنبال می کند و کلید جدید آن را وارد می کند. مراجعه به همان شیوه انجام می شود، با جستجو در جدول به ترتیب شروع در موقعیت ارائه شده توسط تابع هش، تا زمانی که یک سلول با یک کلید تطبیق پیدا کند یا یک سلول خالی پیدا شود ادامه پیدا می کند.
و همچنین کاوش خطی یکی از سریعترین استراتژی های درهم سازی می باشد که علت ان موارد زیر می باشد:
سربار حافظه پایین که ناشی از پیاده سازی آن می باشد که تنها به یک آرایه و تابع درهم ساز نیاز داریم.
مزیت از نظر موقعیت مکانی، زمانی که برخورد اتفاق می افتد تنها خانه های مجاور را جستجو می کنیم.
با ترکیب این دو عامل می توان به عملکرد بهتر حافظه نهان کمک کرد. [ ۱]
کاوش خطی یک جزء از برنامه های آدرس دهی باز برای استفاده از یک جدول درهم ساز برای حل مشکل فرهنگ لغت است. در مشکل فرهنگ لغت، داده ساختار باید بتواند یک مجموعه ای از کلید - مقدار را که عملیات اضافه و حذف را روی جفت موضوع ها هم کلید و هم مقدار حفظ کند و جستجو را برای مقدار مرتبط با یک کلید داده شده برقرار کند. در راه حل های آدرس دهی باز برای این مشکل، داده ساختار یک آرایه T ( جدول درهم ساز ) است که سلول های [ T [ i ( هنگام غیر خالی ) هر یک از جفت کلید - مقدار را ذخیره می کنند. یک تابع درهم ساز برای نشان دادن هر کلید به سلول T استفاده می شود که این کلید باید ذخیره شود، به طور کلی کلیدهای کلاسیک را کپی می کند تا کلیدهایی با مقادیر مشابه در کنار یکدیگر در جدول قرار نداشته باشند. هنگامی که تابع درهم ساز یک کلید را به یک سلول که قبلاً توسط یک کلید دیگر اشغال شده است نگاشت می کند، یک برخورد هش به وجود می آید. کاوش خطی راه حلی برای حل این برخوردها می باشد. که با قرار دادن کلید جدید در نزدیک ترین سلول خالی زیرین، این برخورد و تصادفات را حل می کند. [ ۲]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفو همچنین کاوش خطی یکی از سریعترین استراتژی های درهم سازی می باشد که علت ان موارد زیر می باشد:
سربار حافظه پایین که ناشی از پیاده سازی آن می باشد که تنها به یک آرایه و تابع درهم ساز نیاز داریم.
مزیت از نظر موقعیت مکانی، زمانی که برخورد اتفاق می افتد تنها خانه های مجاور را جستجو می کنیم.
با ترکیب این دو عامل می توان به عملکرد بهتر حافظه نهان کمک کرد. [ ۱]
کاوش خطی یک جزء از برنامه های آدرس دهی باز برای استفاده از یک جدول درهم ساز برای حل مشکل فرهنگ لغت است. در مشکل فرهنگ لغت، داده ساختار باید بتواند یک مجموعه ای از کلید - مقدار را که عملیات اضافه و حذف را روی جفت موضوع ها هم کلید و هم مقدار حفظ کند و جستجو را برای مقدار مرتبط با یک کلید داده شده برقرار کند. در راه حل های آدرس دهی باز برای این مشکل، داده ساختار یک آرایه T ( جدول درهم ساز ) است که سلول های [ T [ i ( هنگام غیر خالی ) هر یک از جفت کلید - مقدار را ذخیره می کنند. یک تابع درهم ساز برای نشان دادن هر کلید به سلول T استفاده می شود که این کلید باید ذخیره شود، به طور کلی کلیدهای کلاسیک را کپی می کند تا کلیدهایی با مقادیر مشابه در کنار یکدیگر در جدول قرار نداشته باشند. هنگامی که تابع درهم ساز یک کلید را به یک سلول که قبلاً توسط یک کلید دیگر اشغال شده است نگاشت می کند، یک برخورد هش به وجود می آید. کاوش خطی راه حلی برای حل این برخوردها می باشد. که با قرار دادن کلید جدید در نزدیک ترین سلول خالی زیرین، این برخورد و تصادفات را حل می کند. [ ۲]
wiki: کاوش خطی