كيفية تنفيذ جدول تجزئة بسيط في JavaScript

كم هي جميلة {}؟

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

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

المشكلة

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

هل تساءلت يومًا كيف تعمل؟ كيف هم بهذه السرعة اللعينة؟

حسنًا ، دعنا نقول أن JavaScript لم يكن لديه {}أو new Map()، ودعنا ننفذ منطقتنا DumbMap!

ملاحظة حول التعقيد

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

يقيس التعقيد عدد الخطوات التي تتطلبها وظيفتنا - فكلما قل عدد الخطوات ، زادت سرعة التنفيذ (المعروف أيضًا باسم "وقت التشغيل").

دعنا نلقي نظرة على المقتطف التالي:

function fn(n, m) { return n * m}

التعقيد الحسابي (من الآن "التعقيد" ببساطة) fnهو O(1)، مما يعني أنه ثابت (يمكنك أن تقرأ على O(1)أنه " التكلفة واحدة "): بغض النظر عن الحجج التي تمررها ، يجب على النظام الأساسي الذي يقوم بتشغيل هذا الرمز القيام بعملية واحدة فقط (اضرب nفي m). مرة أخرى ، نظرًا لأنها عملية واحدة ، يشار إلى التكلفة باسم O(1).

يقاس التعقيد بافتراض أن الحجج الخاصة بوظيفتك قد تحتوي على قيم كبيرة جدًا. لنلقِ نظرة على هذا المثال:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

هل تعتقد أن تعقيدها O(3)صحيح؟

مرة أخرى ، نظرًا لأن التعقيد يقاس في سياق الحجج الكبيرة جدًا ، فإننا نميل إلى "إسقاط" الثوابت والنظر O(3)في الأمر نفسه O(1). لذا ، حتى في هذه الحالة ، يمكننا القول أن تعقيد fnهو O(1). ومهما كانت قيمة nو mهي، وكنت دائما في نهاية المطاف القيام ثلاث عمليات - التي، مرة أخرى، هو تكلفة ثابتة (لذلك O(1)).

الآن هذا المثال مختلف قليلاً:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

كما ترى ، نحن نكرر عدة مرات قيمة n، والتي يمكن أن تكون بالملايين. في هذه الحالة ، نحدد مدى تعقيد هذه الوظيفة O(n)، حيث ستحتاج إلى إجراء العديد من العمليات مثل قيمة إحدى وسيطاتك.

أمثلة أخرى؟

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

هذه الأمثلة تتكرر 2 * nمرات ، مما يعني أن التعقيد يجب أن يكون O(2n). نظرًا لأننا ذكرنا أنه يتم "تجاهل" الثوابت عند حساب مدى تعقيد دالة ، يُصنف هذا المثال أيضًا على أنه O(n).

مرة اخرى؟

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

نحن هنا نعيد nالحلقات مرة أخرى داخل الحلقة الرئيسية ، مما يعني أن التعقيد "مربّع" ( n * n): إذا كانت n2 ، فسنعمل s.push(m)4 مرات ، إذا 3 سنقوم بتشغيلها 9 مرات ، وهكذا.

في هذه الحالة ، تتم الإشارة إلى تعقيد الوظيفة O(n²).

مثال أخير؟

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

في هذه الحالة ، ليس لدينا حلقات متداخلة ، لكننا نحلل مرتين على وسيطتين مختلفتين: يتم تعريف التعقيد على أنه O(n+m). اضحة وضوح الشمس.

الآن بعد أن حصلت للتو على مقدمة موجزة (أو تنشيط) حول التعقيد ، من السهل جدًا أن تفهم أن الوظيفة ذات التعقيد O(1)ستؤدي بشكل أفضل بكثير من أداء وظيفة بها O(n).

جداول التجزئة لها O(1)تعقيد: من منظور الشخص العادي ، فهي فائقة السرعة . هيا لنذهب.

(أنا مستلقٍ على طاولات التجزئة دائمًا ما أعاني من O(1)تعقيد ، ولكن فقط اقرأ ؛))

دعونا نبني جدول تجزئة (غبي)

يحتوي جدول التجزئة الخاص بنا على طريقتين بسيطتين - set(x, y)و get(x). لنبدأ في كتابة بعض التعليمات البرمجية:

ودعنا ننفذ طريقة بسيطة للغاية وغير فعالة لتخزين أزواج القيمة الرئيسية هذه واستعادتها لاحقًا. نبدأ أولاً بتخزينها في مصفوفة داخلية (تذكر ، لا يمكننا استخدامها {}لأننا ننفذ {}- ذهل العقل!):

إذن الأمر يتعلق ببساطة بالحصول على العنصر الصحيح من القائمة:

مثالنا الكامل:

لدينا DumbMap مذهل! إنها تعمل مباشرة خارج الصندوق ، ولكن كيف ستعمل عندما نضيف كمية كبيرة من أزواج القيمة الرئيسية؟

لنجرب معيارًا بسيطًا. سنحاول أولاً العثور على عنصر غير موجود في جدول تجزئة يحتوي على عدد قليل جدًا من العناصر ، ثم نجرب نفس الشيء في جدول يحتوي على كمية كبيرة من العناصر:

نتائج؟ ليس مشجعًا:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

في تطبيقنا ، نحتاج إلى المرور عبر جميع العناصر الموجودة بالداخل this.listللعثور على عنصر به المفتاح المطابق. التكلفة O(n)، وهي مروعة للغاية.

اجعله اسرع)

نحتاج إلى إيجاد طريقة لتجنب التكرار في قائمتنا: حان الوقت لإعادة التجزئة إلى جدول التجزئة .

هل تساءلت يومًا عن سبب تسمية بنية البيانات هذه بجدول التجزئة ؟ هذا بسبب استخدام وظيفة التجزئة على المفاتيح التي تحددها وتحصل عليها. سنستخدم هذه الوظيفة لتحويل مفتاحنا إلى عدد صحيح i، وتخزين قيمتنا في فهرس iقائمتنا الداخلية. نظرًا لأن الوصول إلى عنصر ، من خلال فهرسه ، من قائمة له تكلفة ثابتة ( O(1)) ، فإن تكلفة جدول التجزئة هي أيضًا O(1).

لنجرب هذا:

نحن هنا نستخدم وحدة تجزئة السلسلة ، والتي تقوم ببساطة بتحويل سلسلة إلى تجزئة رقمية. نستخدمه لتخزين وجلب العناصر في فهرس hash(key)قائمتنا. نتائج؟

with lots of records in the map: 0.013ms

W - O - W. هذا ما أتحدث عنه!

لا يتعين علينا إجراء تكرار عبر جميع العناصر الموجودة في القائمة ، كما أن استرداد العناصر منها DumbMapسريع للغاية!

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

تكلفة انتقاء دالة التجزئة الصحيحة

بالطبع ، يعد اختيار وظيفة التجزئة السريعة أمرًا مهمًا للغاية. إذا تم hash(key)تشغيلنا في بضع ثوانٍ ، فستكون وظيفتنا بطيئة جدًا بغض النظر عن مدى تعقيدها.

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

مشوش؟ دعونا نلقي نظرة فاحصة على الاصطدامات.

الاصطدامات

قد تعتقد " آه ، وظيفة التجزئة الجيدة لا تولد تصادمات! ": حسنًا ، عد إلى العالم الحقيقي وفكر مرة أخرى. تمكنت Google من إنتاج تصادمات لخوارزمية التجزئة SHA-1 ، وهي مجرد مسألة وقت ، أو قوة حسابية ، قبل أن تتصدع وظيفة التجزئة وتعيد نفس التجزئة لمدخلتين مختلفتين. افترض دائمًا أن وظيفة التجزئة الخاصة بك تولد تصادمات ، وتنفيذ الدفاع الصحيح ضد مثل هذه الحالات.

مثال على ذلك ، دعنا نحاول استخدام hash()وظيفة تولد الكثير من التصادمات:

تستخدم هذه الوظيفة مصفوفة من 10 عناصر لتخزين القيم ، مما يعني أنه من المحتمل استبدال العناصر - وهو خطأ سيئ في DumbMap:

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

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

دعنا نقيس هذا باستخدام وظيفتنا الخاصة hash()التي تنشئ فهارس من 1 إلى 10:

with lots of records in the map: 11.919ms

وباستخدام دالة التجزئة من string-hash، والتي تنشئ فهارس عشوائية:

with lots of records in the map: 0.014ms

قف! هناك تكلفة انتقاء دالة التجزئة الصحيحة - بالسرعة الكافية بحيث لا تبطئ التنفيذ من تلقاء نفسها ، وجيدة بما يكفي بحيث لا تنتج الكثير من الاصطدامات.

عموما O (1)

تذكر كلامي؟

Hashtables لها O(1)تعقيد

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

وظيفة تجزئة مثل:

function hash(key) { return 0}

قد يعني أن جدول التجزئة لدينا به تعقيد O(n).

هذا هو السبب في أن التعقيد الحسابي ، بشكل عام ، له ثلاثة مقاييس: سيناريوهات أفضل ومتوسط ​​وأسوأ حالة. تحتوي Hashtables على O(1)تعقيد في أفضل السيناريوهات ومتوسط ​​الحالة ، ولكنها تقع O(n)في أسوأ السيناريوهات.

تذكر: وظيفة التجزئة الجيدة هي المفتاح لجدول تجزئة فعال - لا أكثر ولا أقل.

المزيد عن التصادمات ...

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

أسلوب شائع آخر هو العنونة المفتوحة

  • في كل فهرس من قائمتنا ، نقوم بتخزين زوج واحد فقط ذو قيمة رئيسية
  • عند محاولة تخزين زوج في الفهرس x، إذا كان هناك بالفعل زوج ذو قيمة رئيسية ، فحاول تخزين زوجنا الجديد عندx + 1
  • إذا x + 1تم تناوله ، فحاول x + 2وما إلى ذلك ...
  • عند استرداد عنصر ، قم بتجزئة المفتاح ومعرفة ما إذا كان العنصر الموجود في هذا الموضع ( x) يطابق مفتاحنا
  • إذا لم يكن كذلك ، فحاول الوصول إلى العنصر في الموضع x + 1
  • اشطفها وكررها حتى تصل إلى نهاية القائمة ، أو عندما تجد فهرسًا فارغًا - هذا يعني أن عنصرنا ليس في جدول التجزئة

ذكية وبسيطة وأنيقة وعادة ما تكون فعالة للغاية!

أسئلة وأجوبة (أو TL ؛ DR)

هل يقوم جدول التجزئة بتجزئة القيم التي نقوم بتخزينها؟

لا ، يتم تجزئة المفاتيح بحيث يمكن تحويلها إلى عدد صحيح i، ويتم تخزين كل من المفاتيح والقيم في موضع iفي قائمة.

هل تولد وظائف التجزئة التي تستخدمها جداول التجزئة تصادمات؟

بالتأكيد - لذلك يتم تنفيذ جداول التجزئة باستخدام استراتيجيات دفاعية لتجنب الأخطاء السيئة.

هل تستخدم جداول التجزئة قائمة أو قائمة مرتبطة داخليًا؟

هذا يعتمد ، كلاهما يمكن أن يعمل. في أمثلةنا ، نستخدم مصفوفة JavaScript ( []) التي يمكن تغيير حجمها ديناميكيًا:

> a = []
> a[3] = 1
> a[ , 1 ]

لماذا اخترت JavaScript للأمثلة؟ صفائف JS هي جداول تجزئة!

فمثلا:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

أعرف ، لعنة جافا سكريبت.

JavaScript هي لغة "عالمية" وربما أسهل لغة يمكن فهمها عند النظر إلى بعض نماذج التعليمات البرمجية. قد لا تكون JS هي أفضل لغة ، لكنني آمل أن تكون هذه الأمثلة واضحة بما فيه الكفاية.

هل المثال الخاص بك هو تطبيق جيد لجدول التجزئة؟ هل هو حقا بهذه البساطة؟

لا إطلاقا.

ألق نظرة على "تنفيذ جدول تجزئة في JavaScript" بواسطة Matt Zeunert ، حيث سيعطيك المزيد من السياق. هناك الكثير لتتعلمه ، لذا أقترح عليك أيضًا التحقق من:

  • دورة Paul Kube حول طاولات التجزئة
  • تنفيذ جدول التجزئة الخاص بنا مع تسلسل منفصل في Java
  • الخوارزميات ، الإصدار الرابع - جداول التجزئة
  • تصميم جدول تجزئة سريع

فى النهاية…

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

آمل أن تكون قد استمتعت بهذا المقال ، ولا تتردد في مشاركة ملاحظاتك معي.

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

وداعا!