درهم‌سازی جهانی

استفاده از درهم سازی جهانی (در یک الگوریتم تصادفی یا ساختمان داده) به انتخاب یک تابع درهم سازی اتفاقی از خانواده توابع درهم ساز با ویژگی ریاضی قطعی اشاره دارد. این ویژگی، تعداد پائین برخوردها را تضمین می‌کند، حتی اگر داده توسط دشمن یا رقیب انتخاب شده باشد. بسیاری از خانواده‌های جهانی برای درهم سازی اعداد صحیح، بردارها و رشته‌ها شناخته شده‌اند و ارزیابی آن‌ها بسیار اثربخش و مفید است.

درهم سازی جهانی، موارد استفادهٔ فراوانی در علوم کامپیوتر دارد، برای مثال در پیاده‌سازی جداول درهم سازی، الگوریتم‌های تصادفی و رمزنگاری.

معرفی

فرض کنید می‌خواهیم کلیدهایی را از مجموعهٔ جهانی U به مجموعهٔ {M = {۰٬۱٬۲,…،m-1 بنگاریم. الگوریتم باید چندین زیر مجموعه از U را به نام S و به اندازه n ایجاد کند که در آغاز کار معین نیستند. معمولاً هدف از درهم سازی، داشتن کمترین تعداد برخورد است. یک تابع درهم ساز معین هیچ تضمینی نمی‌دهد که این ویژگی برقرار باشد. به همین دلیل، تابع درهم ساز معین اجازهٔ درهم سازی مجدد را نمی‌دهد: گاهی اوقات ورودی ای که به تابع درهم ساز داده می‌شود، بد است؛ بدین معنی که باعث برخوردهای بسیار می‌شود، بنابراین ممکن است که باعث ایجاد تمایل برای تعویض تابع درهم ساز شود.

ضمانت‌های ریاضی

برای هر مجموعه ثابت S با n کلید، استفاده از درهم سازی جهانی، ویژگی‌های زیر را تضمین می‌کند:

  • تعداد کلیدهایی که برای هر x ثابت در S انتظار می‌رود، برابر است با n/m.
  • تعداد زوج کلیدهای x,y در S که x≠y و (H(x) = H(y است، بیشتر از n(n-1)/2m نخواهد بود.
  • تعداد کلیدهای حاضر با حداقل t کلید در آنها، بیشتر از (2n/(t-2(n/m)+۱ نخواهد بود.

همان گونه که این ویژگی‌ها برای هر مجموعه ثابت S تضمین می‌کنند، اگر مجموعه داده توسط دشمن یا رقیب نیز انتخاب شود، باز هم ویژگی‌ها تغییر نخواهند کرد. هرچند اگر دشمن یا رقیب بتواند انتخاب تصادفی الگوریتم را مشاهده کند، تصادفی بودن خدمتی نخواهد کرد و مسئله همانند درهم سازی معین خواهد بود.

دو ویژگی انتهایی معمولاً در اتصال با درهم سازی مجدد مورد استفاده قرار می‌گیرند. برای مثال، یک الگوریتم تصادفی ممکن است برای اداره کردن تعداد (O(n برخورد آماده باشد. اگر برخوردهای بسیاری پیش آید، h دیگری از خانواده انتخاب و الگوریتم تکرار می‌شود. جهانی بودن تضمین می‌کند که تعداد تکرارها، یک متغیر تصادفی هندسی است.

سازه‌ها

از آنجا که هر دادهٔ کامپیوتری را می‌توان با یک یا چند کلمه ماشین نمایش داد، به‌طور کلی نیاز است تا برای ۳ نوع از دامنه تابع درهم سازی داشته باشیم: کلمات ماشین (اعداد صحیح)؛ بردارهای با طول ثابت از کلمات ماشین؛ و بردارهای با طول متغیر (رشته‌ها).

پیوندهای مفید
  • درهم سازی مستقل از K
  • درهم سازی نورد
  • درهم سازی تسطیح
  • تابع درهم ساز یک طرفه جهانی

منابع
    • Universal Classes of Hash Functions". Journal of Computer and System Sciences
    • Miltersen, Peter Bro. "Universal Hashing
    • Black, J. ; Halevi, S. ; Krawczyk, H. ; Krovetz, T. (1999).
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.