해시 테이블

/* ── HashMap 기본 사용 ──────────────────────────────────── */
Map<String, Integer> map = new HashMap<>();

// 삽입 — 평균 O(1)
map.put("apple",  3);
map.put("banana", 5);
map.put("cherry", 2);

// 탐색 — 평균 O(1)
int count = map.getOrDefault("apple", 0); // 3

// 존재 확인
boolean has = map.containsKey("banana");  // true

// 삭제 — 평균 O(1)
map.remove("cherry");

// 순회 (순서 보장 없음)
for (Map.Entry<String, Integer> e : map.entrySet()) {
    System.out.println(e.getKey() + " → " + e.getValue());
}

/* ── 빈도 카운팅 패턴 ───────────────────────────────────── */
int[] nums = {1, 2, 2, 3, 3, 3};
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) {
    freq.merge(n, 1, Integer::sum); // 없으면 1, 있으면 +1
}
// freq: {1=1, 2=2, 3=3}

/* ── HashMap 내부 구조 파라미터 ─────────────────────────── */
// 기본 용량 = 16 (항상 2의 거듭제곱)
// 기본 부하율 = 0.75
// 임계값 = 용량 * 부하율 = 12
// 13번째 삽입으로 size가 임계값 12를 초과 → 용량 32로 리사이징 + 전체 재해싱

// 초기 용량 예측 가능 시 직접 지정으로 리사이징 방지
Map<String, Integer> presized =
    new HashMap<>(1 << 7); // 128 (2의 거듭제곱)

/* ── 키로 사용할 클래스의 필수 규칙 ────────────────────── */
public class Point {
    private final int x, y;

    @Override
    public int hashCode() {
        // Objects.hash는 null 안전, 여러 필드 조합에 적합
        return Objects.hash(x, y);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Point)) return false;
        Point p = (Point) o;
        return x == p.x && y == p.y;
    }
    // hashCode와 equals를 반드시 함께 재정의해야 합니다.
    // equals()가 true면 hashCode()도 같아야 하는 규약 때문입니다.
}

/* ── 체이닝 해시 테이블 구현 ────────────────────────────── */
public class ChainingHashTable<K, V> {
    private static final int DEFAULT_CAP   = 16;
    private static final float LOAD_FACTOR = 0.75f;

    private LinkedList<Entry<K,V>>[] buckets;
    private int size;

    private static class Entry<K, V> {
        K key; V value;
        Entry(K k, V v) { key = k; value = v; }
    }

    @SuppressWarnings("unchecked")
    public ChainingHashTable() {
        buckets = new LinkedList[DEFAULT_CAP];
    }

    private int bucketIdx(K key) {
        // & 0x7FFFFFFF으로 음수 해시값을 양수로 변환
        return (key.hashCode() & 0x7FFFFFFF) % buckets.length;
    }

    public void put(K key, V value) {
        int idx = bucketIdx(key);
        if (buckets[idx] == null) buckets[idx] = new LinkedList<>();

        // 같은 키 존재 시 값 갱신
        for (Entry<K,V> e : buckets[idx]) {
            if (e.key.equals(key)) { e.value = value; return; }
        }
        buckets[idx].add(new Entry<>(key, value));
        size++;

        // 부하율 초과 시 리사이징
        if ((float) size / buckets.length > LOAD_FACTOR) resize();
    }

    public V get(K key) {
        int idx = bucketIdx(key);
        if (buckets[idx] == null) return null;
        for (Entry<K,V> e : buckets[idx]) {
            if (e.key.equals(key)) return e.value;
        }
        return null;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        LinkedList<Entry<K,V>>[] old = buckets;
        buckets = new LinkedList[old.length * 2]; // 2배 확장
        size = 0;
        for (LinkedList<Entry<K,V>> bucket : old) {
            if (bucket == null) continue;
            for (Entry<K,V> e : bucket) put(e.key, e.value); // 재해싱
        }
    }
}