Set and Map: Inside HashMap

import java.util.*;

public class MiniSet {

    private static class Node {
        Object value;
        Node next;
        Node(Object v) { value = v; }
    }

    private Node[] buckets = new Node[16];
    private int size;

    // hashCode, spread with ^ (h >>> 16), then mask with & (buckets.length - 1).
    int bucketFor(Object v) {
        return 0; // TODO
    }

    // false when the value is already in the set.
    public boolean add(Object v) {
        return false; // TODO
    }

    // Look in ONE bucket only. That is the whole point.
    public boolean contains(Object v) {
        return false; // TODO
    }

    public int size() {
        return size;
    }

    // How many values sit in each of the 16 buckets.
    public int[] bucketSizes() {
        return new int[16]; // TODO
    }

    public static void main(String[] args) {
        // TODO: add 1000 strings, print bucketSizes, show they are spread out
        // TODO: add a duplicate and show add returns false
    }
}

import java.util.*;

public class BadHash {

    static class Constant {
        final int id;
        Constant(int i) { id = i; }
        @Override public boolean equals(Object o) { return o instanceof Constant c && c.id == id; }
        @Override public int hashCode() { return 1; }              // legal. Contract satisfied.
    }

    static class Proper {
        final int id;
        Proper(int i) { id = i; }
        @Override public boolean equals(Object o) { return o instanceof Proper p && p.id == id; }
        @Override public int hashCode() { return Integer.hashCode(id); }
    }

    static class ModFour {
        final int id;
        ModFour(int i) { id = i; }
        @Override public boolean equals(Object o) { return o instanceof ModFour m && m.id == id; }
        @Override public int hashCode() { return id % 4; }
    }

    // Build a HashMap of n keys of each class. Return milliseconds.
    static long timeConstant(int n) { return 0; }  // TODO
    static long timeProper(int n)   { return 0; }  // TODO
    static long timeModFour(int n)  { return 0; }  // TODO

    // The uncomfortable part: prove the slow one is still RIGHT.
    static int sizeWithConstantHash(int n) {
        return 0; // TODO
    }

    static boolean lookupsStillCorrect(int n) {
        return false; // TODO
    }

    public static void main(String[] args) {
        // TODO: time all three at 40_000 and print them
        // TODO: print the size and the correctness check too
    }
}

import java.util.*;

public class Spread {

    // Mask into the array. n is always a power of two.
    static int bucket(int hash, int n) {
        return 0; // TODO
    }

    // Mix the high bits down into the low ones.
    static int spread(int h) {
        return h; // TODO
    }

    static int[] bucketsWithoutSpread(int[] hashes, int n) {
        return new int[hashes.length]; // TODO
    }

    static int[] bucketsWithSpread(int[] hashes, int n) {
        return new int[hashes.length]; // TODO
    }

    // All 32 bits, padded with leading zeros.
    static String bits(int h) {
        return ""; // TODO
    }

    public static void main(String[] args) {
        int[] hashes = {65536, 131072, 196608, 262144};

        // TODO: print the buckets without spreading. All four land in the same one
        // TODO: print them with spreading, and compare
        // TODO: print the bits of 65536 before and after mixing, one above the other
        // TODO: check that a negative hash still gives a valid index
    }
}

import java.util.*;

public class Vanish {

    static class Unit {
        String name;
        int id;                                // not final, and that is the bug
        Unit(String n, int i) { name = n; id = i; }
        @Override public boolean equals(Object o) { return o instanceof Unit u && u.id == id; }
        @Override public int hashCode() { return Integer.hashCode(id); }
        @Override public String toString() { return name + "#" + id; }
    }

    // TODO: a second class, the same but with the bug made impossible

    // Put Atlas#101 -> "north patrol", then get it straight back.
    static String lookupBeforeChange() {
        return null; // TODO
    }

    // Put it in, change atlas.id to 999, then report whether get returns null.
    static boolean getFailsAfterChange() {
        return false; // TODO
    }

    static boolean containsKeyFailsAfterChange() {
        return false; // TODO
    }

    // The map still says it holds how many?
    static int sizeAfterChange() {
        return 0; // TODO
    }

    // Walk the entries. Is the entry still physically in there?
    static boolean entryStillThere() {
        return false; // TODO
    }

    // The same scenario with your redesigned class. Nothing can go wrong.
    static boolean fixedVersionCannotBreak() {
        return false; // TODO
    }

    public static void main(String[] args) {
        // TODO: print all six and read them in order
    }
}

import java.util.*;

public class ThreeSets {

    static List<String> hashSetOrder(List<String> input) {
        return List.of(); // TODO
    }

    static List<String> linkedHashSetOrder(List<String> input) {
        return List.of(); // TODO
    }

    static List<String> treeSetOrder(List<String> input) {
        return List.of(); // TODO
    }

    // Add a plain Object to a TreeSet. Return "ok" or the exception's name.
    static String treeSetWithNoNaturalOrder() {
        return "ok"; // TODO
    }

    // Add 0 to n-1 to the set given. Return milliseconds.
    static long timeInserts(Set<Integer> target, int n) {
        return 0; // TODO
    }

    public static void main(String[] args) {
        List<String> input = List.of("pear", "apple", "fig", "date", "cherry");

        // TODO: print all three orderings for the same input
        // TODO: time 200_000 insertions into each of the three and rank them
        // TODO: print what a TreeSet does with something that has no natural order
    }
}