Hashmaps – انجمن DEV

تعریف

Hashmaps که به عنوان جداول هش یا فرهنگ لغت نیز شناخته می شود، یک ساختار داده بنیادی در علوم کامپیوتر است که برای ذخیره و بازیابی موثر جفت های کلید-مقدار استفاده می شود. در هشمپ، هر کلید از طریق یک تابع هش به یک مقدار خاص نگاشت می شود، که کلید را به یک شاخص عددی تبدیل می کند که برای ذخیره و بازیابی مقدار مرتبط در یک ساختار داده آرایه مانند به نام سطل استفاده می شود.

فرآیند افزودن یک جفت کلید-مقدار به یک نقشه هشم شامل مراحل زیر است:

• تابع هش کلید را به عنوان ورودی می گیرد و یک کد هش تولید می کند که یک مقدار صحیح است که کلید را به شکل فشرده تر و استانداردتر نشان می دهد.
• سپس کد هش برای محاسبه یک شاخص در ساختار سطلی آرایه مانند استفاده می شود، جایی که مقدار مربوط به کلید را می توان ذخیره کرد.
• اگر مقداری از قبل در شاخص محاسبه شده ذخیره شده باشد، یک برخورد رخ داده است و یک استراتژی حل برخورد برای رسیدگی به برخورد و ذخیره مقدار جدید در یک سطل دیگر استفاده می شود.

• اگر مقداری در شاخص محاسبه شده ذخیره نشده باشد، جفت کلید-مقدار جدید در سطل آن شاخص ذخیره می شود.
  هنگام بازیابی یک مقدار از هشمپ، فرآیند مشابه است:

• تابع هش روی کلید برای محاسبه کد هش اعمال می شود.

• کد هش برای محاسبه شاخص در ساختار سطلی که مقدار باید در آن ذخیره شود استفاده می شود.

• مقدار شاخص محاسبه شده برگردانده می شود، یا اگر مقداری در آن شاخص ذخیره نشده باشد، کلید در نقشه هشم نیست.

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

  پیاده سازی
  

class HashTable:
    def __init__(self, size):
        self.size = size
        self.hash_table = self.create_buckets()

    def create_buckets(self):
        return [[] for _ in range(self.size)]

    def set_val(self, key, val):
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket[index] = (key, val)
        else:
            bucket.append((key, val))

    def get_val(self, key):
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
            if record_key == key:
                found_key = True
                break
        if found_key:
            return record_val
        else:
            return "No record found"

    def delete_val(self, key):
        hashed_key = hash(key) % self.size
        bucket = self.hash_table[hashed_key]
        found_key = False
        for index, record in enumerate(bucket):
            record_key, record_val = record
            if record_key == key:
                found_key = True
                break
        if found_key:
            bucket.pop(index)
        return

    def __str__(self):
        return "".join(str(item) for item in self.hash_table)

معایب:
با این حال، هشمپ ها معایبی نیز دارند. مهم ترین مسئله احتمال برخورد است که در صورت عدم مدیریت صحیح می تواند عملکرد ساختار داده را کاهش دهد. علاوه بر این، هش مپ ها می توانند در برابر انواع خاصی از حملات آسیب پذیر باشند، مانند حملات برخورد هش، که می تواند برای غلبه بر ساختار سطل با کلیدهای ساخته شده عمدی استفاده شود.

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