Hashing

A hash table has m = 11 slots and uses h(k) = k mod 11. What is the home slot of the key 57?

The keys 22, 35, 13, 46, 57, 24 are inserted in this order into an empty table of size m = 11 with h(k) = k mod 11 and linear probing. In which slot does 24 end up?

In the linear-probing table of the previous question (m = 11, keys 22, 35, 13, 46, 57, 24 inserted in order), how many slots does the insertion of 24 examine, including the slot where it is finally stored?

The same keys 22, 35, 13, 46, 57, 24 are inserted in order into an empty table of size 11 with h(k) = k mod 11 and quadratic probing (h(k) + i² mod 11, i = 0, 1, 2, …). Where does 57 end up?

The same keys 22, 35, 13, 46, 57, 24 are inserted in order into an empty table of size 11 using double hashing: probe h(k), h(k) + s, h(k) + 2s, … (mod 11) with h(k) = k mod 11 and step s = 7 − (k mod 7). Where does 57 end up?

The keys 15, 8, 22, 3, 10, 29 are inserted in this order into a separate-chaining table with m = 7 buckets, h(k) = k mod 7, each new key appended to the end of its chain. Which statement is true?

A chaining table starts with m = 8 buckets. After every insertion, if n / m > 1, the table doubles m and rehashes. What is the load factor after 20 keys have been inserted?

A new HashMap<Integer, String>() (default capacity 16, load factor 0.75) receives put calls with distinct keys. Which put causes the first resize, and what is the new capacity?

What is "AB".hashCode()? ('A' is 65 and 'B' is 66.)

Which two strings have the same hashCode()?

Long runs of consecutive occupied slots that grow as keys hashing anywhere into them are added at their end — which collision strategy suffers most from this?

What does secondary clustering mean?

The keys 0, 8, 16, 24 are inserted in this order into an empty table of size m = 8 with h(k) = k mod 8 and quadratic probing (h(k) + i² mod 8). What happens?

The keys 12, 22, 42, 5, 15, 33 are inserted in this order into an empty table of size 10 with h(k) = k mod 10 and linear probing. In which slot does 33 end up?

Linear probing, m = 11, h(k) = k mod 11: after inserting 22, 35, 13, 46, 57, 24 the table holds 35, 13, 46, 57, 24 in slots 2–6. Now 13 is removed by simply setting slot 3 to null. What does a search for 46 return?

In a separate-chaining hash table with n keys, what is the worst-case cost of get, assuming chains are plain linked lists?

A separate-chaining table with m buckets holds n keys, and the hash function spreads keys uniformly. What is the expected cost of an unsuccessful search?

A hash table grows whenever its load factor would exceed 0.75. Implementation X doubles the array on each resize; implementation Y adds 100 slots. What is the amortized cost per insertion over n insertions?

All keys are multiples of 8 (8, 16, 24, …) and h(k) = k mod m. Which table size spreads them best?

What does this program print?

import java.util.*;

public class KeyDemo {
    static class Key {
        int id;
        Key(int id) { this.id = id; }
        @Override public int hashCode() { return id % 3; }
    }
    public static void main(String[] args) {
        Map<Key, String> map = new HashMap<>();
        map.put(new Key(1), "a");
        map.put(new Key(1), "b");
        map.put(new Key(4), "c");
        System.out.println(map.size() + " " + map.get(new Key(1)));
    }
}

A student computes a bucket index as Math.abs(key.hashCode()) % 10. For a key whose hash code is Integer.MIN_VALUE, what is the result?

"cat".hashCode() is 98262. java.util.HashMap computes hash = h ^ (h >>> 16) and then index = hash & (n - 1). Which bucket does "cat" use in a table of length n = 16?

A class overrides equals correctly and writes public int hashCode() { return 42; }. Which statement is true?

You need a map from student IDs to records that must also answer "which students have IDs between 1200 and 1300?" and list all records in ID order. Which implementation fits best?

In double hashing, the probe sequence is h(k), h(k) + s, h(k) + 2s, … (mod m) with s = h₂(k). Which requirement on s is essential?

A table uses h(k) = k mod m. Explain why a prime m is usually recommended, using an example where a non-prime m performs badly.

In an open-addressing table, why can a deleted key not simply be replaced by an empty slot? Describe how tombstones solve the problem and what their drawback is.

A hash table doubles its array whenever the load factor would exceed 0.75. A single resize re-inserts every entry and costs O(n). Explain why the amortized cost of an insertion is nevertheless O(1).

You implement MyHashMap<K,V> with separate chaining. A user stores entries with a key class that overrides equals but not hashCode. Trace what goes wrong in your put and get, and state the rule that the key class must obey.

Write a class MyHashMap<K, V> that uses separate chaining with an array of LinkedList<Entry<K, V>> buckets (initial length 16). Implement:

• V get(K key) — the value for key, or null;
• V put(K key, V value) — insert or replace; return the previous value or null. When the number of entries exceeds 0.75 × the number of buckets, double the array and rehash every entry;
• int size().

null keys must work (hash them to bucket 0), and bucket indices must never be negative.

Write a class ProbingSet that stores int keys in an Integer[] of fixed length m using linear probing with h(k) = Math.floorMod(k, m). Implement boolean add(int key) (returns false for a duplicate), boolean contains(int key) and boolean remove(int key). Deletion must use tombstones so that later searches still work, and add should reuse tombstone slots.