ما هي جداول التصنيف والهاشماب وحالات استخدامها النموذجية؟

Question

لقد قمت مؤخرًا بتشغيل هذه الشروط عدة مرات ولكني في حيرة من أمري حول كيفية عملها ومتى يتم تنفيذها عادةً؟

Answer 1

حسنا، أعتقد أنه من هذا الطريق.

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

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

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

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

يحتوي كل عنصر على خاصيتين وبيانات ومفتاح يحدد البيانات.على سبيل المثال، ستكون قائمة الرموز البريدية للولايات المتحدة عبارة عن رمز بريدي -> اسم نوع الارتباط.تعمل الوظيفة على تقليل المفتاح، ولكنها لا تأخذ في الاعتبار البيانات.

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

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

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

لا يحتوي جدول التجزئة النموذجي على عدد لا نهائي من العناصر المتاحة للتخزين، لذلك عادةً ما يتم تقليل العدد إلى فهرس يناسب حجم المصفوفة.إحدى الطرق للقيام بذلك هي ببساطة أخذ معامل الفهرس مقارنة بحجم المصفوفة.بالنسبة لمصفوفة بحجم 10، سيتم تعيين الفهرس 0-9 مباشرةً إلى فهرس، وسيتم تعيين الفهرس 10-19 إلى 0-9 مرة أخرى، وهكذا.

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

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

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

الوظيفة التي تقلل المفتاح إلى رقم لا تنتج قيمة خطية، على سبيل المثال.يصبح "AAA" 1، ثم يصبح "AAB" 2، لذلك لا يتم فرز جدول التجزئة حسب أي قيمة نموذجية.

هناك مقالة ويكيبيديا جيدة متاحة حول هذا الموضوع أيضًا، هنا.

Answer 2

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

هنالك لا يوجد فرق مهم بين جداول التجزئة وخرائط التجزئة 99٪ من الوقت.

جداول التجزئة سحرية

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

1) كل شيء في جدول التجزئة هو جزء من زوج - هناك مفتاح و أ قيمة.يمكنك إدخال البيانات وإخراجها عن طريق تحديد المفتاح الذي تعمل عليه.

2) إذا كنت تفعل أي شيء باستخدام مفتاح واحد على جدول التجزئة، فهو كذلك بسرعة مذهلة.وهذا يعني أن put(key,value), get(key), contains(key), ، و remove(key) كلها سريعة حقا.

3) جداول التجزئة العامة تفشل في فعل أي شيء غير مدرج في رقم 2!(نعني بكلمة "فشل" أنهم بطيئون للغاية.)

متى نستخدم جداول التجزئة؟

نحن نستخدم جداول التجزئة عندما يناسب سحرهم مشكلتنا.

على سبيل المثال، التخزين المؤقت غالبًا ما ينتهي الأمر باستخدام جدول التجزئة - على سبيل المثال، لنفترض أن لدينا 45000 طالب في إحدى الجامعات وتحتاج بعض العمليات إلى الاحتفاظ بسجلات لهم جميعًا.إذا كنت تشير بشكل روتيني إلى الطالب عن طريق رقم الهوية، فإن أ ID => student ذاكرة التخزين المؤقت منطقية ممتازة.العملية التي تقوم بتحسينها لذاكرة التخزين المؤقت هذه هي بحث سريع.

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

كما أنهم يصنعون أ خيار أول جيد إلى حد ما لبنية البيانات إلا عندما تحتاج إلى القيام بأحد الإجراءات التالية:

متى لا تستخدم جداول التجزئة

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

فرز. إذا لم تتمكن من التكرار، فإن الفرز يمثل ألمًا كبيرًا أيضًا.

الانتقال من القيمة إلى المفتاح.يستخدم اثنين جداول التجزئة.صدقني، لقد أنقذتك للتو الكثير من الألم.

Answer 3

إذا كنت تتحدث من حيث Java، فكلاهما عبارة عن مجموعات تسمح بإضافة الكائنات وحذفها وتحديثها واستخدام خوارزميات Hasing داخليًا.

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

وبصرف النظر عن المزامنة، فإن الآلية الداخلية لتخزين واسترجاع الكائنات هي التجزئة في كلتا الحالتين.

إذا كنت تريد معرفة كيفية عمل التجزئة، فإنني أوصي بالقليل من البحث على Google حول مُنشئي البيانات وتقنيات التجزئة.

Answer 4

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