Hash Table

package com.datastructures.hashing.hashtable.classic;

import org.junit.jupiter.api.Test;

import java.util.NoSuchElementException;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class HashTableTest {

    @Test
    void startsEmpty() {
        HashTable<String, Integer> table = new HashTable<>();

        assertThat(table.isEmpty()).isTrue();
        assertThat(table.size()).isZero();
    }

    @Test
    void putThenGetReturnsTheStoredValue() {
        HashTable<String, Integer> table = new HashTable<>();

        table.put("a", 1);

        assertThat(table.get("a")).isEqualTo(1);
        assertThat(table.size()).isEqualTo(1);
        assertThat(table.isEmpty()).isFalse();
    }

    @Test
    void getOnAMissingKeyReturnsNull() {
        HashTable<String, Integer> table = new HashTable<>();

        assertThat(table.get("missing")).isNull();
        assertThat(table.containsKey("missing")).isFalse();
    }

    @Test
    void puttingAnExistingKeyOverwritesTheValueAndReturnsThePrevious() {
        HashTable<String, Integer> table = new HashTable<>();
        table.put("a", 1);

        Integer previous = table.put("a", 2);

        assertThat(previous).isEqualTo(1);
        assertThat(table.get("a")).isEqualTo(2);
        assertThat(table.size()).isEqualTo(1);
    }

    @Test
    void removeDeletesTheEntryAndReturnsItsValue() {
        HashTable<String, Integer> table = new HashTable<>();
        table.put("a", 1);

        Integer removed = table.remove("a");

        assertThat(removed).isEqualTo(1);
        assertThat(table.containsKey("a")).isFalse();
        assertThat(table.size()).isZero();
    }

    @Test
    void removingAMissingKeyThrows() {
        HashTable<String, Integer> table = new HashTable<>();

        assertThatThrownBy(() -> table.remove("missing")).isInstanceOf(NoSuchElementException.class);
    }

    @Test
    void keysThatCollideOnTheSameBucketAreAllRetrievableIndependently() {
        HashTable<CollidingKey, String> table = new HashTable<>();
        CollidingKey first = new CollidingKey("first");
        CollidingKey second = new CollidingKey("second");
        CollidingKey third = new CollidingKey("third");

        table.put(first, "1");
        table.put(second, "2");
        table.put(third, "3");

        assertThat(table.get(first)).isEqualTo("1");
        assertThat(table.get(second)).isEqualTo("2");
        assertThat(table.get(third)).isEqualTo("3");
        assertThat(table.size()).isEqualTo(3);
    }

    @Test
    void removingOneCollidingKeyDoesNotAffectItsBucketmates() {
        HashTable<CollidingKey, String> table = new HashTable<>();
        CollidingKey first = new CollidingKey("first");
        CollidingKey second = new CollidingKey("second");
        table.put(first, "1");
        table.put(second, "2");

        table.remove(first);

        assertThat(table.containsKey(first)).isFalse();
        assertThat(table.get(second)).isEqualTo("2");
    }

    @Test
    void growingPastTheLoadFactorResizesAndKeepsEveryEntryRetrievable() {
        HashTable<Integer, Integer> table = new HashTable<>();
        int initialBucketCount = table.bucketCount();

        for (int i = 0; i < 1000; i++) {
            table.put(i, i * 10);
        }

        assertThat(table.bucketCount()).isGreaterThan(initialBucketCount);
        assertThat(table.size()).isEqualTo(1000);
        for (int i = 0; i < 1000; i++) {
            assertThat(table.get(i)).isEqualTo(i * 10);
        }
    }

    @Test
    void putRejectsNullKeys() {
        HashTable<String, Integer> table = new HashTable<>();

        assertThatThrownBy(() -> table.put(null, 1)).isInstanceOf(NullPointerException.class);
    }

    /** A key whose hashCode is fixed regardless of content, to force every instance into the same bucket. */
    private static final class CollidingKey {
        private final String label;

        CollidingKey(String label) {
            this.label = label;
        }

        @Override
        public int hashCode() {
            return 42;
        }

        @Override
        public boolean equals(Object other) {
            return other instanceof CollidingKey that && this.label.equals(that.label);
        }
    }
}

package com.datastructures.hashing.hashtable.applied;

import org.junit.jupiter.api.Test;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneOffset;

import static org.assertj.core.api.Assertions.assertThat;

class IdempotencyKeyCacheTest {

    @Test
    void aKeySeenForTheFirstTimeIsNotADuplicate() {
        IdempotencyKeyCache cache = new IdempotencyKeyCache(Clock.systemUTC());

        assertThat(cache.isDuplicate("tx-1")).isFalse();
    }

    @Test
    void markingAKeyProcessedMakesTheNextCheckReportADuplicate() {
        IdempotencyKeyCache cache = new IdempotencyKeyCache(Clock.systemUTC());

        cache.markProcessed("tx-1");

        assertThat(cache.isDuplicate("tx-1")).isTrue();
    }

    @Test
    void differentKeysAreTrackedIndependently() {
        IdempotencyKeyCache cache = new IdempotencyKeyCache(Clock.systemUTC());

        cache.markProcessed("tx-1");

        assertThat(cache.isDuplicate("tx-1")).isTrue();
        assertThat(cache.isDuplicate("tx-2")).isFalse();
        assertThat(cache.size()).isEqualTo(1);
    }

    @Test
    void reMarkingTheSameKeyDoesNotGrowTheCache() {
        IdempotencyKeyCache cache = new IdempotencyKeyCache(Clock.systemUTC());

        cache.markProcessed("tx-1");
        cache.markProcessed("tx-1");

        assertThat(cache.size()).isEqualTo(1);
    }

    @Test
    void evictOlderThanRemovesOnlyExpiredEntries() {
        Instant now = Instant.parse("2026-08-16T12:00:00Z");
        MutableClock clock = new MutableClock(now);
        IdempotencyKeyCache cache = new IdempotencyKeyCache(clock);

        cache.markProcessed("old-tx");
        clock.advance(Duration.ofMinutes(10));
        cache.markProcessed("recent-tx");

        cache.evictOlderThan(now.plus(Duration.ofMinutes(5)));

        assertThat(cache.isDuplicate("old-tx")).isFalse();
        assertThat(cache.isDuplicate("recent-tx")).isTrue();
        assertThat(cache.size()).isEqualTo(1);
    }

    /** A JDK {@link Clock} whose {@code instant()} can be moved forward on demand for tests. */
    private static final class MutableClock extends Clock {
        private Instant current;

        MutableClock(Instant current) {
            this.current = current;
        }

        void advance(Duration duration) {
            current = current.plus(duration);
        }

        @Override
        public ZoneOffset getZone() {
            return ZoneOffset.UTC;
        }

        @Override
        public Clock withZone(java.time.ZoneId zone) {
            throw new UnsupportedOperationException();
        }

        @Override
        public Instant instant() {
            return current;
        }
    }
}