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

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

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

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

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

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

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

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

تصادم

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

فیلم آموزش مروری بر توابع Hash و خطر تصادم در آن ها (رایگان) در فرادرس

کلیک کنید

در راهبرد زنجیره‌سازی مجزا، از یک آرایه یا لیست پیوندی دیگر برای ذخیره‌سازی چند مقدار در یک اندیس واحد استفاده می‌شود. به تصویر زیر دقت کنید. هر دو کلید 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}

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

• مجموعه آموزش‌های مهندسی نرم افزار
• آموزش مروری بر توابع Hash و خطر تصادم در آن ها
• مجموعه آموزش‌های برنامه‌‌نویسی
• آموزش درهم سازی در ساختمان داده
• پیاده سازی جدول هش (Hash Table) در جاوا اسکریپت — راهنمای مقدماتی
• تابع هش یا درهم سازی (Hash Function) چیست؟ — به زبان ساده
• انواع الگوریتم های جستجو و Hash Table — راهنمای جامع

==