😿 🔻 👂🏼 ما تحتاج إلى معرفته عن المجموعات القائمة على التجزئة 💃🏾 👋🏻 👩‍🏫

تحية للجميع. على اتصال فلاديسلاف رودين. حاليًا ، أنا رئيس دورة High Load Architect في OTUS ، وأدرس أيضًا دورات في هندسة البرمجيات.

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

المقدمة

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

صياغة المشكلة

دعنا نضع هدفًا لإنشاء بنية بيانات تتيح لك:

يحتوي على (عنصر عنصر) تحقق مما إذا كان عنصر فيه أم لا ، لـ O (1)
add (element element) add element in O (1)
حذف (عنصر) حذف عنصر في O (1)

مجموعة مصفوفة

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

التحقق من التوفر

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

مضيفا

إذا كنا بحاجة إلى إضافة عنصر في أي مكان ، فسنحتاج أولاً إلى العثور على خلية فارغة ، ثم كتابة العنصر إليها. وبالتالي ، نقوم مرة أخرى بإجراء بحث خطي والحصول على السلوك المقارب لـ O (n).

حذف

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

أبسط مجموعة تجزئة

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

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

مشاكل أبسط تنفيذ لمجموعة التجزئة

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

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

طريقة التسلسل

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

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

يتم استخدام طريقة حل التصادمات هذه في Java ، وتسمى بنية البيانات HashSet .

طريقة العنونة المفتوحة

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

من تجزئة تعيين إلى جدول تجزئة (HashMap)

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

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

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

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

يسمى هيكل البيانات هذا بجدول التجزئة .

أسئلة المقابلة النموذجية

س: كيف يتم ترتيب HashSet و HashMap؟ كيف تتم العمليات الرئيسية في هذه المجموعات؟ كيف يتم تطبيق طرق يساوي () و hashCode ()؟
ج : يمكن العثور على إجابات لهذه الأسئلة أعلاه.

س: ما هو عقد يساوي () و hashCode ()؟ ما سبب ذلك؟
ج : إذا كانت الكائنات متساوية ، فيجب أن يكون لها رمز التجزئة متساوٍ. وبالتالي ، يجب تحديد hashCode من خلال قدرة الحقول المتساوية. يمكن أن يؤدي انتهاك هذا العقد إلى آثار مثيرة للاهتمام للغاية. إذا كانت الكائنات متساوية ، لكن رمز التجزئة الخاص بها مختلف ، فقد لا تحصل على القيمة المقابلة للمفتاح الذي أضفت به الكائن إلى HashSet أو HashMap.

استنتاج

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

هذا كل شئ. إذا كنت قد قرأت المادة حتى النهاية ، فأنا أدعو زميلي Evgeny Volosatov ليوضح لك كيفية حل مشكلة الأولمبياد باستخدام أفكار البرمجة الديناميكية لدرس مجاني حول موضوع "أسرار البرمجة الديناميكية" .

ما تحتاج إلى معرفته عن المجموعات القائمة على التجزئة