آدرس‌دهی باز

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
تداخل درهم‌ سازی‌ حل شده با بررسی خطی (انداره قدم=1)

آدرس‌دهی باز, یا درهم‌سازی بسته روشی برای حل تصادم در جدول درهم‌ساری است.در این روش با بررسی، یا جستجوی متناوب در میان خانه‌های آرایه تا زمانی که هدف و یا یک خانه خالی بیابیم ادامه می‌یابد, رسیدن به خانه‌ی خالی در جستجو برای یک کلید به معنای نبود این کلید در جدول می‌باشد. روش‌های شناخته شده برای ترتیب بررسی شامل موارد زیر است:

بررسی خطی

روشی که در آن ترتیب بررسی ثابت و معمولاً با قدم‌های به اندازه 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

در بررسی بین این سه روش ، بررسی خطی بهترین عملکرد کش را دارد ولی وقوع تصادم در آن معمول‌تر است, درحالی که درهم‌سازی مضاعف عملکرد کش ضعیفی دارد ولی به طور تقریبی هیچ تصادمی در آن اتفاق نمی‌افتد و بررسی درجه دوم در ناحیه‌ای بین این دو حالت قرار میگیرد.همچنین درهم‌سازی مضاعف به محاسبه بیشتری نسبت به روش‌های دیگر نیاز دارد.

در تعدادی دیگر از روش‌های آدرس‌دهی باز , فرایند کلید‌های موجود در جدول را جابه‌جا کرده و یک خانه‌ی خالی برای کلید جدید ایجاد می‌کنند. این روش‌ها حداکثر زمان جستجوی کمتری نسبت به روش‌های بر مبنای بررسی ( مانند روش‌های بالا) ارائه میدهند.

یک عامل بحرانی در مورد درهم‌سازی‌های با آدرس‌دهی باز ضریب بار(یا عامل بار) است. باید توجه داشت که منظور از ضریب‌‌ بار ، نسبت تعداد خانه‌های پر جدول به تعداد کل خانه‌های جدول می‌باشد .هنگامی که ضریب بار افزایش می‌یابد و به 100% نزدیک می‌شود, تعداد بررسی‌های مورد نیاز برای پیدا کردن و یا درج یک کلید به شکل چشمگیری افزایش می‌یابد . هنگامی که جدول کاملا پر می‌شود , ممکن است الگوربتم‌های بررسی نتوانند درست کار کنند . حتی با یک تابع درهم‌ساری خوب , معمولا ضریب بار به 80% محدود می‌شود . یک درهم‌ساز ضعیف حتی در حالی که بسیاری از جدول خالی است در نتیجه ضریب بار پایین است با تولید تعداد قابل توجهی تصادم کارایی بسیار پایینی نشان می‌دهد.[درحال ویرایش]

بررسی ضریب بار در آدرس‌دهی باز[ویرایش]

در آدرس‌دهی باز با توجه به اینکه حداکثر به اندازه‌ی تعداد خانه‌های جدول عنصر وجود دارد ضریب بار که معمولا به اختصار آن را با \alpha نشان می‌دهند همواره از 1 کوچکتر است. همچنین می‌توان ثابت کرد در یک درهم‌سازی یکنواخت با ‌آدرس‌دهی باز تعداد مورد انتظار جستجوی ناموفق برابر با \tfrac{1}{1- \alpha} می‌باشد, در حالی که برای جستجوی موفق برابر با \tfrac{1}{\alpha}ln\tfrac{1}{1- \alpha} است .

شبه‌کد[ویرایش]

شبه‌کد زیر یک پیاده‌ساری مربوط به یک درهم‌ساری با آدرس‌دهی باز و بررسی خطی با قدم‌های به اندازه یک می‌باشد.یک رویکرد مشترک که در توابع در هم‌ساز خوب موثر واقع می‌شود این‌ است که هر بک از توابع جستجو(lookup), قراردادن(set)و حذف(remove) از یک تابع به اسم یافتن_خانه(find_slot)استفاده کنند . یافتن_خانه، خانه‌ای را که شامل کلید داده‌شده و یا خانه‌ای که در صورت موجود بودن ، این کلید در آن قرار می‌گرفت را پیدا می‌کند.

 record pair { key, value }
 var pair array slot[0..num_slots-1]
 function find_slot(key)
     i := hash(key) mod num_slots
     // search until we either find the key, or find an empty slot.
     while (slot[i] is occupied) and ( slot[i].key ≠ key )
         i = (i + 1) mod num_slots
     return i
 function lookup(key)
     i := find_slot(key)
     if slot[i] is occupied   // key is in table
         return slot[i].value
     else                     // key is not in table
         return not found
 function set(key, value)
     i := find_slot(key)
     if slot[i] is occupied   // we found our key
         slot[i].value = value
         return
     if the table is almost full
         rebuild the table larger (note 1)
         i = find_slot(key)
     slot[i].key   = key
     slot[i].value = value

یک مثال دیگر که نشان دهنده روش آدرس‌دهی باز است ;ارائه کردن تابعی برای تبدیل هریک از (4) بخش یک آدرس پروتکل اینترنت است . توجه شود که NOT , XOR , OR و AND عملگرهای بیتی هستند و عملگرهای << و >> عملگرهای ''شیفت منطقی'' به راست و چپ می‌باشند.

 // key_1,key_2,key_3,key_4 are following 3-digit numbers - parts of ip address xxx.xxx.xxx.xxx
 function ip(key parts)
     j := 1
     do
         key := (key_2 << 2)
         key := (key + (key_3 << 7))
         key := key + (j OR key_4 >> 2) * (key_4) * (j + key_1) XOR j
         key := key AND _prime_    // _prime_ is a prime number
         j := (j+1)
     while collision
     return key
یادداشت 1

دوباره ساختن یک جدول نیازمند در نظر گرفتن یک آرایه بزرگ و به استفاده متناوب از تابع set است تا تمام عنصرهای آرایه قبلی را به آرایه بزگتر جدید وارد کنیم .به طور معمول اندازه آرایه دارای ''رشد نمایی'' می‌باشد ، به طور مثال اندازه جدید را دوبرابراندازه آرایه قبلی در نظر می‌گیریم.

 function remove(key)
     i := find_slot(key)
     if slot[i] is unoccupied
         return   // key is not in the table
     j := i
     loop
         mark slot[i] as unoccupied
        r2: (note 2)
         j := (j+1) mod num_slots
         if slot[j] is unoccupied
             exit loop
         k := hash(slot[j].key) mod num_slots
         // k lies cyclically in ]i,j]
         // |    i.k.j |
         // |....j i.k.| or  |.k..j i...|
         if ( (i<=j) ? ((i<k)&&(k<=j)) : ((i<k)||(k<=j)) )
             goto r2;
         slot[i] := slot[j]
         i := j
یادداشت 2

برای تمام داده‌های مربوط به یک گروه(داده‌هایی مربوط به یک گروه‌اند که توالی ایجاد شده برای آن‌ها به وسیله درهم‌ساز یکسان است), نباید هیچ خانه‌ای به صورت خالی بین خانه‌ی نتیجه طبیعی درهم‌ساری و خانه‌ای که هم‌اکنون در آن قرار دارند وجود داشته باشد.(در غیر این صورت قبل از اینکه به آن خانه برسیم روند یافتن آن پایان می‌یابد).[درحال ویرایش]

یک روش دیگر برای حذف علامت گذاری آن خانه به عنوان حذف شده است. هرچند این روش سرانجام نیازمند دوباره ساختن جدول فقط برای پاک کردن داده‌های پاک شده می‌باشد(توجه شود منظور زمانی است که بخواهیم هیچ خانه‌ای علامت گذاری نشده باشد). این روش انجام بروز رسانی و حذف در پیچیدگی زمانی (O(1 برای داده‌های موجود را ممکن می‌کند , با دوباره ساختن گاه‌به‌گاه جدول در صورتی که تعداد خانه‌های علامت گذاری زیاد باشد.

روش حذف گفته شده در پیچیدگی زمانی (O(1 فقط در بررسی خطی با قدم‌های واحد ممکن است . در حالتی که بخواهیم تعداد زیادی داده را به صورت همزمان حذف کنیم , علامت‌ گذاری خانه‌ها برای حذف شدن و دوباره ساختن جدول می‌تواند کاراتر باشد.

منابع[ویرایش]

ویکی‌پدیای انگلیسی :Open addressing ، Linear probing ، Quadratic probing و Double hashing

مقدمه‌ای برالگوریتم‌ها , نشر درخشش , چاپ سوم , مترجمان:گروه مهندسی پژوهشی خوارزمی , مهدی رواخواه , محمود عالمی , محسن اسدی ، شبنم جعفرخانی ، شادی لنگری ، الهام صدر