جدول Hash — به زبان ساده

۲۴۵۷ بازدید
آخرین به‌روزرسانی: ۲۸ شهریور ۱۴۰۲
زمان مطالعه: ۳ دقیقه
جدول Hash — به زبان ساده

در جدول Hash از جفت‌های کلید-مقدار برای ذخیره‌سازی داده‌ها استفاده می‌شود. این جداول به دلیل سرعت و کارایی‌شان در تقریباً همه زبان‌های برنامه‌نویسی به نوعی پیاده‌سازی شده‌اند. جداول هَش در جاوا اسکریپت به نام شیء (Object) خوانده می‌شوند و در پایتون دیکشنری نام دارند و در جاوا، اسکالا و Go نیز به صورت Map نامگذاری شده‌اند. جداول هش به این دلیل ایجاد شده‌اند که انسان‌ها با استفاده از چیزهایی فراتر از اعداد فکر می‌کنند.

فهرست مطالب این نوشته
997696

آرایه‌ها عالی هستند؛ اما این که مجبور باشیم همه داده‌های خود را بر مبنای اندیس‌ها مدلسازی کنیم، کابوس وحشتناکی به حساب می‌آید. بنابراین جداول هش پدید آمده‌اند، زیرا مدلسازی داده‌ها به صورت ["passwords["gmail بسیار بهتر از مدلسازی آن‌ها به روش [passwords[0 است.

با این وجود، آیا تاکنون کنجکاو بوده‌اید که این ساختمان داده در پس‌زمینه چگونه سازماندهی شده است؟ رایانه‌ها به طور شهودی رشته‌های قابل خواندن از سوی انسان را به عنوان کلید تشخیص نمی‌دهند. بنابراین چگونه می‌توانند مقادیر مرتبط با کلیدها را ذخیره کنند؟

پاسخ کوتاه این است که لازم نیست رایانه‌ها چنین کاری انجام دهند. ما می‌توانیم یک تابع هش بسازیم که به عنوان یک مترجم عمل می‌کند. انسان‌ها کلمات را درک می‌کنند و رایانه‌ها اندیس‌ها را می‌فهمند. یک تابع هش می‌تواند یک کلمه را بردارد و آن را به اندیس مناسب تبدیل کند. به این ترتیب می‌توانیم داده‌ها را در یک آرایه ذخیره کنیم و از طریق اندیس به دنبال آن بگردیم.

ایده مفهومی تابع هش
ایده مفهومی تابع هش

بدین ترتیب جداول هش از یک تابع هش کردن یا درهم سازی (hashing) استفاده می‌کنند. ایجاد یک تابع هش کردن به کمی آشنایی با ریاضیات نیاز دارد. نکات مهم یک تابع هش کردن به شرح زیر هستند:

  1. تابع هش باید سریع باشد (بر حسب پیچیدگی زمانی).
  2. تابع هش کردن خروجی‌ها را در اندیس‌های خاص خوشه‌بندی نمی‌کند؛ بلکه آن‌ها را به طور یکنواختی توزیع می‌کند.
  3. تابع هش کردن قطعی است و ورودی‌های یکسان همواره خروجی‌های یکسان ارائه می‌کنند.

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

تصادم

مهم نیست که تابع هش کردن کار خود را تا چه حد خوب انجام دهد، چون همواره امکان بروز تصادم وجود دارد. تصادم به موقعیت‌هایی گفته می‌شود که دو ورودی اندیس خروجی یکسانی داشته باشند. دو راهبرد برای رفع تصادم وجود دارد که اولی «زنجیره‌سازی مجزا» (Separate chaining) و دومی «پراب کردن خطی» (linear probing) نام دارد.

در راهبرد زنجیره‌سازی مجزا، از یک آرایه یا لیست پیوندی دیگر برای ذخیره‌سازی چند مقدار در یک اندیس واحد استفاده می‌شود. به تصویر زیر دقت کنید. هر دو کلید darkblue و salmon باعث می‌شود اندیس یکسانی ایجاد شود. ما به جای بازنویسی مقدار موجود در اندیس 4، هر دو مقدار را در آرایه نگهداری می‌کنیم.

زنجیره‌سازی مجزا
طرز کار زنجیره‌سازی مجزا

در راهبرد پراب کردن خطی، زمانی که تصادمی رخ دهد، نخستین موقعیت آزاد بعدی در آرایه را یافته و جفت کلید-مقدار را در آن قرار می‌دهیم.

 پراب کردن خطی
طرز کار پراب کردن خطی

پیاده‌سازی کد نمونه

در قطعه کد زیر اثبات این مفهوم انجام یافته و ساده‌سازی زیادی نیز روی آن صورت گرفته است. تابع هش کردن تنها روی رشته‌ها کار می‌کند. این تابع روی همه کاراکترها اجرا می‌شود، انکودینگ UTF-8 آن را پیدا می‌کند و مقدار 96 را از آن کم می‌کند که باعث می‌شود ترتیب الفبایی پیدا کند. سپس مقدار در یک عدد اول ضرب می‌شود و به مجموع کل اضافه می‌شود. زمانی که همه کاراکترها در رشته محاسبه شدند، باقیمانده مجموع بر طول آرایه ذخیره‌سازی تقسیم می‌شود. به این ترتیب، می‌توانیم خروجی خود را از مقادیری که خارج از آرایه قرار می‌گیرند دور نگهداریم.

1class HashTable {
2    constructor(size=53){
3        this.keyMap = new Array(size)
4    }
5
6    _hash(key){
7        let total = 0
8        let WEIRD_PRIME = 31
9        for (let i=0; i < Math.min(key.length, 100); i++){
10            let char = key[i]
11            let value = char.charCodeAt(0) - 96
12            total = (total * WEIRD_PRIME + value) %    this.keyMap.length
13        }
14        return total;
15    }
16
17    set(key, value){
18        let hashedKey = this._hash(key)
19        if (!this.keyMap[hashedKey]) this.keyMap[hashedKey] = []
20        this.keyMap[hashedKey].push([key, value])
21        return this;
22    }
23
24    get(key){
25        let hashedKey = this._hash(key)
26        if (this.keyMap[hashedKey]) {
27            let found = this.keyMap[hashedKey].map((value) => {
28                if (value[0] === key) {
29                    return value[1]
30                }
31            })
32            return found[0]
33        } else {
34            return undefined
35        }
36    }
37
38    keys(){
39        let keys = []
40        for (let i=0; i < this.keyMap.length; i++){
41            if (this.keyMap[i]){
42                for (let j=0; j < this.keyMap[i].length; j++){
43                    if (!keys.includes(this.keyMap[i][j][0])){
44                        keys.push(this.keyMap[i][j][0])    
45                    }
46                }
47            }
48        }
49        return keys
50    }
51
52    values(){
53        let values = []
54        for (let i=0; i < this.keyMap.length; i++){
55            if (this.keyMap[i]){
56                for (let j=0; j < this.keyMap[i].length; j++){
57                    if (!values.includes(this.keyMap[i][j][1])) {
58                        values.push(this.keyMap[i][j][1])    
59                    }
60                }
61            }
62        }
63        return values
64    }
65}

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای ۱۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
verdi
۱ دیدگاه برای «جدول Hash — به زبان ساده»

ممنونم
متن زیر چیزی بود که دنبالش بودم:
رایانه‌ها به طور شهودی رشته‌های قابل خواندن از سوی انسان را به عنوان کلید تشخیص نمی‌دهند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *