شرح جداول الهاش، مجموعات الهاش، وخرائط الهاش

جدول الهاش (Hash Table) هو هيكل بيانات يخزن البيانات باستخدام دالة هاش. يقوم بربط المفاتيح بالمواضع في مصفوفة داخلية، مما يسمح بالإدراج والبحث والحذف السريع في متوسط زمن O(1).

تُعد جداول الهاش من أهم المواضيع في هياكل البيانات والخوارزميات. إنها الأساس وراء مجموعات الهاش (Hash Sets) وخرائط الهاش (Hash Maps)، وتظهر في العديد من أنظمة البرمجيات الحقيقية مثل القواميس، وذاكرات التخزين المؤقت (caches)، وقواعد البيانات، والفهارس، والمترجمات (compilers)، وجداول التوجيه (routing tables)، وخدمات البحث.

مقدمة

عندما يحتاج المطورون إلى البحث عن البيانات بسرعة، لا تكون المصفوفة البسيطة كافية دائمًا. إذا كانت المصفوفة غير مرتبة، فقد يتطلب البحث التحقق من كل عنصر على حدة باستخدام البحث الخطي (Linear Search). وهذا يعطي تعقيدًا زمنيًا من O(n).

تحل جداول الهاش هذه المشكلة باستخدام فكرة مختلفة. فبدلاً من البحث عبر جميع العناصر، يستخدم جدول الهاش مفتاحًا ودالة هاش لحساب مكان تخزين البيانات.

يسمح هذا بالعديد من العمليات مثل الإدراج والبحث والتحديث والحذف لتكون سريعة جدًا في المتوسط. وبسبب ذلك، تُستخدم جداول الهاش بكثرة في لغات البرمجة، والأطر، وقواعد البيانات، وأنظمة الواجهة الخلفية (backend) في العالم الحقيقي.

ما هو جدول الهاش؟

جدول الهاش هو هيكل بيانات يخزن البيانات في بنية تشبه المصفوفة باستخدام دالة هاش. تحول دالة الهاش المفتاح إلى فهرس (index)، ويحدد هذا الفهرس مكان تخزين القيمة.

الفكرة الأساسية تبدو كالتالي:

key → hash function → index → bucket

على سبيل المثال، إذا أردنا تخزين مستخدم عن طريق البريد الإلكتروني، يمكن استخدام البريد الإلكتروني كمفتاح:

Key:   user@example.com
Value: User data

تحول دالة الهاش المفتاح إلى فهرس مصفوفة داخلي:

hash(user@example.com) % tableSize = 3

لذلك يتم تخزين القيمة عند فهرس الدلو (bucket) رقم 3.

لماذا جداول الهاش مهمة؟

تُعد جداول الهاش مهمة لأنها توفر بحثًا سريعًا جدًا. في العديد من التطبيقات، يحتاج المطورون إلى الإجابة على أسئلة مثل:

• هل اسم المستخدم هذا موجود بالفعل؟

• أي مستخدم ينتمي إلى هذا المعرف (ID)؟

• هل هذا العنصر موجود بالفعل في المجموعة؟

• كم مرة ظهرت هذه الكلمة؟

• هل هذه الصلاحية مخصصة لهذا الدور؟

• هل يمكننا استرداد البيانات المخزنة مؤقتًا باستخدام هذا المفتاح؟

بدون جدول هاش، قد تتطلب هذه العمليات مسح قائمة. مع جدول الهاش، يمكن إجراؤها غالبًا في متوسط زمن O(1).

مصطلحات جدول الهاش

قبل دراسة جداول الهاش بعمق، من المهم فهم المصطلحات الشائعة.

• المفتاح (Key): المعرف المستخدم لتخزين البيانات أو استردادها.

• القيمة (Value): البيانات الفعلية المرتبطة بالمفتاح.

• دالة الهاش (Hash function): دالة تحول المفتاح إلى قيمة هاش رقمية.

• الفهرس (Index): الموضع في المصفوفة الداخلية حيث قد يتم تخزين البيانات.

• الدلو (Bucket): فتحة (مكان) في المصفوفة الداخلية.

• التصادم (Collision): حالة ينتج فيها مفتاحان مختلفان نفس الفهرس.

• عامل التحميل (Load factor): قياس لمدى امتلاء جدول الهاش.

• إعادة الهاش (Rehashing): عملية تغيير حجم الجدول وإعادة توزيع المفاتيح.

تظهر هذه المصطلحات في كل تطبيق تقريبًا لجدول الهاش.

كيف يعمل جدول الهاش

يعمل جدول الهاش عادةً في ثلاث خطوات رئيسية.

1. يتم تمرير مفتاح إلى دالة هاش.

2. تولد دالة الهاش قيمة هاش رقمية.

3. يتم تحويل قيمة الهاش إلى فهرس مصفوفة.

على سبيل المثال:

Key: "apple"

Hash function output: 93029210

Table size: 10

Index = 93029210 % 10 = 0

القيمة المرتبطة بالمفتاح apple مخزنة في الدلو 0.

عندما نرغب في استرداد القيمة لاحقًا، يتم تمرير نفس المفتاح إلى نفس دالة الهاش. تنتج نفس الفهرس، وبالتالي يعرف جدول الهاش مكان البحث.

ما هي دالة الهاش؟

دالة الهاش هي دالة تأخذ مفتاح إدخال وتحوله إلى قيمة رقمية. ثم تُستخدم هذه القيمة الرقمية لحساب فهرس في المصفوفة الداخلية.

يجب أن تكون دالة الهاش الجيدة:

• تعيد دائمًا نفس الهاش لنفس المفتاح.

• توزع المفاتيح بالتساوي عبر الجدول.

• سريعة في الحساب.

• تقلل من التصادمات قدر الإمكان.

لأغراض تعليمية، يمكننا تخيل دالة هاش بسيطة تحول الأحرف إلى أرقام.

مثال على دالة هاش بسيطة

لنفترض أن لدينا المفتاح:

cat

يمكننا تحويل كل حرف إلى رمز رقمي وجمعها:

c = 99
a = 97
t = 116

hash = 99 + 97 + 116 = 312

إذا كان حجم الجدول 10، يصبح الفهرس:

index = 312 % 10 = 2

وبالتالي سيتم تخزين المفتاح cat في فهرس الدلو 2.

دالة الهاش هذه بسيطة ومفيدة للتعلم، ولكن دوال الهاش الحقيقية أكثر تقدمًا لأنها تحتاج إلى توزيع أفضل وعدد أقل من التصادمات.

جدول الهاش في الذاكرة

يستخدم جدول الهاش عادةً مصفوفة داخلية من الدلاء. يمكن لكل دلو تخزين زوج من المفتاح والقيمة، أو مجموعة من أزواج المفاتيح والقيم إذا حدثت تصادمات.

على سبيل المثال:

Index 0: empty
Index 1: empty
Index 2: key = cat, value = 5
Index 3: empty
Index 4: key = dog, value = 8

لا يقوم الجدول بتخزين العناصر بالترتيب الذي تم إدراجها به. بل يخزنها بناءً على فهرس الهاش.

هذا هو السبب في أن جداول الهاش ممتازة للبحث ولكنها غير مصممة للتجول المرتب (ordered traversal) إلا إذا كان تطبيق اللغة المحدد يحافظ على ترتيب الإدراج.

مثال تشغيل يدوي

دعنا نُدخل يدويًا ثلاثة أزواج من المفاتيح والقيم في جدول هاش صغير.

Table size = 5

سنستخدم دالة هاش تعليمية بسيطة:

hash(key) = sum of character codes
index = hash(key) % tableSize

نريد إدراج:

"cat" → 10
"dog" → 20
"bird" → 30

الخطوة 1: إدراج cat

احسب الهاش لـ cat:

c = 99
a = 97
t = 116

hash = 99 + 97 + 116 = 312

احسب الفهرس:

index = 312 % 5 = 2

خزن القيمة عند الفهرس 2:

Index 0: empty
Index 1: empty
Index 2: cat → 10
Index 3: empty
Index 4: empty

الخطوة 2: إدراج dog

احسب الهاش لـ dog:

d = 100
o = 111
g = 103

hash = 100 + 111 + 103 = 314

احسب الفهرس:

index = 314 % 5 = 4

خزن القيمة عند الفهرس 4:

Index 0: empty
Index 1: empty
Index 2: cat → 10
Index 3: empty
Index 4: dog → 20

الخطوة 3: إدراج bird

احسب الهاش لـ bird:

b = 98
i = 105
r = 114
d = 100

hash = 98 + 105 + 114 + 100 = 417

احسب الفهرس:

index = 417 % 5 = 2

الفهرس 2 يحتوي بالفعل على cat. هذا يخلق تصادمًا.

Index 2 already has:
cat → 10

New item:
bird → 30

يجب على جدول الهاش التعامل مع هذا التصادم باستخدام استراتيجية حل التصادم.

ما هو التصادم؟

يحدث التصادم عندما ينتج مفتاحان مختلفان نفس الفهرس في جدول الهاش.

على سبيل المثال:

cat  → index 2
bird → index 2

كلا المفتاحين يريدان استخدام نفس الدلو. التصادمات طبيعية في جداول الهاش لأن العديد من المفاتيح المحتملة تُربط بعدد محدود من الدلاء.

لا يحاول جدول الهاش الجيد جعل التصادمات مستحيلة. بدلاً من ذلك، يستخدم استراتيجية للتعامل معها بشكل صحيح.

استراتيجيات التعامل مع التصادمات

استراتيجيتان حل التصادم الأكثر شيوعًا هما:

• التسلسل المنفصل (Separate chaining).

• العنونة المفتوحة (Open addressing).

تحل كل استراتيجية التصادمات بطريقة مختلفة.

التسلسل المنفصل (Separate Chaining)

التسلسل المنفصل يعني أن كل دلو يمكنه تخزين أزواج متعددة من المفاتيح والقيم، عادةً في قائمة مرتبطة (linked list) أو مصفوفة ديناميكية.

إذا كان كل من cat و bird يربطان بالفهرس 2، يمكن للدلو تخزين كليهما:

Index 0: empty
Index 1: empty
Index 2: [cat → 10] → [bird → 30]
Index 3: empty
Index 4: dog → 20

عند البحث عن مفتاح في الفهرس 2، يتحقق جدول الهاش من العناصر الموجودة في هذا الدلو حتى يجد المفتاح المطابق.

التسلسل المنفصل بسيط وشائع في التفسيرات التعليمية لأنه سهل الفهم.

العنونة المفتوحة (Open Addressing)

العنونة المفتوحة تخزن جميع أزواج المفاتيح والقيم مباشرة داخل المصفوفة الرئيسية. إذا حدث تصادم، يبحث جدول الهاش عن دلو آخر متاح.

على سبيل المثال، إذا كان الفهرس 2 مستخدمًا بالفعل، فقد يحاول الجدول الفهرس 3:

Index 0: empty
Index 1: empty
Index 2: cat → 10
Index 3: bird → 30
Index 4: dog → 20

توجد طرق فحص مختلفة للعنونة المفتوحة:

• الفحص الخطي (Linear probing): جرب الفهرس التالي، ثم التالي، حتى يتم العثور على دلو فارغ.

• الفحص التربيعي (Quadratic probing): استخدم نمط خطوة تربيعي لتقليل التكتل.

• الهاش المزدوج (Double hashing): استخدم دالة هاش ثانية لتحديد خطوة الفحص.

يمكن أن تكون العنونة المفتوحة فعالة من حيث الذاكرة، ولكنها تتطلب معالجة دقيقة للإدخالات المحذوفة وتغيير حجم الجدول.

عامل التحميل (Load Factor)

يقيس عامل التحميل مدى امتلاء جدول الهاش.

load factor = number of stored items / number of buckets

على سبيل المثال، إذا كان الجدول يحتوي على 10 دلاء ويخزن 7 عناصر:

load factor = 7 / 10 = 0.7

يعني عامل التحميل المرتفع أن الجدول أصبح ممتلئًا. وهذا يمكن أن يزيد التصادمات ويقلل الأداء.

العديد من تطبيقات جداول الهاش تقوم بتغيير حجم الجدول عندما يصبح عامل التحميل مرتفعًا جدًا.

إعادة الهاش (Rehashing)

إعادة الهاش هي عملية إنشاء جدول هاش أكبر ونقل جميع العناصر الموجودة إليه.

هذا مطلوب لأنه عندما يصبح الجدول ممتلئًا جدًا، تزداد التصادمات. يمنح الجدول الأكبر دالة الهاش المزيد من مواقع الدلاء لتوزيع المفاتيح.

خلال إعادة الهاش:

1. يتم إنشاء مصفوفة دلاء جديدة أكبر.

2. يتم عمل هاش لكل مفتاح موجود مرة أخرى.

3. يتم إدراج كل زوج من المفتاح والقيمة في الجدول الجديد.

4. يتم استبدال الجدول القديم.

تكلف عملية إعادة الهاش وقتًا، ولكنها لا تحدث في كل عملية. إنها تساعد في الحفاظ على متوسط العمليات قريبًا من O(1).

عمليات جدول الهاش

يدعم جدول الهاش عادةً هذه العمليات:

• insert (إدراج): إضافة زوج من المفتاح والقيمة.

• get (الحصول): استرداد قيمة بواسطة المفتاح.

• update (تحديث): تغيير القيمة المرتبطة بمفتاح.

• delete (حذف): إزالة زوج من المفتاح والقيمة.

• contains (يحتوي): التحقق مما إذا كان المفتاح موجودًا.

• keys (المفاتيح): إرجاع جميع المفاتيح.

• values (القيم): إرجاع جميع القيم.

الميزة الأكثر أهمية هي أن عمليات الإدراج والحصول والحذف والتحقق من الوجود تتم في متوسط زمن O(1).

الرمز الزائف لجدول الهاش (Hash Table Pseudocode)

class HashTable:
    buckets = array of empty lists

    hash(key):
        return numeric hash value

    index(key):
        return hash(key) % bucket count

    set(key, value):
        i = index(key)

        if key exists in buckets[i]:
            update value
        else:
            add key-value pair to buckets[i]

    get(key):
        i = index(key)

        search buckets[i] for key
        if found:
            return value

        return null

    delete(key):
        i = index(key)

        remove key-value pair from buckets[i]

يستخدم هذا الرمز الزائف التسلسل المنفصل لمعالجة التصادمات.

مثال لجدول الهاش في PHP

إليك تطبيق بسيط تعليمي لجدول الهاش في PHP باستخدام التسلسل المنفصل.

<?php

class SimpleHashTable
{
    private array $buckets;

    public function __construct(private int $size = 10)
    {
        $this->buckets = array_fill(0, $this->size, []);
    }

    private function hash(string $key): int
    {
        $hash = 0;

        for ($i = 0; $i < strlen($key); $i++) {
            $hash += ord($key[$i]);
        }

        return $hash;
    }

    private function index(string $key): int
    {
        return $this->hash($key) % $this->size;
    }

    public function set(string $key, mixed $value): void
    {
        $index = $this->index($key);

        foreach ($this->buckets[$index] as &$pair) {
            if ($pair['key'] === $key) {
                $pair['value'] = $value;
                return;
            }
        }

        $this->buckets[$index][] = [
            'key' => $key,
            'value' => $value,
        ];
    }

    public function get(string $key): mixed
    {
        $index = $this->index($key);

        foreach ($this->buckets[$index] as $pair) {
            if ($pair['key'] === $key) {
                return $pair['value'];
            }
        }

        return null;
    }

    public function contains(string $key): bool
    {
        return $this->get($key) !== null;
    }

    public function delete(string $key): bool
    {
        $index = $this->index($key);

        foreach ($this->buckets[$index] as $position => $pair) {
            if ($pair['key'] === $key) {
                unset($this->buckets[$index][$position]);
                $this->buckets[$index] = array_values($this->buckets[$index]);

                return true;
            }
        }

        return false;
    }
}

$table = new SimpleHashTable();

$table->set('name', 'Adnan');
$table->set('role', 'Developer');

echo $table->get('name'); // Adnan
echo PHP_EOL;

var_dump($table->contains('role')); // true

$table->delete('role');

var_dump($table->contains('role')); // false

هذا التطبيق مبسط للتعلم. جداول الهاش على مستوى اللغة الحقيقية تكون أكثر تحسينًا بكثير وتتعامل مع العديد من الحالات الهامشية.

مثال لجدول الهاش في JavaScript

إليك تطبيق بسيط لجدول الهاش في JavaScript باستخدام التسلسل المنفصل.

class SimpleHashTable {
    constructor(size = 10) {
        this.size = size;
        this.buckets = Array.from({ length: size }, () => []);
    }

    hash(key) {
        let hash = 0;

        for (const char of key) {
            hash += char.charCodeAt(0);
        }

        return hash;
    }

    index(key) {
        return this.hash(key) % this.size;
    }

    set(key, value) {
        const index = this.index(key);
        const bucket = this.buckets[index];

        for (const pair of bucket) {
            if (pair.key === key) {
                pair.value = value;
                return;
            }
        }

        bucket.push({ key, value });
    }

    get(key) {
        const index = this.index(key);
        const bucket = this.buckets[index];

        for (const pair of bucket) {
            if (pair.key === key) {
                return pair.value;
            }
        }

        return null;
    }

    contains(key) {
        return this.get(key) !== null;
    }

    delete(key) {
        const index = this.index(key);
        const bucket = this.buckets[index];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i].key === key) {
                bucket.splice(i, 1);
                return true;
            }
        }

        return false;
    }
}

const table = new SimpleHashTable();

table.set('name', 'Adnan');
table.set('role', 'Developer');

console.log(table.get('name'));      // Adnan
console.log(table.contains('role')); // true

table.delete('role');

console.log(table.contains('role')); // false

تتبع نسخة JavaScript نفس المفهوم الذي تتبعه نسخة PHP. يتم تحويل المفاتيح إلى فهارس دلاء، ويتم التعامل مع التصادمات باستخدام مصفوفات داخل الدلاء.

جداول الهاش في اللغات المدمجة

توفر العديد من لغات البرمجة هياكل شبيهة بجداول الهاش مدمجة.

الأمثلة تشمل:

• PHP: المصفوفات الترابطية (Associative arrays).

• JavaScript: الكائنات (Objects)، و Map، و Set.

• Python: dict و set.

• Java: HashMap و HashSet.

• C#: Dictionary و HashSet.

هذه الهياكل المدمجة تكون عادةً محسنة ويجب استخدامها في المشاريع الحقيقية بدلاً من تطبيق جدول هاش يدويًا من الصفر.

مجموعات الهاش (Hash Sets) في هياكل البيانات والخوارزميات (DSA)

مجموعة الهاش (Hash Set) هي هيكل بيانات يخزن قيمًا فريدة. يتم بناؤها عادةً فوق جدول هاش، لكنها تخزن المفاتيح فقط، وليس أزواج المفاتيح والقيم.

الغرض الرئيسي من مجموعة الهاش هو الإجابة على هذا السؤال بسرعة:

Does this value exist?

على سبيل المثال:

Hash Set:
{apple, banana, orange}

إذا حاولنا إضافة banana مرة أخرى، فإن المجموعة لا تخزن تكرارًا.

{apple, banana, orange}

هذا يجعل مجموعات الهاش مفيدة للتحقق من التفرد والعضوية.

عمليات مجموعة الهاش

تدعم مجموعة الهاش عادةً هذه العمليات:

• add (إضافة): إضافة قيمة إذا لم تكن موجودة بالفعل.

• has (يحتوي): التحقق مما إذا كانت القيمة موجودة.

• delete (حذف): إزالة قيمة.

• size (الحجم): إرجاع عدد القيم الفريدة.

• clear (مسح): إزالة جميع القيم.

متوسط التعقيد الزمني لعمليات الإضافة، والتحقق من الوجود، والحذف هو O(1).

تشغيل يدوي لمجموعة الهاش

دعنا نُجري هذه العمليات على مجموعة الهاش يدويًا:

add(10)
add(20)
add(10)
has(20)
delete(10)
has(10)

ابدأ بمجموعة فارغة:

{}

بعد add(10):

{10}

بعد add(20):

{10, 20}

بعد add(10) مرة أخرى:

{10, 20}

القيمة 10 لا يتم تكرارها.

الآن، has(20) يعيد:

true

بعد delete(10):

{20}

الآن، has(10) يعيد:

false

يوضح هذا التشغيل اليدوي السلوك الرئيسي لمجموعة الهاش: تخزين فريد وتحقق سريع من العضوية.

مثال لمجموعة الهاش في JavaScript

توفر JavaScript كائن Set مدمجًا.

const visitedUsers = new Set();

visitedUsers.add(101);
visitedUsers.add(102);
visitedUsers.add(101);

console.log(visitedUsers.has(101)); // true
console.log(visitedUsers.size);     // 2

visitedUsers.delete(101);

console.log(visitedUsers.has(101)); // false

تتم إضافة القيمة 101 مرة واحدة فقط لأن المجموعات تخزن قيمًا فريدة.

مثال لمجموعة الهاش في PHP

لا تملك PHP نوع Set مخصصًا مدمجًا مثل JavaScript، ولكن يمكن استخدام المصفوفات الترابطية لمحاكاة مجموعة الهاش.

<?php

$visitedUsers = [];

$visitedUsers[101] = true;
$visitedUsers[102] = true;
$visitedUsers[101] = true;

var_dump(isset($visitedUsers[101])); // true
echo count($visitedUsers);           // 2

unset($visitedUsers[101]);

var_dump(isset($visitedUsers[101])); // false

تمثل المفاتيح قيم المجموعة. وبما أن مفاتيح المصفوفات فريدة، يتم تجنب التكرارات بشكل طبيعي.

حالات الاستخدام الشائعة لمجموعات الهاش

مجموعات الهاش مفيدة عندما يكون التفرد أو التحقق من العضوية مهمًا.

حالات الاستخدام الشائعة تشمل:

• إزالة القيم المكررة.

• التحقق مما إذا كان عنصر ما قد تمت زيارته بالفعل.

• اكتشاف أسماء مستخدمين أو رسائل بريد إلكتروني مكررة.

• تتبع العقد التي تمت زيارتها في خوارزميات الرسوم البيانية (graph algorithms).

• التحقق مما إذا كانت القيمة موجودة في مجموعة.

• إيجاد تقاطعات بين المجموعات.

على سبيل المثال، في اجتياز الرسوم البيانية، يمكن لمجموعة الهاش تخزين العقد التي تمت زيارتها حتى لا تعالج الخوارزمية نفس العقدة مرتين.

مثال: إزالة التكرارات باستخدام مجموعة الهاش

لنفترض أن لدينا هذه المصفوفة:

[3, 5, 3, 2, 5, 1]

باستخدام مجموعة الهاش، يمكننا الاحتفاظ بالقيم الفريدة فقط:

{3, 5, 2, 1}

في JavaScript:

const numbers = [3, 5, 3, 2, 5, 1];

const uniqueNumbers = [...new Set(numbers)];

console.log(uniqueNumbers);

سيكون الإخراج:

[3, 5, 2, 1]

قد يتبع الترتيب ترتيب الإدراج في Set في JavaScript، ولكن الفكرة الرئيسية هي التفرد.

خرائط الهاش (Hash Maps) في هياكل البيانات والخوارزميات (DSA)

خريطة الهاش (Hash Map) هي هيكل بيانات يخزن أزواجًا من المفاتيح والقيم. وعادة ما يتم بناؤها أيضًا فوق جدول هاش.

الغرض الرئيسي من خريطة الهاش هو الإجابة على هذا السؤال بسرعة:

What value belongs to this key?

على سبيل المثال:

userId → userName

101 → Ali
102 → Sara
103 → Omar

إذا عرفنا المفتاح 102، يمكننا استرداد القيمة "Sara" بسرعة.

عمليات خريطة الهاش

تدعم خريطة الهاش عادةً هذه العمليات:

• set (تعيين): إضافة أو تحديث زوج من المفتاح والقيمة.

• get (الحصول): استرداد القيمة لمفتاح.

• has (يحتوي): التحقق مما إذا كان المفتاح موجودًا.

• delete (حذف): إزالة زوج من المفتاح والقيمة.

• keys (المفاتيح): إرجاع جميع المفاتيح.

• values (القيم): إرجاع جميع القيم.

• entries (المدخلات): إرجاع جميع أزواج المفاتيح والقيم.

متوسط التعقيد الزمني لعمليات التعيين، والحصول، والتحقق من الوجود، والحذف هو O(1).

تشغيل يدوي لخريطة الهاش

دعنا نُجري هذه العمليات على خريطة الهاش يدويًا:

set('name', 'Ali')
set('age', 25)
get('name')
set('age', 26)
delete('name')
has('name')

ابدأ بخريطة فارغة:

{}

بعد set('name', 'Ali'):

{
  name: Ali
}

بعد set('age', 25):

{
  name: Ali,
  age: 25
}

get('name') تعيد:

Ali

بعد set('age', 26)، يتم تحديث القيمة:

{
  name: Ali,
  age: 26
}

بعد delete('name'):

{
  age: 26
}

has('name') تعيد:

false

يوضح هذا التشغيل اليدوي سلوك المفتاح والقيمة لخريطة الهاش.

مثال لخريطة الهاش في JavaScript

توفر JavaScript كائن Map مدمجًا.

const userMap = new Map();

userMap.set(101, 'Ali');
userMap.set(102, 'Sara');
userMap.set(103, 'Omar');

console.log(userMap.get(102)); // Sara
console.log(userMap.has(101)); // true

userMap.set(102, 'Sarah');

console.log(userMap.get(102)); // Sarah

userMap.delete(101);

console.log(userMap.has(101)); // false

تخزن Map القيم بواسطة المفتاح وتسمح بالبحث السريع.

مثال لخريطة الهاش في PHP

تُستخدم المصفوفات الترابطية في PHP عادةً كخرائط هاش.

<?php

$userMap = [];

$userMap[101] = 'Ali';
$userMap[102] = 'Sara';
$userMap[103] = 'Omar';

echo $userMap[102]; // Sara
echo PHP_EOL;

var_dump(isset($userMap[101])); // true

$userMap[102] = 'Sarah';

echo $userMap[102]; // Sarah
echo PHP_EOL;

unset($userMap[101]);

var_dump(isset($userMap[101])); // false

هذه إحدى أكثر الطرق شيوعًا التي يستخدم بها مطورو PHP سلوك خريطة الهاش في المشاريع الحقيقية.

جدول الهاش مقابل مجموعة الهاش مقابل خريطة الهاش

جداول الهاش ومجموعات الهاش وخرائط الهاش مترابطة بشكل وثيق، لكنها ليست نفس المفهوم تمامًا.

جدول الهاش هو فكرة هيكل البيانات الأساسية. يستخدم دالة هاش، ودلاء، ومعالجة التصادمات.

تخزن مجموعة الهاش قيمًا فريدة. داخليًا، يمكنها استخدام جدول هاش حيث تعمل القيم كمفاتيح.

تخزن خريطة الهاش أزواج المفاتيح والقيم. داخليًا، تستخدم المفاتيح لحساب مكان تخزين القيم.

Hash Table: underlying mechanism
Hash Set:   stores unique values
Hash Map:   stores key-value pairs

بشكل مبسط:

• استخدم مجموعة الهاش عندما تهتم فقط بما إذا كانت القيمة موجودة.

• استخدم خريطة الهاش عندما تحتاج إلى تخزين واسترداد القيم بواسطة المفتاح.

• ادرس جداول الهاش لفهم كيفية عمل الهيكلين داخليًا.

التعقيد الزمني لجداول الهاش

يصف التعقيد الزمني (Time complexity) كيف ينمو وقت تشغيل العمليات مع زيادة حجم الإدخال.

بالنسبة لجداول الهاش، فإن التعقيدات المتوسطة الشائعة هي:

• الإدراج (Insert): متوسط O(1)

• البحث (Search): متوسط O(1)

• الحذف (Delete): متوسط O(1)

• التحديث (Update): متوسط O(1)

• التجول (Traversal): O(n)

أداء O(1) في المتوسط هو السبب الرئيسي وراء فائدة جداول الهاش الكبيرة.

التعقيد الزمني في أسوأ الحالات

أسوأ حالة لعمليات جدول الهاش يمكن أن تكون O(n).

يحدث هذا عندما تتصادم العديد من المفاتيح في نفس الدلو. إذا تم تخزين جميع المفاتيح في دلو واحد، فقد يحتاج جدول الهاش إلى مسح العديد من العناصر داخل هذا الدلو.

Index 0: empty
Index 1: empty
Index 2: [key1] → [key2] → [key3] → [key4] → [key5]
Index 3: empty

إذا كان المفتاح المستهدف في نهاية السلسلة، يمكن أن يستغرق البحث زمنًا قدره O(n).

تساعد دوال الهاش الجيدة، وتغيير الحجم، ومعالجة التصادمات على تجنب هذا الموقف عمليًا.

التعقيد المكاني لجداول الهاش

عادة ما يكون التعقيد المكاني لجدول الهاش هو O(n)، حيث n هو عدد العناصر المخزنة.

ومع ذلك، تقوم جداول الهاش أيضًا بتخصيص دلاء، وبعض الدلاء قد تكون فارغة. هذا يعني أنها قد تستخدم ذاكرة أكبر من القائمة البسيطة.

تكلفة الذاكرة تشمل:

• مصفوفة الدلاء.

• المفاتيح المخزنة.

• القيم المخزنة.

• مراجع إضافية أو هياكل سلاسل للتصادمات.

تضحي جداول الهاش بذاكرة إضافية مقابل بحث أسرع.

لماذا جداول الهاش متوسطها O(1)

متوسط أداء جداول الهاش هو O(1) لأن دالة الهاش تحسب مباشرة مكان تخزين المفتاح.

بدلاً من التحقق من العناصر واحدًا تلو الآخر، يقوم الجدول بما يلي:

key → hash → index

إذا كانت التصادمات قليلة، فإن الدلو يحتوي على عنصر واحد أو عدد قليل من العناصر فقط. هذا يجعل البحث سريعًا جدًا.

ومع ذلك، لا يُضمن O(1) في كل موقف. يعتمد ذلك على دالة هاش جيدة، وعامل تحميل معقول، ومعالجة فعالة للتصادمات.

مثال عملي: عد تكرار الكلمات

خرائط الهاش ممتازة لعد التكرارات.

لنفترض أن لدينا هذه القائمة من الكلمات:

apple, banana, apple, orange, banana, apple

يمكننا استخدام خريطة هاش لعد مرات الظهور:

apple  → 3
banana → 2
orange → 1

في JavaScript:

const words = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple'];
const frequency = new Map();

for (const word of words) {
    const currentCount = frequency.get(word) || 0;
    frequency.set(word, currentCount + 1);
}

console.log(frequency);

هذه حالة استخدام كلاسيكية لخريطة الهاش لأن كل كلمة يمكن تحديثها بسرعة.

مثال عملي: اكتشاف التكرارات

مجموعات الهاش ممتازة لاكتشاف التكرارات.

لنفترض أن لدينا هذه المصفوفة:

[4, 2, 7, 4, 9]

يمكننا مسح المصفوفة وإضافة القيم إلى مجموعة. إذا رأينا قيمة موجودة بالفعل في المجموعة، فقد وجدنا تكرارًا.

const numbers = [4, 2, 7, 4, 9];
const seen = new Set();

for (const number of numbers) {
    if (seen.has(number)) {
        console.log('Duplicate found:', number);
        break;
    }

    seen.add(number);
}

هذا يتجنب الحلقات المتداخلة ويحسن الأداء من O(n²) إلى متوسط O(n).

مثال عملي: مشكلة المجموع الثنائي (Two Sum Problem)

مشكلة المجموع الثنائي (Two Sum problem) هي مثال شهير حيث تعمل خريطة الهاش على تحسين الأداء.

بمعطاة مصفوفة وهدف، أوجد رقمين يضافان ليساويا الهدف.

numbers = [2, 7, 11, 15]
target = 9

الإجابة هي 2 و 7.

باستخدام خريطة الهاش، نقوم بتخزين الأرقام التي رأيناها بالفعل:

function twoSum(numbers, target) {
    const seen = new Map();

    for (let i = 0; i < numbers.length; i++) {
        const complement = target - numbers[i];

        if (seen.has(complement)) {
            return [seen.get(complement), i];
        }

        seen.set(numbers[i], i);
    }

    return [];
}

console.log(twoSum([2, 7, 11, 15], 9));

سيكون الإخراج:

[0, 1]

هذا الحل هو متوسط O(n)، لأن كل بحث في خريطة الهاش هو متوسط O(1).

متى يجب على المطورين استخدام مجموعة الهاش؟

يجب على المطورين استخدام مجموعة الهاش عندما يحتاجون إلى التفرد أو التحقق السريع من العضوية.

تكون مجموعات الهاش مفيدة عندما:

• يجب إزالة القيم المكررة.

• يجب تتبع العناصر التي تمت زيارتها.

• فحوصات العضوية متكررة.

• القيم فقط هي المهمة، وليس علاقات المفتاح والقيمة.

• يتطلب اجتياز الرسوم البيانية مجموعة من العقد التي تمت زيارتها.

السؤال الرئيسي هو: هل نحتاج فقط إلى معرفة ما إذا كانت القيمة موجودة؟ إذا كانت الإجابة نعم، فقد تكون مجموعة الهاش هي الخيار الصحيح.

متى يجب على المطورين استخدام خريطة الهاش؟

يجب على المطورين استخدام خريطة الهاش عندما يحتاجون إلى ربط المفاتيح بالقيم.

تكون خرائط الهاش مفيدة عندما:

• تحتاج معرفات المستخدمين (User IDs) للربط ببيانات المستخدم.

• تحتاج رموز المنتجات للربط بكائنات المنتجات.

• تحتاج الكلمات للربط بالعدد.

• تحتاج مفاتيح التخزين المؤقت للربط بالنتائج المخزنة مؤقتًا.

• تحتاج أسماء التكوين (Configuration names) للربط بالقيم.

• مطلوب بحث سريع بواسطة المفتاح.

السؤال الرئيسي هو: هل نحتاج إلى استرداد قيمة باستخدام مفتاح؟ إذا كانت الإجابة نعم، فإن خريطة الهاش عادة ما تكون خيارًا قويًا.

متى لا يجب استخدام جداول الهاش

جداول الهاش قوية، لكنها ليست دائمًا الخيار الأفضل.

قد يتجنب المطورون جداول الهاش عندما:

• يكون الترتيب المصنف مطلوبًا.

• تكون استعلامات النطاق (Range queries) مطلوبة.

• يجب أن يكون استخدام الذاكرة ضئيلاً.

• المفاتيح صعبة التحويل إلى هاش بشكل صحيح.

• مطلوب ترتيب تكرار يمكن التنبؤ به ولا تضمنه اللغة.

• تكون ضمانات أسوأ الحالات أهم من الأداء المتوسط.

للبيانات المرتبة، قد تكون الأشجار أو المصفوفات المرتبة أفضل. لاستعلامات النطاق، قد تكون الأشجار المتوازنة أو فهارس قواعد البيانات أكثر ملاءمة.

جداول الهاش مقابل المصفوفات

المصفوفات وجداول الهاش تحل مشاكل مختلفة.

المصفوفات جيدة عندما يتم الوصول إلى العناصر بواسطة فهرس رقمي.

array[0]
array[1]
array[2]

جداول الهاش جيدة عندما يتم الوصول إلى القيم بواسطة المفتاح.

users['email@example.com']
products['SKU-100']

الاختلافات الرئيسية تشمل:

• توفر المصفوفات وصولاً سريعًا بواسطة الفهرس.

• توفر جداول الهاش وصولاً سريعًا بواسطة المفتاح.

• تحافظ المصفوفات على ترتيب الفهرس الطبيعي.

• تنظم جداول الهاش البيانات بواسطة فهارس الهاش.

• المصفوفات بسيطة وفعالة من حيث الذاكرة.

• تستخدم جداول الهاش ذاكرة إضافية للبحث السريع.

إذا كانت البيانات مفهرسة بشكل طبيعي حسب الموضع، استخدم مصفوفة. إذا تم الوصول إلى البيانات بواسطة المفتاح، استخدم خريطة هاش أو جدول هاش.

جداول الهاش مقابل البحث الثنائي

يعمل البحث الثنائي (Binary Search) على المصفوفات المرتبة ولديه تعقيد زمني O(log n). بينما توفر جداول الهاش عادةً بحثًا بمتوسط O(1).

ومع ذلك، يحافظ البحث الثنائي على ترتيب البيانات، بينما لا تدعم جداول الهاش الترتيب المصنف بشكل طبيعي.

الاختلافات الرئيسية تشمل:

• يتطلب البحث الثنائي بيانات مرتبة.

• لا تتطلب جداول الهاش بيانات مرتبة.

• بحث البحث الثنائي هو O(log n).

• بحث جدول الهاش هو متوسط O(1).

• يدعم البحث الثنائي الاستدلال المرتب.

• جداول الهاش أفضل للبحث المباشر بالمفتاح.

يعتمد الاختيار الصحيح على ما إذا كان الترتيب مهمًا.

أخطاء شائعة عند تعلم جداول الهاش

غالبًا ما يعتقد المبتدئون أن جداول الهاش هي دائمًا O(1)، لكن هذا هو سلوك الحالة المتوسطة فقط.

الأخطاء الشائعة تشمل:

• تجاهل التصادمات.

• الاعتقاد بأن التصادمات مستحيلة.

• استخدام دالة هاش سيئة.

• نسيان التعامل مع المفاتيح المكررة.

• الخلط بين مجموعة الهاش وخريطة الهاش.

• افتراض أن جداول الهاش تحافظ دائمًا على الترتيب.

• تجاهل النفقات العامة للذاكرة.

• استخدام جداول الهاش عندما يكون الترتيب المصنف مطلوبًا.

النقطة الأهم هي أن جداول الهاش قوية بسبب دوال الهاش الجيدة ومعالجة التصادمات.

قائمة تحقق عملية لفهم جداول الهاش

قبل الانتقال إلى مواضيع أكثر تقدمًا، يجب أن يكون المطورون قادرين على الإجابة على هذه الأسئلة:

• ما هو المفتاح؟

• ما هي القيمة؟

• ماذا تفعل دالة الهاش؟

• كيف يتم تحويل قيمة الهاش إلى فهرس؟

• ما هو الدلو؟

• ما هو التصادم؟

• كيف يعمل التسلسل المنفصل؟

• ما هي العنونة المفتوحة؟

• ما هو عامل التحميل؟

• لماذا العمليات متوسطها O(1)؟

• لماذا يمكن أن تصبح أسوأ الحالات O(n)؟

• ما الفرق بين مجموعة الهاش وخريطة الهاش؟

إذا كانت هذه الأسئلة واضحة، فإن المطور يفهم جداول الهاش بعمق بدلاً من مجرد حفظ المصطلحات.

مزايا جداول الهاش

تتمتع جداول الهاش بالعديد من المزايا الهامة.

• توفر إدراجًا بمتوسط O(1).

• توفر بحثًا بمتوسط O(1).

• توفر حذفًا بمتوسط O(1).

• ممتازة لتخزين المفتاح والقيمة.

• مفيدة لفحوصات التفرد.

• عملية للتخزين المؤقت (caching) والفهرسة.

• تحسن العديد من الخوارزميات من O(n²) إلى O(n).

هذه المزايا تجعل جداول الهاش واحدة من أكثر هياكل البيانات فائدة في تطوير البرمجيات.

عيوب جداول الهاش

جداول الهاش لها أيضًا قيود.

• تستخدم ذاكرة إضافية.

• لا تحافظ بشكل طبيعي على الترتيب المصنف.

• يمكن أن تصبح عمليات أسوأ الحالات O(n).

• يعتمد الأداء على دالة الهاش.

• تضيف معالجة التصادمات تعقيدًا.

• يمكن أن تكون إعادة الهاش مكلفة عند حدوثها.

هذه القيود لا تجعل جداول الهاش سيئة. إنها ببساطة توضح متى قد يكون هيكل بيانات آخر أكثر ملاءمة.

جداول الهاش في مشاريع البرمجيات الحقيقية

تظهر جداول الهاش في كل مكان في مشاريع البرمجيات الحقيقية.

الاستخدامات الشائعة في العالم الحقيقي تشمل:

• البحث عن المستخدمين بواسطة المعرف (ID) أو البريد الإلكتروني.

• البحث عن المنتجات بواسطة رمز SKU.

• تخزين ذاكرة التخزين المؤقت (Cache storage) بواسطة المفتاح.

• تخزين الجلسات (Session storage).

• عد التكرارات.

• إزالة التكرارات.

• تتبع العقد التي تمت زيارتها.

• مفاهيم الفهرسة في قواعد البيانات.

• جداول الرموز في المترجمات (Compiler symbol tables).

• جداول التوجيه وخرائط التكوين.

بالنسبة لمطوري الواجهة الخلفية (backend developers)، تُعد خرائط الهاش ومجموعات الهاش مهمة بشكل خاص لأنها تظهر في معالجة البيانات، والتحقق من الصحة، والتخزين المؤقت، ومنطق واجهات برمجة التطبيقات (API logic).

الخاتمة

جدول الهاش هو هيكل بيانات يستخدم دالة هاش لربط المفاتيح بفهارس مصفوفة داخلية. يسمح بالإدراج والبحث والتحديث والحذف السريع في متوسط زمن O(1).

جداول الهاش هي الأساس وراء مجموعات الهاش وخرائط الهاش. تخزن مجموعة الهاش قيمًا فريدة ومفيدة للتحقق من العضوية. تخزن خريطة الهاش أزواج المفاتيح والقيم ومفيدة للبحث السريع بواسطة المفتاح.

أهم المفاهيم الداخلية هي دوال الهاش، الدلاء، التصادمات، معالجة التصادمات، عامل التحميل، وإعادة الهاش. تشرح هذه المفاهيم سبب سرعة جداول الهاش في المتوسط وسبب إمكانية أن يصبح أداؤها في أسوأ الحالات O(n).

ليست جداول الهاش دائمًا الحل الأفضل. فهي تستخدم ذاكرة إضافية ولا تحافظ بشكل طبيعي على الترتيب المصنف. ومع ذلك، عندما تكون هناك حاجة إلى الوصول السريع المستند إلى المفتاح أو التحقق من التفرد، فهي واحدة من أقوى هياكل البيانات المتاحة.

بالنسبة للمطورين الذين يتعلمون هياكل البيانات والخوارزميات، فإن جداول الهاش ضرورية. إنها تبني الأساس لحل العديد من المشاكل العملية بكفاءة، بما في ذلك اكتشاف التكرارات، وعد التكرارات، والتخزين المؤقت، والفهرسة، وجداول البحث، وتصميم الخوارزميات المحسن.