انتقل إلى المحتوى
أمين أبوزيد
Englishالعربية
BEG-041

التجزئة (Hashing)

  • 5 درس
  • 55 دقيقة قراءة
  • 3 ساعة تدريب (تقدير)
ابدأ الوحدة
في هذه الصفحة 8 موضوعات

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

نظرة عامة

الموضوعات

  • دوال التجزئة
  • جداول التجزئة (hash tables)
  • التصادمات (collisions)
  • المجموعات المبنية على التجزئة

تعلّم أولًا

55 دقيقة قراءة · 3 ساعة تدريب (تقدير)

مخرجات التعلم

  1. Explain how a hash table maps keys to buckets.
  2. Describe collision handling (chaining, open addressing) and load-factor resizing.
  3. Explain why a bad hashCode degrades HashMap performance and why mutable keys break it.

الدروس

  1. 01دوال التجزئة (Hash functions)11 د قراءة
  2. 02جداول التجزئة والسلال (buckets)10 د قراءة
  3. 03التصادمات وتغيير الحجم12 د قراءة
  4. 04داخل HashMap وHashSet11 د قراءة
  5. 05عرض عملي: MyHashMap وبطء hashCode الثابت11 د قراءة

المختبر والتمارين

Lab

BEG-041-LAB1 · MyHashMap

Outcomes: 1–3 · Time: ~3 h

  1. Implement a chaining-based MyHashMap<K,V> with put, get, remove, size, and load-factor resizing.
  2. Test it, including replacing an existing key and a missing key.
  3. Create a key class with a constant hashCode; time 20,000 inserts and lookups with it and with a good hashCode; record both timings.

Acceptance: tests pass; timing evidence.

Exercises (assessment: implementation plus quiz)

IDOutcomeTask
BEG-041-EX011With 5 buckets and index = hash % 5, place keys with hashes 12, 7, 22, 3, 17 and say where the collisions are.
BEG-041-EX021Explain in three sentences how get finds a value without scanning the whole table.
BEG-041-EX032Compare chaining and open addressing in two sentences each.
BEG-041-EX042A table has 16 buckets and load factor 0.75. At which entry count does it resize, and to what size?
BEG-041-EX053A Point class overrides equals but not hashCode. Describe what goes wrong when you put it in a HashSet.
BEG-041-EX063A key is stored in a HashMap, then one of its fields changes. What happens to get(key), and how do you avoid it?
أظهر الحلول
  • EX01 Indexes: 12 -> 2, 7 -> 2, 22 -> 2, 3 -> 3, 17 -> 2. Keys 12, 7, 22, 17 collide in bucket 2; 3 is alone in bucket 3.
  • EX02 get computes the key's hash, turns it into a bucket index, and opens only that bucket. It compares keys with equals along the short chain there. The rest of the table is never touched.
  • EX03 Chaining: each bucket holds a list of entries, and colliding keys are added to it; easy to implement. Open addressing: all entries live in the array itself, and a collision probes for the next free slot; saves node objects but needs care when removing.
  • EX04 Resize when entries exceed 12 (16 x 0.75); new capacity 32.
  • EX05 Two equal points can have different hash codes, so they land in different buckets and the set may hold duplicates or fail contains. Always override both methods together.
  • EX06 The hash changes, so get looks in a different bucket and returns null (the entry is still inside, unreachable). Use immutable keys such as String, Integer, or records.

الاختبار

Outcomes: O1 hash tables and buckets · O2 collisions and resizing · O3 bad hash codes and mutable keys.

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

  1. 1A hash function turns a key into:O1
  2. 2If a.equals(b) is true, their hashCode() values must be:O1
  3. 3In a hash table, the bucket for a key is chosen from:O1
  4. 4Average cost of HashMap.get:O1
  5. 5Two different keys in the same bucket is called a:O2
  6. 6Chaining handles collisions by:O2
  7. 7Load factor is:O2
  8. 8When the load factor limit is passed, the table:O2
  9. 9A hashCode that always returns the same number makes lookups about:O3
  10. 10Changing a key after putting it in a HashMap can cause:O3

الجزء العملي

Implementation of MyHashMap (lab BEG-041-LAB1) with timing evidence, plus this quiz and exercises BEG-041-EX01 to EX06. Pass: tests pass, timing shows the constant-hash slowdown, and at least 8 of 10 quiz answers correct.

أخطاء شائعة

Mutating a key after insertion; assuming HashMap iteration order.

التقييم

Implementation plus quiz.

الصلة بالمسار الوظيفي

Caching (MID-037), partitioning (MID-028), sharding (SRC-007).

اكتب للبحث في المستويات والمراحل والوحدات والدروس.