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

در مطلب قبلی در مورد Hashing نوشتم. نمونه هایی از آن در دنیای واقعی :

کد شناسایی دانشجویی

کد کتاب در کتابخانه

اطلاعات دانشجو <----- می رسیم به ----- کد شناسایی دانشجو 

اطلاعات کتاب <----- می رسیم به ------ کد کتاب 

 

کد شناسایی دانشجو یا کد کتاب در موارد بالا کلیدهای ما هستند برای رسیدن به اطلاعات دانشجو یا اطلاعات کتاب. برای شناسایی کلید در یک سیستم باید موارد زیر را در نظر بگیریم :

اول برای هر داده منحصربفرد (یکتا) باشد،

دوم برای همه داده ها موجود باشد (تهی نباشد)

سوم ثابت باشد. 

سپس کلید به عنوان ورودی به تابع هشینگ ارسال می شود و خروجی کلید هش شده (اندیس) خواهد بود، به صورت زیر:

Key ------- hash function ------> hash key

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

مراحل این کار در 2 مرحله پیاده سازی خواهد شد:

1- هر مورد (کلید) به یک عدد صحیح تبدیل می شود و از آن به عنوان اندیس برای نگهداری داده اصلی (مقدار) استفاده می شود.

hash = hash function(key)

index = hash % array_size ( a number between 0 to array_size - 1 )

2- کلید در جدول هَش نگهداری می شود جایی که می توان به سرعت توسط کلید بازیابی شود. به مقدارها (داده ها) که در این ساختار نگهداری می شود hash table می گویند. 

The values stored in this data structure called hash table.