تصادم التجزئة

TypeScript

/* جدول تجزئة بالسلسلة المنفصلة */
class HashMapChaining {
    #size: number; // عدد أزواج المفتاح-القيمة
    #capacity: number; // سعة جدول التجزئة
    #loadThres: number; // عتبة معامل الحمولة لتفعيل التوسيع
    #extendRatio: number; // مضاعف التوسيع
    #buckets: Pair[][]; // مصفوفة الدلاء

    /* البانية */
    constructor() {
        this.#size = 0;
        this.#capacity = 4;
        this.#loadThres = 2.0 / 3.0;
        this.#extendRatio = 2;
        this.#buckets = new Array(this.#capacity).fill(null).map((x) => []);
    }

    /* دالة التجزئة */
    #hashFunc(key: number): number {
        return key % this.#capacity;
    }

    /* معامل الحمولة */
    #loadFactor(): number {
        return this.#size / this.#capacity;
    }

    /* عملية الاستعلام */
    get(key: number): string | null {
        const index = this.#hashFunc(key);
        const bucket = this.#buckets[index];
        // اجتز الدلو، وإذا وُجد key فأعِد val المقابل
        for (const pair of bucket) {
            if (pair.key === key) {
                return pair.val;
            }
        }
        // إذا لم يُعثر على key، أعِد null
        return null;
    }

    /* عملية الإضافة */
    put(key: number, val: string): void {
        // عندما يتجاوز معامل الحمولة العتبة، نفّذ التوسيع
        if (this.#loadFactor() > this.#loadThres) {
            this.#extend();
        }
        const index = this.#hashFunc(key);
        const bucket = this.#buckets[index];
        // اجتز الدلو، وإذا صادفت key المحدد، فحدّث val المقابل وأعِد
        for (const pair of bucket) {
            if (pair.key === key) {
                pair.val = val;
                return;
            }
        }
        // إذا لم يكن key موجوداً، ألحق زوج المفتاح-القيمة بالنهاية
        const pair = new Pair(key, val);
        bucket.push(pair);
        this.#size++;
    }

    /* عملية الحذف */
    remove(key: number): void {
        const index = this.#hashFunc(key);
        let bucket = this.#buckets[index];
        // اجتز الدلو واحذف زوج المفتاح-القيمة منه
        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket.splice(i, 1);
                this.#size--;
                break;
            }
        }
    }

    /* توسيع جدول التجزئة */
    #extend(): void {
        // خزّن جدول التجزئة الأصلي مؤقتاً
        const bucketsTmp = this.#buckets;
        // هيّئ جدول التجزئة الجديد الموسّع
        this.#capacity *= this.#extendRatio;
        this.#buckets = new Array(this.#capacity).fill(null).map((x) => []);
        this.#size = 0;
        // انقل أزواج المفتاح-القيمة من جدول التجزئة الأصلي إلى الجديد
        for (const bucket of bucketsTmp) {
            for (const pair of bucket) {
                this.put(pair.key, pair.val);
            }
        }
    }

    /* طباعة جدول التجزئة */
    print(): void {
        for (const bucket of this.#buckets) {
            let res = [];
            for (const pair of bucket) {
                res.push(pair.key + ' -> ' + pair.val);
            }
            console.log(res);
        }
    }
}

TypeScript

/* جدول تجزئة بالعنونة المفتوحة */
class HashMapOpenAddressing {
    private size: number; // عدد أزواج المفتاح-القيمة
    private capacity: number; // سعة جدول التجزئة
    private loadThres: number; // عتبة معامل الحمولة لتفعيل التوسيع
    private extendRatio: number; // مضاعف التوسيع
    private buckets: Array<Pair | null>; // مصفوفة الدلاء
    private TOMBSTONE: Pair; // علامة الحذف

    /* البانية */
    constructor() {
        this.size = 0; // عدد أزواج المفتاح-القيمة
        this.capacity = 4; // سعة جدول التجزئة
        this.loadThres = 2.0 / 3.0; // عتبة معامل الحمولة لتفعيل التوسيع
        this.extendRatio = 2; // مضاعف التوسيع
        this.buckets = Array(this.capacity).fill(null); // مصفوفة الدلاء
        this.TOMBSTONE = new Pair(-1, '-1'); // علامة الحذف
    }

    /* دالة التجزئة */
    private hashFunc(key: number): number {
        return key % this.capacity;
    }

    /* معامل الحمولة */
    private loadFactor(): number {
        return this.size / this.capacity;
    }

    /* ابحث عن فهرس الدلو المقابل لـ key */
    private findBucket(key: number): number {
        let index = this.hashFunc(key);
        let firstTombstone = -1;
        // فحص خطي، توقف عند مصادفة دلو فارغ
        while (this.buckets[index] !== null) {
            // إذا صادفت key، فأعِد فهرس الدلو المقابل
            if (this.buckets[index]!.key === key) {
                // إذا صادفت علامة حذف سابقاً، فانقل زوج المفتاح-القيمة إلى ذلك الفهرس
                if (firstTombstone !== -1) {
                    this.buckets[firstTombstone] = this.buckets[index];
                    this.buckets[index] = this.TOMBSTONE;
                    return firstTombstone; // أعِد فهرس الدلو المنقول
                }
                return index; // أعِد فهرس الدلو
            }
            // سجّل أول علامة حذف تُصادفها
            if (
                firstTombstone === -1 &&
                this.buckets[index] === this.TOMBSTONE
            ) {
                firstTombstone = index;
            }
            // احسب فهرس الدلو، وعُد إلى الرأس إذا تجاوزت الذيل
            index = (index + 1) % this.capacity;
        }
        // إذا لم يكن key موجوداً، فأعِد فهرس الإدراج
        return firstTombstone === -1 ? index : firstTombstone;
    }

    /* عملية الاستعلام */
    get(key: number): string | null {
        // ابحث عن فهرس الدلو المقابل لـ key
        const index = this.findBucket(key);
        // إذا وُجد زوج المفتاح-القيمة، فأعِد val المقابل
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            return this.buckets[index]!.val;
        }
        // إذا لم يكن زوج المفتاح-القيمة موجوداً، فأعِد null
        return null;
    }

    /* عملية الإضافة */
    put(key: number, val: string): void {
        // عندما يتجاوز معامل الحمولة العتبة، نفّذ التوسيع
        if (this.loadFactor() > this.loadThres) {
            this.extend();
        }
        // ابحث عن فهرس الدلو المقابل لـ key
        const index = this.findBucket(key);
        // إذا وُجد زوج المفتاح-القيمة، فاكتب فوق val وأعِد
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            this.buckets[index]!.val = val;
            return;
        }
        // إذا لم يكن زوج المفتاح-القيمة موجوداً، فأضف زوج المفتاح-القيمة
        this.buckets[index] = new Pair(key, val);
        this.size++;
    }

    /* عملية الحذف */
    remove(key: number): void {
        // ابحث عن فهرس الدلو المقابل لـ key
        const index = this.findBucket(key);
        // إذا وُجد زوج المفتاح-القيمة، فاكتب فوقه علامة الحذف
        if (
            this.buckets[index] !== null &&
            this.buckets[index] !== this.TOMBSTONE
        ) {
            this.buckets[index] = this.TOMBSTONE;
            this.size--;
        }
    }

    /* توسيع جدول التجزئة */
    private extend(): void {
        // خزّن جدول التجزئة الأصلي مؤقتاً
        const bucketsTmp = this.buckets;
        // هيّئ جدول التجزئة الجديد الموسّع
        this.capacity *= this.extendRatio;
        this.buckets = Array(this.capacity).fill(null);
        this.size = 0;
        // انقل أزواج المفتاح-القيمة من جدول التجزئة الأصلي إلى الجديد
        for (const pair of bucketsTmp) {
            if (pair !== null && pair !== this.TOMBSTONE) {
                this.put(pair.key, pair.val);
            }
        }
    }

    /* طباعة جدول التجزئة */
    print(): void {
        for (const pair of this.buckets) {
            if (pair === null) {
                console.log('null');
            } else if (pair === this.TOMBSTONE) {
                console.log('TOMBSTONE');
            } else {
                console.log(pair.key + ' -> ' + pair.val);
            }
        }
    }
}