مقدمة

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

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

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

تنفيذ خريطة تجزئة بسيطة في جافا سكريبت

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

التعامل مع الاصطدامات

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

تسلسل منفصل : في تسلسل منفصل، تحتوي كل فتحة في مصفوفة جدول التجزئة على قائمة مرتبطة (أو بنية بيانات أخرى يمكنها الاحتفاظ بعناصر متعددة). عند حدوث تصادم، تتم إضافة زوج المفتاح والقيمة الجديد إلى نهاية القائمة المرتبطة في الفهرس المقابل.

إليك تنفيذ بسيط لخريطة التجزئة باستخدام تسلسل منفصل في JavaScript:

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



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

إليك تنفيذ بسيط لخريطة التجزئة باستخدام الفحص الخطي في JavaScript:


class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index   1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index   1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



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