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

جداول التجزئة والسلال (buckets)

  • الدرس 2 من 5
  • 10 دقيقة قراءة
  • مبتدئ
في هذا الدرس 11 موضوعات

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

Lesson Overview

In the last lesson a hash function turned a key into a number. Now we use that number. A hash table is an array of numbered slots, called buckets, like the wall of mailboxes in an office. To store "Ana", we compute her hash code, turn it into a box number, and put her entry in that box. To find her later, we compute the same number and open that one box.

That is the whole trick: the key itself tells us where to look, so we skip every other box. This lesson shows how the number becomes a box, how put and get work, and why lookup is fast on average. It also ends with a small problem, two keys wanting the same box, which the next lesson solves.

Why this matters: this is how HashMap and HashSet work. Once you see the array behind them, their speed, and the rules about hashCode, stop being magic.

This lesson builds on hash codes (previous lesson), on arrays and Big O notation (the data structures modules), and on the % operator.

Learning Objectives

By the end of this lesson you will be able to:

  • Describe a hash table as an array of buckets.
  • Turn any int hash code into a valid bucket index in Java.
  • Trace put and get on a small table by hand.
  • Explain why get does not scan the whole table and what "O(1) on average" means.
  • Explain why hashCode and equals are both needed to find a key.
  • Spot the situation where two keys want the same bucket.

Written Explanation

An array of buckets

A hash table keeps an ordinary array. Each position in the array is a bucket. The number of buckets is the table's capacity. In this lesson a bucket will hold one entry (a key and its value); the next lesson lets it hold several.

text
index:   0     1     2     3     4     5     6     7
       [    ][    ][    ][    ][Ana ][    ][    ][Omar]

An entry that stores both a key and a value turns the table into a map: look up the key, get the value. A set is the same table that stores only keys.

From hash code to bucket index

A hash code can be any int, negative or huge. A bucket index must be between 0 and capacity - 1. The usual step is the remainder after division:

text
index = hash code modulo capacity

In Java the % operator keeps the sign of the left side, so a negative hash code gives a negative result. For example, -7 % 5 is -2, which is not an index. Two safe options:

  • Math.floorMod(hash, capacity). The Java documentation says its result has the sign of the divisor, so with a positive capacity it is always 0 or higher.
  • (hash & 0x7fffffff) % capacity. The mask clears the sign bit, so the number is never negative.

Do not use Math.abs(hash) % capacity: Math.abs(Integer.MIN_VALUE) is still negative. Both safe options give a valid index, but they can give different indexes for the same negative hash. That is fine, as long as a table uses the same formula every time.

(Real HashMap uses another trick with power-of-two capacities, which lesson 4 mentions. The idea is the same: squeeze the hash code into the range of the array.)

put: store a key

  1. Compute key.hashCode().
  2. Turn it into a bucket index.
  3. Place the entry in that bucket.

get: find a key

  1. Compute key.hashCode() (the same number as in put, because hash codes are deterministic).
  2. Turn it into the same bucket index.
  3. Open that bucket only. If its key is equals to the key we want, return the value. If the bucket is empty, the key is not there.

Step 3 uses equals as the final check. The hash code only chooses where to look; equals confirms we found the right key. This is why equal keys must have equal hash codes: otherwise get computes a different index and looks in the wrong box.

Why this is fast

A list would check entries one by one: up to n checks, which is O(n). A hash table computes the hash (a few steps for a typical key), computes an index (one operation), and opens one bucket. The work does not grow with the number of entries, so put and get are O(1) on average.

"On average" matters, and it depends on two conditions that the next lessons examine:

  • keys are well spread, so few keys share a bucket (the quality from lesson 1);
  • the table is not too full, so buckets stay short (resizing, lesson 3).

The Java documentation for HashMap states the same condition: constant-time get and put, assuming the hash function disperses elements properly among the buckets.

Note that the cost of computing a hash is not always trivial: hashing a long string looks at every character. For short keys we treat it as a constant.

A first look at the problem

Our simple table keeps one entry per bucket. What if two different keys map to the same index? We would overwrite one with the other, and the lost key could not be found. The example below shows this with real keys. A hash table needs a plan for this situation, and that plan is the topic of lesson 3.

Examples

Example 1: finding the bucket by hand (simple)

A table has 8 buckets. Hash codes: Ana is 65972, Omar is 2461359. By hand: 65972 % 8 is 4 (since 8 * 8246 = 65968, remainder 4), and 2461359 % 8 is 7. So Ana goes in bucket 4 and Omar in bucket 7, as in the drawing above. Looking up Ana computes 65972 again, goes to bucket 4, and finds her.

Example 2: a tiny table with put and get (practical)

This table has 8 buckets and keeps one key and one value per bucket.

java
public class L02 {
    static final int BUCKETS = 8;
    static final String[] keys = new String[BUCKETS];
    static final int[] values = new int[BUCKETS];

    static int indexFor(Object key) {
        return Math.floorMod(key.hashCode(), BUCKETS);
    }
    static void put(String key, int value) {
        int i = indexFor(key);
        keys[i] = key;      // no collision handling yet!
        values[i] = value;
    }
    static Integer get(String key) {
        int i = indexFor(key);
        if (keys[i] != null && keys[i].equals(key)) return values[i];
        return null;
    }
    public static void main(String[] args) {
        for (String k : new String[] {"Ana", "Omar", "Sara", "Lina", "Khaled"})
            System.out.println(k + " hash=" + k.hashCode() + " -> bucket " + indexFor(k));
        put("Ana", 30);
        put("Omar", 25);
        System.out.println(get("Ana") + " " + get("Omar") + " " + get("Sara"));
    }
}

Real output:

text
Ana hash=65972 -> bucket 4
Omar hash=2461359 -> bucket 7
Sara hash=2569501 -> bucket 5
Lina hash=2368528 -> bucket 0
Khaled hash=-2048738041 -> bucket 7
30 25 null

get("Sara") opens bucket 5, finds it empty, and returns null. Look at the last key: Khaled's hash code is negative, and floorMod still gives a valid bucket, 7, the same as Omar's.

Example 3: the first collision breaks a naive table (realistic)

Add one more line after the two put calls: put("Khaled", 40);, then print get("Omar") + " " + get("Khaled"). Real output:

text
null 40

Khaled and Omar share bucket 7. Our put overwrote Omar's entry, so get("Omar") finds Khaled's key in the box, the equals check fails, and the answer is null. Omar's data is silently gone. A correct hash table must not do this, and the next lesson fixes it by letting a bucket hold more than one entry.

The same example also shows why the equals check in get is needed: without it, get("Omar") would return Khaled's value, 40.

Backend Insight

Hash tables are the engine behind many everyday backend structures: a Map of user id to user object, a Set of seen request ids (to ignore duplicate requests), an in-memory cache. The reason these are used so often is the property you just saw: lookup cost does not grow as the data grows.

Two practical points. First, the speed depends on well spread keys, so a key class with a careless hashCode is a performance bug, not just a style problem. Second, a hash table has no useful order: the bucket position comes from the hash code, not from when or in what order keys were added. Never rely on the order of a HashMap or HashSet.

Common Mistakes

Mistake 1: Using a negative hash code as an index

  • Incorrect: hash % capacity with a possibly negative hash (can give -2), or Math.abs(hash) % capacity.
  • Correct: Math.floorMod(hash, capacity) or (hash & 0x7fffffff) % capacity.

Mistake 2: Computing the index differently in put and get

If put and get use different formulas or different capacities, get opens the wrong bucket and the key seems to vanish. One helper method used by both, like indexFor above, prevents this.

Mistake 3: Skipping the equals check in get

The bucket may contain a different key that shares the same index. Returning whatever is in the bucket gives wrong answers. Always compare keys with equals before returning the value.

Mistake 4: Believing a hash table keeps insertion or sorted order

Keys sit where their hash codes place them. If you need a given order, a hash table is the wrong tool (or you need an ordered variant, covered when you choose collections).

Exercises

Try each exercise yourself before opening the solutions.

Level A: Foundation

A1. A table has 8 buckets and uses index = hash % 8. Give the bucket of hash codes 10, 18, 3, 26, and 11.

أظهر الحل A1

A1. 10 % 8 = 2, 18 % 8 = 2, 3 % 8 = 3, 26 % 8 = 2, 11 % 8 = 3.

A2. Which keys in A1 share a bucket?

أظهر الحل A2

A2. 10, 18, and 26 share bucket 2. 3 and 11 share bucket 3.

A3. In one sentence: why does get not scan every bucket?

أظهر الحل A3

A3. It computes the key's hash, which gives a bucket index, and looks only in that bucket.

Level B: Application

B1. For a table with 8 buckets, compute -9 % 8 and Math.floorMod(-9, 8). Which one can be used as an index?

أظهر الحل B1

B1. -9 % 8 is -1 (the sign follows the left side), which is not an index. Math.floorMod(-9, 8) is 7, which is valid.

B2. Describe the steps of get("Ana") in your own words, including where equals is used.

أظهر الحل B2

B2. Compute "Ana".hashCode() (65972), convert it to a bucket index with the same formula as put, open that bucket, and compare the key stored there with "Ana" using equals. If equal, return its value; if the bucket is empty or holds a different key, report not found.

B3. A developer's put uses Math.floorMod(hash, capacity), but get uses hash & 0x7fffffff followed by % capacity on a negative-hash key. Explain what may go wrong.

أظهر الحل B3

B3. The two formulas can give different indexes for the same negative hash (for example -4 gives 1 with floorMod(-4, 5) and 4 with the mask version, when run). get then opens a different bucket from the one put used, and does not find the key. A table must use one formula everywhere.

Level C: Challenge

C1. The table in Example 2 is changed to 16 buckets. Without running it, say whether Omar's bucket stays 7. Then run or compute it: 2461359 % 16.

أظهر الحل C1

C1. 2461359 % 16 is 15, so Omar moves from bucket 7 to bucket 15. The index depends on the capacity, which is why a table that changes its size (lesson 3) has to place all entries again.

C2. Explain why a hash table with a very good hash function can still be slow if the capacity is 1.

أظهر الحل C2

C2. With one bucket every key has index 0 whatever the hash, so all keys share one place and a lookup must examine them one after another, which is O(n). A good hash function cannot help if the capacity leaves no room to spread keys.

Mini Challenge

On paper, draw a table of 5 buckets. Use index = hash % 5 for these hash codes, in order: 14, 9, 21, 4, 7. Mark each bucket as you place the keys, and write down the moment a bucket you want is already occupied. Then explain, in two sentences, what a naive table that keeps one entry per bucket would lose.

Check your work: the first conflict appears when 9 meets 14 in bucket 4, and your explanation says that the earlier entry would be overwritten and its key no longer found.

Summary & Next Lesson

Key takeaways

  • A hash table is an array of buckets. A hash code is turned into a bucket index, for example with Math.floorMod(hash, capacity).
  • put and get both go straight to one bucket, and get confirms the key with equals.
  • That makes lookups O(1) on average, provided keys are well spread and the table is not too full.
  • Negative hash codes need care: use floorMod or a sign mask, not % alone or Math.abs.
  • When two keys share a bucket, a one-entry-per-bucket table loses data. Handling this is the next lesson.

Next lesson

Next, "Collisions and resizing" shows how two keys can share a bucket safely using chaining and open addressing, and how a table grows when it becomes too full.

Self-check

  1. What is a bucket?
  2. Why does get not scan the whole table?
  3. Why is -7 % 5 unsuitable as an index, and what can you use instead?
  4. Why does get still need equals after finding the bucket?
  5. What goes wrong if put and get compute the index differently?
أظهر الإجابات
  1. One position in the table's array, which holds the entry (or entries) for the keys that map to it.
  2. The key's hash code leads straight to one bucket, so only that bucket is examined.
  3. It equals -2, which is not a valid array index. Use Math.floorMod(-7, 5) (which gives 3) or mask the sign bit first.
  4. The bucket may hold a different key that mapped to the same index, so equals confirms it is the right one.
  5. get opens a different bucket from the one put used, so the key appears to be missing.

References

  • Oracle, Math (Java SE 21). It says floorMod returns a result with the sign of the divisor and that Math.abs(Integer.MIN_VALUE) stays negative.
  • Oracle, HashMap (Java SE 21). It defines capacity as the number of buckets, promises constant-time get and put when the hash function disperses elements properly, and gives no ordering guarantee.
  • The mailbox analogy, the one-entry-per-bucket teaching table, and the description of the masking formula are this course's own simplifications. Example 2 and the exercise values were compiled and run on JDK 21 (Example 3 by adding the two lines described).

التطبيق

طبّق هذا الدرس بمختبر الوحدة وتمارينها واختبارها.

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

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

تابع إلى الدرس التالي

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