Bloom Filters, LRU Cache & Trie: Advanced Java Algorithm Implementations for Production (2026)

import java.util.BitSet;
import java.nio.charset.StandardCharsets;

public class BloomFilter<T> {
    private final BitSet bitSet;
    private final int bitSetSize;
    private final int numHashFunctions;
    private int elementCount;

    public BloomFilter(int expectedElements, double falsePositiveRate) {
        this.bitSetSize = optimalBitSetSize(expectedElements, falsePositiveRate);
        this.numHashFunctions = optimalNumHashFunctions(expectedElements, bitSetSize);
        this.bitSet = new BitSet(bitSetSize);
    }

    private static int optimalBitSetSize(int n, double p) {
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    private static int optimalNumHashFunctions(int n, int m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    // MurmurHash3-inspired double hashing: h_i(x) = h1(x) + i * h2(x)
    private int[] getHashPositions(T element) {
        byte[] bytes = element.toString().getBytes(StandardCharsets.UTF_8);
        int h1 = murmurHash(bytes, 0);
        int h2 = murmurHash(bytes, h1);
        int[] positions = new int[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            positions[i] = Math.abs((h1 + i * h2) % bitSetSize);
        }
        return positions;
    }

    private int murmurHash(byte[] data, int seed) {
        int h = seed;
        for (byte b : data) {
            h ^= b;
            h *= 0x5bd1e995;
            h ^= h >>> 15;
        }
        return h;
    }

    public void add(T element) {
        for (int pos : getHashPositions(element)) {
            bitSet.set(pos);
        }
        elementCount++;
    }

    public boolean mightContain(T element) {
        for (int pos : getHashPositions(element)) {
            if (!bitSet.get(pos)) return false;
        }
        return true; // might be false positive
    }

    public double expectedFalsePositiveRate() {
        double exp = -((double) numHashFunctions * elementCount) / bitSetSize;
        return Math.pow(1 - Math.exp(exp), numHashFunctions);
    }

    public int getBitSetSize() { return bitSetSize; }
    public int getNumHashFunctions() { return numHashFunctions; }
    public int getElementCount() { return elementCount; }
}

BloomFilter<String> crawledUrls = new BloomFilter<>(10_000_000, 0.01);

public void crawl(String url) {
    if (crawledUrls.mightContain(url)) {
        // ~1% chance of false positive — skip to avoid re-crawl
        return;
    }
    crawledUrls.add(url);
    // proceed with fetching and indexing
    fetchAndIndex(url);
}

// Solution 1: LinkedHashMap (simplest)
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // accessOrder=true for LRU
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}

// Solution 2: Thread-safe LRU with explicit doubly-linked list
public class ConcurrentLRUCache<K, V> {
    private final int capacity;
    private final Map<K, Node<K, V>> map;
    private final Node<K, V> head, tail; // sentinel nodes

    public ConcurrentLRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new ConcurrentHashMap<>();
        this.head = new Node<>(null, null);
        this.tail = new Node<>(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public synchronized V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) return null;
        moveToFront(node);
        return node.value;
    }

    public synchronized void put(K key, V value) {
        if (map.containsKey(key)) {
            Node<K, V> node = map.get(key);
            node.value = value;
            moveToFront(node);
        } else {
            if (map.size() >= capacity) {
                Node<K, V> lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
            Node<K, V> newNode = new Node<>(key, value);
            addToFront(newNode);
            map.put(key, newNode);
        }
    }

    private void moveToFront(Node<K, V> node) {
        remove(node);
        addToFront(node);
    }

    private void addToFront(Node<K, V> node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void remove(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    static class Node<K, V> {
        K key; V value;
        Node<K, V> prev, next;
        Node(K key, V value) { this.key = key; this.value = value; }
    }
}

public class LFUCache<K, V> {
    private final int capacity;
    private int minFreq;
    private final Map<K, V> keyToVal;
    private final Map<K, Integer> keyToFreq;
    private final Map<Integer, LinkedHashSet<K>> freqToKeys;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minFreq = 0;
        this.keyToVal = new HashMap<>();
        this.keyToFreq = new HashMap<>();
        this.freqToKeys = new HashMap<>();
    }

    public V get(K key) {
        if (!keyToVal.containsKey(key)) return null;
        increaseFreq(key);
        return keyToVal.get(key);
    }

    public void put(K key, V value) {
        if (capacity <= 0) return;
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, value);
            increaseFreq(key);
            return;
        }
        if (keyToVal.size() >= capacity) {
            removeMinFreqKey();
        }
        keyToVal.put(key, value);
        keyToFreq.put(key, 1);
        freqToKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void increaseFreq(K key) {
        int freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqToKeys.get(freq).remove(key);
        if (freqToKeys.get(freq).isEmpty()) {
            freqToKeys.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqToKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void removeMinFreqKey() {
        LinkedHashSet<K> keys = freqToKeys.get(minFreq);
        K evictKey = keys.iterator().next(); // oldest with minFreq
        keys.remove(evictKey);
        if (keys.isEmpty()) freqToKeys.remove(minFreq);
        keyToVal.remove(evictKey);
        keyToFreq.remove(evictKey);
    }
}

          root
           |
           c
           |
           a
          / \
        t*   r
            / \
          d*   e*

public class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
        node.word = word;
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    // Autocomplete: return all words with given prefix
    public List<String> autocomplete(String prefix) {
        List<String> results = new ArrayList<>();
        TrieNode prefixNode = findNode(prefix);
        if (prefixNode == null) return results;
        dfs(prefixNode, results);
        return results;
    }

    private void dfs(TrieNode node, List<String> results) {
        if (node.isEndOfWord) results.add(node.word);
        for (TrieNode child : node.children.values()) {
            dfs(child, results);
        }
    }

    private TrieNode findNode(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            node = node.children.get(c);
            if (node == null) return null;
        }
        return node;
    }

    // Word Search II — find all words from dictionary in a 2D board
    public List<String> findWords(char[][] board, String[] words) {
        for (String w : words) insert(w);
        Set<String> found = new HashSet<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfsBoard(board, i, j, root, found);
        return new ArrayList<>(found);
    }

    private void dfsBoard(char[][] board, int i, int j, TrieNode node, Set<String> found) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || !node.children.containsKey(c)) return;
        TrieNode next = node.children.get(c);
        if (next.isEndOfWord) found.add(next.word);
        board[i][j] = '#'; // mark visited
        dfsBoard(board, i+1, j, next, found);
        dfsBoard(board, i-1, j, next, found);
        dfsBoard(board, i, j+1, next, found);
        dfsBoard(board, i, j-1, next, found);
        board[i][j] = c; // restore
    }

    static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isEndOfWord;
        String word; // store word at terminal node for easy retrieval
    }
}

// ConcurrentSkipListMap: thread-safe sorted map, O(log n) ops
ConcurrentSkipListMap<Integer, String> leaderboard =
    new ConcurrentSkipListMap<>(Comparator.reverseOrder());

leaderboard.put(100, "Alice");
leaderboard.put(250, "Bob");
leaderboard.put(175, "Charlie");

// Top 3 players: O(log n) per operation
leaderboard.entrySet().stream().limit(3).forEach(e ->
    System.out.println(e.getValue() + " -> " + e.getKey()));

// Range query: scores between 100 and 200
NavigableMap<Integer, String> range = leaderboard.subMap(200, true, 100, true);

// ConcurrentSkipListSet for sorted deduplication
ConcurrentSkipListSet<String> sortedUserIds = new ConcurrentSkipListSet<>();
sortedUserIds.add("user:abc");
sortedUserIds.add("user:xyz");
String lowest = sortedUserIds.first();
String highest = sortedUserIds.last();