جداول هش 101: برخورد، تغییر اندازه، هش کردن

Summarize this content to 400 words in Persian Lang

درک نماد Big O را فرض می کند. نمونه ها در جاوا اسکریپت هستند. منابع اطلاعاتی “شکستن مصاحبه کدگذاری” توسط گیل لااکمن مک داول

درک جداول هش

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

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

اجزای کلیدی یک جدول هش

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

تابع هش چیست؟

یک تابع هش یک جزء حیاتی از جدول هش است. این یک الگوریتم است، معمولاً به شکل یک تابع، که یک ورودی (یا «کلید») را می گیرد و رشته ای با اندازه ثابت از بایت ها، معمولاً به شکل یک عدد صحیح را برمی گرداند. خروجی a نامیده می شود کد هش یا به سادگی یک هش.

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

ویژگی های یک عملکرد هشینگ خوب:

قطعی: برای یک ورودی معین، همیشه باید همان خروجی هش را تولید کند.

توزیع یکنواخت: باید ورودی های مورد انتظار را تا حد امکان به طور یکنواخت در محدوده خروجی خود ترسیم کند.

کارآمد: باید سریع محاسبه شود.

اثر بهمن: یک تغییر کوچک در ورودی باید به خروجی هش متفاوتی منجر شود.

چرا از آرایه ای از لیست های پیوندی استفاده می کنیم؟

استفاده از آرایه ای از لیست های پیوندی در پیاده سازی جدول هش یک تکنیک رایج است که به نام شناخته می شود زنجیر زدن. این رویکرد چندین مزیت را ارائه می دهد:

برخورد با برخورد: دلیل اصلی استفاده از آرایه‌ای از لیست‌های پیوندی، مدیریت مؤثر برخوردها است. وقتی دو کلید هش می‌شوند و به یک شاخص نگاشت می‌شوند، می‌توانیم به سادگی جفت کلید-مقدار جدید را به لیست پیوندی در آن فهرست اضافه کنیم.

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

Array: [0] -> (key1, value1) -> (key2, value2)
[1] -> (key3, value3)
[2] -> (key4, value4) -> (key5, value5) -> (key6, value6)
[3] -> Empty
[4] -> (key7, value7)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

در این مثال، کلیدهای 1 و 2 به فهرست 0 هش می‌شوند، در حالی که کلیدهای 4، 5 و 6 همگی به فهرست 2 هش می‌شوند.

درج جفت کلید-مقدار

اکنون که درک خوبی از توابع درهم‌سازی و دلیل استفاده از زنجیره‌سازی داریم، اجازه دهید جریان درج جفت‌های کلید-مقدار در جدول هش را مرور کنیم:

هنگام وارد کردن کلید (هر مقدار)، ابتدا کلید را محاسبه می کنیم کد هش (معمولا یک int یا long). این امکان وجود دارد که دو کلید مختلف بتوانند کد هش یکسانی داشته باشند زیرا ممکن است تعداد نامتناهی کلید و تعداد محدودی وجود داشته باشد. ints.
کد هش را به یک شاخص در آرایه نگاشت کنید. یک روش رایج برای نگاشت کد هش به آرایه استفاده از عملگر مدول. (مثلا hash(key) % array.length)). این امکان وجود دارد که دو کد هش مختلف با این روش به یک شاخص نگاشت شوند.
در یک فهرست، یک لیست پیوندی از کلیدها و مقادیر وجود دارد. جفت کلید-مقدار را در این شاخص ذخیره کنید. برخوردها زمانی اتفاق می‌افتند که کلیدها دارای کدهای هش یکسان باشند یا کدهای هش به همان شاخص‌ها نگاشت شوند.

دسترسی به جفت های کلید-مقدار

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

با فرض اجرای خوب، دسترسی به جفت های کلید-مقدار (درج و حذف نیز) طول می کشد

O(1)O (1)O(1)

.

چه چیزی اجرای یک جدول هش را “خوب” می کند؟

یک جدول هش که به خوبی اجرا شده باشد باید کارایی، استفاده از فضا و مدیریت برخورد را متعادل کند. در اینجا عوامل کلیدی که به اجرای خوب جدول هش کمک می کنند آورده شده است:

یک تابع هش خوب

قلب هر جدول هش تابع هش آن است. یک تابع هش خوب باید:

سریع حساب کنید
برخوردها را به حداقل برسانید

ضریب بار بهینه

را ضریب بار نسبت اسلات های پر شده به کل اسلات ها در جدول هش است. حفظ ضریب بار مناسب بسیار مهم است:

معمولی نقطه شیرین بین 0.6 و 0.75 است

خیلی کم (
خیلی زیاد (> 0.8): خطر برخورد را افزایش می دهد

تکنیک های تشخیص برخورد

دو روش اصلی برای مدیریت برخورد عبارتند از:

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

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

تغییر اندازه پویا

با افزایش تعداد عناصر، اندازه جدول هش برای حفظ عملکرد باید تغییر کند:

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

این عملیات گران است اما نادر است و پیچیدگی زمانی مستهلک شده را در O(1) نگه می دارد.

پیاده سازی جاوا اسکریپت

این پیاده سازی از تغییر اندازه و زنجیره ای برای حل برخورد استفاده می کند. فرض می کنیم که کلیدهای ما اعداد صحیح هستند.

برای تابع هش + نقشه برداری، آن را بسیار ساده نگه می داریم و به سادگی کلید زیر را انجام می دهیم:

کهy%الفrrالفyجالفصالفجمنتیyکلید \hspace{0.2cm} \% \hspace{0.2cm} آرایه \hspace{0.1cm} ظرفیتکچشم%الفrrالفyجالفصالفجمنتیy

OOP کلاسیک

class HashNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
}
}

class HashTable {
constructor(capacity = 16) {
this.capacity = capacity;
this.size = 0;
this.buckets = new Array(this.capacity).fill(null);
this.threshold = 0.75;
}

hash(key) {
return key % this.capacity;
}

insert(key, value) {
const index = this.hash(key);
if (!this.buckets[index]) {
this.buckets[index] = new HashNode(key, value);
this.size++;
} else {
let currentNode = this.buckets[index];
while (currentNode.next) {
if (currentNode.key === key) {
currentNode.value = value;
return;
}
currentNode = currentNode.next;
}
if (currentNode.key === key) {
currentNode.value = value;
} else {
currentNode.next = new HashNode(key, value);
this.size++;
}
}

if (this.size / this.capacity >= this.threshold) {
this.resize();
}
}

get(key) {
const index = this.hash(key);
let currentNode = this.buckets[index];
while (currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return undefined;
}

remove(key) {
const index = this.hash(key);
if (!this.buckets[index]) {
return false;
}
if (this.buckets[index].key === key) {
this.buckets[index] = this.buckets[index].next;
this.size–;
return true;
}
let currentNode = this.buckets[index];
while (currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next = currentNode.next.next;
this.size–;
return true;
}
currentNode = currentNode.next;
}
return false;
}

resize() {
const newCapacity = this.capacity * 2;
const newBuckets = new Array(newCapacity).fill(null);
this.buckets.forEach(head => {
while (head) {
const newIndex = head.key % newCapacity;
const next = head.next;
head.next = newBuckets[newIndex];
newBuckets[newIndex] = head;
head = next;
}
});
this.buckets = newBuckets;
this.capacity = newCapacity;
}

getSize() {
return this.size;
}

getCapacity() {
return this.capacity;
}
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

OOP عملکردی

function createHashTable(initialCapacity = 16) {
let capacity = initialCapacity;
let size = 0;
let buckets = new Array(capacity).fill(null);
const threshold = 0.75;

function hash(key) {
return key % capacity;
}

function resize() {
const newCapacity = capacity * 2;
const newBuckets = new Array(newCapacity).fill(null);
buckets.forEach(function(head) {
while (head) {
const newIndex = head.key % newCapacity;
const next = head.next;
head.next = newBuckets[newIndex];
newBuckets[newIndex] = head;
head = next;
}
});
buckets = newBuckets;
capacity = newCapacity;
}

return {
insert: function(key, value) {
const index = hash(key);
const newNode = { key, value, next: null };

if (!buckets[index]) {
buckets[index] = newNode;
size++;
} else {
let currentNode = buckets[index];
while (currentNode.next) {
if (currentNode.key === key) {
currentNode.value = value;
return;
}
currentNode = currentNode.next;
}
if (currentNode.key === key) {
currentNode.value = value;
} else {
currentNode.next = newNode;
size++;
}
}

if (size / capacity >= threshold) {
resize();
}
},

get: function(key) {
const index = hash(key);
let currentNode = buckets[index];
while (currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return undefined;
},

remove: function(key) {
const index = hash(key);
if (!buckets[index]) {
return false;
}
if (buckets[index].key === key) {
buckets[index] = buckets[index].next;
size–;
return true;
}
let currentNode = buckets[index];
while (currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next = currentNode.next.next;
size–;
return true;
}
currentNode = currentNode.next;
}
return false;
},

getSize: function() {
return size;
},

getCapacity: function() {
return capacity;
}
};
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

Array:  [0] -> (key1, value1) -> (key2, value2)
        [1] -> (key3, value3)
        [2] -> (key4, value4) -> (key5, value5) -> (key6, value6)
        [3] -> Empty
        [4] -> (key7, value7)

class HashNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

class HashTable {
    constructor(capacity = 16) {
        this.capacity = capacity;
        this.size = 0;
        this.buckets = new Array(this.capacity).fill(null);
        this.threshold = 0.75;
    }

    hash(key) {
        return key % this.capacity;
    }

    insert(key, value) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            this.buckets[index] = new HashNode(key, value);
            this.size++;
        } else {
            let currentNode = this.buckets[index];
            while (currentNode.next) {
                if (currentNode.key === key) {
                    currentNode.value = value;
                    return;
                }
                currentNode = currentNode.next;
            }
            if (currentNode.key === key) {
                currentNode.value = value;
            } else {
                currentNode.next = new HashNode(key, value);
                this.size++;
            }
        }

        if (this.size / this.capacity >= this.threshold) {
            this.resize();
        }
    }

    get(key) {
        const index = this.hash(key);
        let currentNode = this.buckets[index];
        while (currentNode) {
            if (currentNode.key === key) {
                return currentNode.value;
            }
            currentNode = currentNode.next;
        }
        return undefined;
    }

    remove(key) {
        const index = this.hash(key);
        if (!this.buckets[index]) {
            return false;
        }
        if (this.buckets[index].key === key) {
            this.buckets[index] = this.buckets[index].next;
            this.size--;
            return true;
        }
        let currentNode = this.buckets[index];
        while (currentNode.next) {
            if (currentNode.next.key === key) {
                currentNode.next = currentNode.next.next;
                this.size--;
                return true;
            }
            currentNode = currentNode.next;
        }
        return false;
    }

    resize() {
        const newCapacity = this.capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        this.buckets.forEach(head => {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        this.buckets = newBuckets;
        this.capacity = newCapacity;
    }

    getSize() {
        return this.size;
    }

    getCapacity() {
        return this.capacity;
    }
}

function createHashTable(initialCapacity = 16) {
    let capacity = initialCapacity;
    let size = 0;
    let buckets = new Array(capacity).fill(null);
    const threshold = 0.75;

    function hash(key) {
        return key % capacity;
    }

    function resize() {
        const newCapacity = capacity * 2;
        const newBuckets = new Array(newCapacity).fill(null);
        buckets.forEach(function(head) {
            while (head) {
                const newIndex = head.key % newCapacity;
                const next = head.next;
                head.next = newBuckets[newIndex];
                newBuckets[newIndex] = head;
                head = next;
            }
        });
        buckets = newBuckets;
        capacity = newCapacity;
    }

    return {
        insert: function(key, value) {
            const index = hash(key);
            const newNode = { key, value, next: null };

            if (!buckets[index]) {
                buckets[index] = newNode;
                size++;
            } else {
                let currentNode = buckets[index];
                while (currentNode.next) {
                    if (currentNode.key === key) {
                        currentNode.value = value;
                        return;
                    }
                    currentNode = currentNode.next;
                }
                if (currentNode.key === key) {
                    currentNode.value = value;
                } else {
                    currentNode.next = newNode;
                    size++;
                }
            }

            if (size / capacity >= threshold) {
                resize();
            }
        },

        get: function(key) {
            const index = hash(key);
            let currentNode = buckets[index];
            while (currentNode) {
                if (currentNode.key === key) {
                    return currentNode.value;
                }
                currentNode = currentNode.next;
            }
            return undefined;
        },

        remove: function(key) {
            const index = hash(key);
            if (!buckets[index]) {
                return false;
            }
            if (buckets[index].key === key) {
                buckets[index] = buckets[index].next;
                size--;
                return true;
            }
            let currentNode = buckets[index];
            while (currentNode.next) {
                if (currentNode.next.key === key) {
                    currentNode.next = currentNode.next.next;
                    size--;
                    return true;
                }
                currentNode = currentNode.next;
            }
            return false;
        },

        getSize: function() {
            return size;
        },

        getCapacity: function() {
            return capacity;
        }
    };
}