جنگولرن

Forwarded from بنیاد پایتون کاران فارسی (SorousH)

HashMaps به بیان ساده:
قرار هست ببینیم associative array چیه، hashmap چیه، چه ارتباطی به dictionary داره، ویژگی هاشون چیه، hash collision چیه، چطور برطرف میشن، نمونه خیلی سادش رو پیاده سازی کنیم و در انتها یه نمونه کامل هم ببینیم ازش.

خب... زمانی که ما یک سری دیتا داریم که به هم مرتبط هستن میتونیم اون ها رو توی یه collection نگهداری کنیم مثلا array. اطلاعاتی مثل تمام نمرات دانش آموزان یک کلاس:

grades = [17, 19, 18, ...]

و با ایندکس های عددی بهشون دسترسی پیدا کنیم:

grades[2]

خیلی هم سریع هستن array ها تو دسترسی چون مستقیم میریم سراغ همون نمره ای که نیاز داریم.
مشکل کجاست؟
مشکل اینه که برای ما سخته حفظ کنیم کدوم ایندکس برای کدوم شخص بوده و ترجیح میدیم که اگه نمره ی شخصی رو میخوایم به جای اینکه یه عدد بی معنی بدیم، اسمش رو بدیم و نمرش رو بگیریم:

grades["ali"]

راه حل چیه؟
اینکه اسمش رو(که بهش میگیم کلید) متصل یا مربوط یا "associate" بکنیم به نمرش.
چطوری؟ مثلا:

grades = [("reza", 17), ("sara", 19), ("ali", 18)]

و بعد هم اینجوری میگیریم:

def get_grade(person_name):
    for name, grade in grades:
        if name == person_name:
            return grade

print(get_grade("ali"))

خیلی بهتر و راحت تر شد الان...
چیزی که ما بالا ساختیم یک پیاده سازی (بد) از associative array بود. چون associate کردیم یک کلید رو به مقدارش. associative array یک abstract هست و میتونه به شکل های مختلف پیاده سازی بشه.

خب... فقط یه مشکلی هست الان:
قبلا که با ایندکس میگرفتیم صاف میرفتیم سراغ خودش، الان مجبوریم که iterate کنیم روشون و دونه دونه بگردیم تا برسیم به اونی که میخوایم. کنده!! (شما مثال های این پست رو با ۱۰۰۰ تا داده مثلا تصور کنید)

راه حل چیه؟
اینکه بیایم "یه جوری" این اسم ها رو map کنیم به ایندکس های عددی تا دوباره بتونیم صاف بریم سراغ اونی که میخوایم و سرعت بهتر بگیریم.

چطور اینکارو بکنیم؟
مثلا بیایم یک فانکشن بنویسیم که از کلیدها عدد تولید کنیم به این صورت که اعداد اسکی متناظر با هر حرف از کلیدمون رو باهم جمع کنیم. یعنی برای sara داریم:

s: 115
a: 97
r: 114
a: 97

در نتیجه:
"sara" # -> 115 + 97 + 114 + 97 -> 423
این میشه فانکشنش:

def hash_func(string):
    return sum(map(ord, string))

حالا یه لیست بسازیم که ۵ تا جای خالی داره:

grades = [None, None, None, None, None]

خب حالا الان عددی که از هش کردن(پس یه هش فانکشن ساده بود اون) کلید sara به دست آوردیم و چطور map کنیم به یکی از ایندکس های لیستمون؟ ما که ۴۲۳ تا slot نداریم...
باقی ماندش رو با طول لیستمون حساب کنیم!
اینطوری مطمئن هستیم که داخل اون رنجی که میخوایم هست. پس:
423 % 5 -> 3
کافیه sara و نمرش رو توی ایندکس شماره ۳ ذخیره کنیم:

grades = [None, None, None, ("sara", 19), None]

اگه همین کار رو برای باقی هم بکنیم همچین چیزی میشه:

grades = [
    ("ali", 18),
    None,
    None,
    ("sara", 19),
    ("reza", 17),
]

(تو پرانتز حواسمون هست که ترتیبش عوض شد...)

الان خوب شد. هر کدوم از نمره هارو بخوایم بگیریم اول اون کلید رو hash میکنیم بعد باقی ماندش رو حساب میکنیم میشه ایندکس مورد نظر. دیگه iteration ای در کار نیست و به time complexity عه O(1) رسیدیم. الان get_grade عه ما اینطوری شد:

def hash_func(string):
    return sum(map(ord, string))

def get_grade(person_name):
    hash_value = hash_func(person_name)
    idx = hash_value % 5
    return grades[idx][1]

print(get_grade("reza"))

موقع insert کردن هم دقیقا برعکس همین شکل عمل میکنیم یعنی ابتدا هش میکنیم بعد باقیمانده میگیریم بعد که فهمیدیم کدوم slot برای اون کلید میشه میذاریمش اونجا. درواقع هر چیزی که برای get کردن میگیم برعکسش برای set کردن میشه.

خب ما الان تونستیم associative array رو با کمک hashmap پیاده سازی کنیم :) بریم ادامش...

حالا اگه اسم یکی دیگه از دانشجو ها aras بود چی؟
(پست بعدی)

پست ۱ از ۳

👍2

548 views04:42