Triển khai Custom HashSet trong Java

Ý tưởng

Tự viết một HashSet đơn giản để hiểu cơ chế: dùng mảng bucket, hash function, xử lý collision (chaining). Thực tế nên dùng java.util.HashSet (đã tối ưu, thread-safe options, serialization...).

Ví dụ minh họa (giản lược)

import java.util.*;

public class CustomHashSetDemo {
    public static void main(String[] args) {
        // Chỉ demo ý tưởng, không phải implementation hoàn chỉnh
        MyHashSet set = new MyHashSet<>();
        set.add("England");
        set.add("Australia");
        set.add("India");
        set.add("Australia"); // duplicate -> ignored

        System.out.println(set); // [England, Australia, India] (thứ tự không đảm bảo)
    }
}

// Custom HashSet cực đơn giản (chỉ demo)
class MyHashSet extends AbstractSet {
    private static final int INITIAL_CAPACITY = 16;
    private Node[] buckets = (Node[]) new Node[INITIAL_CAPACITY];
    private int size = 0;

    static class Node {
        E key;
        Node next;
        Node(E key, Node next) { this.key = key; this.next = next; }
    }

    private int hash(Object key) {
        int h = key.hashCode();
        return (h ^ (h >>> 16)) & (buckets.length - 1);
    }

    @Override
    public boolean add(E e) {
        int idx = hash(e);
        for (Node n = buckets[idx]; n != null; n = n.next) {
            if (n.key.equals(e)) return false; // đã tồn tại
        }
        buckets[idx] = new Node<>(e, buckets[idx]);
        size++;
        return true;
    }

    @Override
    public Iterator iterator() {
        return new Iterator() {
            int bucket = -1; Node current = null, next = null;
            { advance(); }
            void advance() {
                if (next != null) { current = next; return; }
                while (++bucket < buckets.length) {
                    if (buckets[bucket] != null) { current = buckets[bucket]; next = current.next; return; }
                }
                current = null;
            }
            public boolean hasNext() { return current != null; }
            public E next() { E k = current.key; advance(); return k; }
        };
    }

    @Override public int size() { return size; }
    @Override public String toString() { return iteratorToString(); }
}

Kết quả

[England, Australia, India]

Lưu ý: Implementation trên thiếu: resize/rehash, remove(), serialization, thread-safety, null handling, spliterator... Chỉ để hiểu nguyên lý. Producción dùng java.util.HashSet.