شنبه ها و یک اصطلاح کامپیوتری (Hash function)

در پست قبل در مورد hash نوشتم. گفتیم تابعی وجود دارد که کلید را دریافت می کند و یک مقدار که اندیس مربوط به یک خانه از حافظه هست را برمی گرداند. در این مطلب در مورد این تابع می نویسم. 

به چه تابعی می گوییم Hash Function ؟

هر تابعی که یک داده با اندازه اولیه را بگیرد و آن را به داده با اندازه ثابت و مشخص نگاشت کند Hash Function می گویند. به مقدار خروجی این تابع Hash value یا Hash sum یا Hash code می گوییم. برای اینکه تابع Hash خوبی داشته باشیم باید یک سری نیازمندیها را رعایت کنیم: 

1. سادگی در محاسبات 
2. توزیع یکنواخت : باید یک توزیع یکنواخت در بین رکوردهای Hash table ایجاد کند و نباید نتایج به صورت شاخه ای و دسته ای باشد. 
3. کمترین تصادم ها : تصادم یعنی زمانی که چند کلید یک Hash value یکسان داشته باشند. برای جلوگیری از تصادم مهم هست که توسط تکنیک های شفاف سازی تصادم مدیریت شود. 

مثال: فرض کنیم می خواهیم متن ها را توسط Hash function زیر هَش کنیم. 

Hash function: مجموع کد اسکی هر کاراکتر و سپس باقیمانده آن بر عدد 599 (عدد اول احتمال یکسان شدن Hash value برای چند کاراکتر را کاهش می دهد.) 

متن ها : 'bcdefg' , 'cdefgb', 'defgbc', 'efgbcd' 

 

b      c     d      e      f      g

98   99   100  101  102  103                             sum = 603 

چون تمام متن ها کاراکترهای یکسان با جایگشت های مختلف هستند، مجموع تمام آنها 603 هست که نتیجه باقیمانده بر 599 می شود 4 . پس تمام مقادیر در اندیس یکسان 4 ذخیره می شوند. 

 

در اینجا پیچیدگی زمانی برای دستیابی به یک مقدار برابر O(n) است که n تعداد متن ها است. این پیچیدگی زمانی خیلی خوشایند نیست.