Consistant Hashing, Bloom Filter, SkipLists, B-Tree, LRU/LFU

1. Consistence Hashing

Consistent hashing is a hashing technique that minimizes the need for remapping when a hash table is resized . In traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. However, consistent hashing uses a special kind of hashing technique such that only keys need to be remapped on average, where “n” is the number of keys and “m” is the number of slots. This technique is particularly useful in load balancing, where a standard hash function can be used to calculate the hash value for a blob, and then the resultant value of the hash is used with modular operations to determine the specific server where the blob will be placed. This technique is used in various data storage and distribution systems, including OpenStack’s Object Storage Service Swift, Amazon’s storage system Dynamo, and Akamai content delivery network.

Consistent hashing is widely used in distributed system design for several use cases, including but not limited to:

• Load balancing: Consistent hashing allows for easy distribution of load across multiple servers. When a new server is added to the cluster or an existing server is removed, only a small subset of keys need to be remapped to the new or remaining servers, minimizing the impact of the change on the overall system.

• Caching: Consistent hashing is used to determine which cache node should store a particular key-value pair. This can help reduce the number of cache misses, improving the overall performance of the system.

• Content delivery: Consistent hashing is used to map content to edge servers in a content delivery network (CDN). This helps ensure that content is served from the server closest to the user, reducing latency and improving the user experience.

• Database sharding: Consistent hashing is also used to shard data across multiple database servers, allowing for efficient distribution of data and improved performance. In this case, each shard is allocated to a particular server based on its hash value.

Simple java implementation

import java.util.*;

// Class representing consistent hashing
public class ConsistentHashing {
    private final TreeMap<Integer, String> circle = new TreeMap<>(); // TreeMap to store hashed nodes
    private final int numVirtualNodes; // Number of virtual nodes per physical node

    // Constructor to initialize consistent hashing with the number of virtual nodes
    public ConsistentHashing(int numVirtualNodes) {
        this.numVirtualNodes = numVirtualNodes;
    }

    // Method to add a node to the consistent hashing ring
    public void addNode(String node) {
        // Add virtual nodes for the given physical node
        for (int i = 0; i < numVirtualNodes; i++) {
            String virtualNode = node + "#" + i; // Create a virtual node with an index
            int hash = getHash(virtualNode); // Get hash value for the virtual node
            circle.put(hash, node); // Put the virtual node in the TreeMap with its hash value
        }
    }

    // Method to remove a node from the consistent hashing ring
    public void removeNode(String node) {
        // Remove virtual nodes associated with the given physical node
        for (int i = 0; i < numVirtualNodes; i++) {
            String virtualNode = node + "#" + i; // Create a virtual node with an index
            int hash = getHash(virtualNode); // Get hash value for the virtual node
            circle.remove(hash); // Remove the virtual node from the TreeMap
        }
    }

    // Method to get the node responsible for a given key
    public String getNode(String key) {
        if (circle.isEmpty()) {
            return null; // Return null if the circle is empty
        }
        int hash = getHash(key); // Get hash value for the key
        if (!circle.containsKey(hash)) {
            // If the hash value is not in the TreeMap, find the closest succeeding node
            SortedMap<Integer, String> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash); // Return the node responsible for the key
    }

    // Method to get the hash value for a string
    private int getHash(String key) {
        // Use a simple hashing algorithm (e.g., Java's hashCode() function)
        return key.hashCode(); // Return the hash value of the key
    }

    // Main method to test the consistent hashing implementation
    public static void main(String[] args) {
        ConsistentHashing consistentHashing = new ConsistentHashing(3); // Create consistent hashing with 3 virtual nodes per physical node
        consistentHashing.addNode("Node1"); // Add physical nodes to the consistent hashing ring
        consistentHashing.addNode("Node2");
        consistentHashing.addNode("Node3");

        // Test keys and get the corresponding nodes
        String[] keys = {"Key1", "Key2", "Key3", "Key4", "Key5"};
        for (String key : keys) {
            String node = consistentHashing.getNode(key); // Get the node responsible for the key
            System.out.println("Key: " + key + ", Node: " + node); // Print the key and corresponding node
        }
    }
}

2. Bloom Filters

A Bloom filter is a probabilistic data structure that is used to test whether an element is a member of a set or not 1. It works by hashing elements and setting the corresponding bits in an array of bits. When testing if an element is in the set, the Bloom filter hashes the element and checks if all of the corresponding bits in the array are set. If any of the bits are not set, then the element is not in the set. However, if all of the bits are set, the element may or may not be in the set, as there could have been a collision with another element that set the same bits.

Bloom filters have a high space efficiency as they require relatively small amounts of memory compared to other data structures, such as hash tables or binary search trees. They are also very fast in terms of insertion and search time, with constant time complexity. However, they have a trade-off in terms of the number of false positives, which is the probability that a Bloom filter will incorrectly identify an element as being in the set when it is not. The probability of false positives can be controlled by adjusting the size of the Bloom filter and the number of hash functions used.

Bloom filters are commonly used in various applications, including:

• Spell checkers: Bloom filters can be used to quickly check if a word is in a dictionary, reducing the need to search through the entire dictionary word by word.

• Network routers and firewalls: Bloom filters can be used to store information about the network traffic, such as the IP addresses of known malware or spam sources, and quickly identify if incoming traffic is from a known source.

• Databases and search engines: Bloom filters can be used to pre-filter candidate records or documents to avoid expensive disk access and CPU processing.

• Web browsers: Bloom filters can be used to store information about visited URLs for fast phishing and malware detection.

Java simple implementation

import java.util.BitSet;
import java.util.Random;

// Bloom Filter class
public class BloomFilter {
    private BitSet bitSet; // BitSet to store the filter
    private int size; // Size of the filter
    private int[] hashes; // Array to store hash values
    private int numHashes; // Number of hash functions

    // Constructor to initialize the Bloom Filter with the given size and number of hash functions
    public BloomFilter(int size, int numHashes) {
        this.size = size;
        this.numHashes = numHashes;
        bitSet = new BitSet(size); // Initialize the BitSet with the given size
        hashes = new int[numHashes]; // Initialize the array for hash values
    }

    // Method to add an element to the Bloom Filter
    public void add(String value) {
        for (int i = 0; i < numHashes; i++) {
            int hash = hash(value, i); // Compute the hash value for the element
            bitSet.set(hash % size, true); // Set the corresponding bit in the BitSet
        }
    }

    // Method to check if an element might be in the Bloom Filter
    public boolean contains(String value) {
        for (int i = 0; i < numHashes; i++) {
            int hash = hash(value, i); // Compute the hash value for the element
            if (!bitSet.get(hash % size)) {
                return false; // If any of the corresponding bits is not set, the element is not in the filter
            }
        }
        return true; // If all corresponding bits are set, the element might be in the filter
    }

    // Method to compute the hash value for an element using a specific hash function
    private int hash(String value, int index) {
        // Use a simple hashing algorithm (e.g., Java's hashCode() function)
        // You may use more sophisticated hash functions depending on your requirements
        return value.hashCode() + index; // Add index to avoid collisions for different hash functions
    }

    // Main method to test the Bloom Filter implementation
    public static void main(String[] args) {
        BloomFilter bloomFilter = new BloomFilter(100, 3); // Create a Bloom Filter with size 100 and 3 hash functions
        // Add some elements to the Bloom Filter
        bloomFilter.add("apple");
        bloomFilter.add("banana");
        bloomFilter.add("orange");
        // Check if elements might be in the Bloom Filter
        System.out.println("Contains 'apple': " + bloomFilter.contains("apple")); // true
        System.out.println("Contains 'grape': " + bloomFilter.contains("grape")); // false
    }
}

3. Skip Lists

Skip lists are a type of probabilistic data structure, similar to a multilevel linked list, that can efficiently search, insert, and delete elements in a sorted sequence. They are designed to have an average search, insertion, and deletion time complexity of O(log n), making them a suitable alternative to balanced trees in some cases.

Skip lists allow for efficient searching by adding multiple levels of links between nodes, with the lower levels acting as shortcuts to higher levels. The linking between levels is done randomly, so that each element has a probability of appearing at each level, with higher levels having progressively smaller probabilities. This randomness helps ensure that the skip list stays balanced on average, even as elements are added or removed.

Skip lists are used in a variety of applications, including databases, game programming, and network routing. They are particularly well-suited for applications that require fast search times and frequent insertions, and may be a better choice than balanced trees in situations where the cost of rebalancing becomes prohibitive. However, because they rely on randomness, their performance can be difficult to predict precisely, and they may not be as suitable for applications that require very tight control over performance characteristics.

Simple java implementation

import java.util.Random;

// Class representing a node in the Skip List
class SkipListNode {
    int value; // Value stored in the node
    SkipListNode[] next; // Array to store pointers to next nodes at different levels

    // Constructor to initialize a node with a given value and number of levels
    public SkipListNode(int value, int level) {
        this.value = value;
        this.next = new SkipListNode[level + 1]; // Initialize the array of pointers
    }
}

// Class representing the Skip List
public class SkipList {
    private final Random random; // Random number generator
    private final int maxHeight; // Maximum height of the Skip List
    private SkipListNode head; // Head node of the Skip List

    // Constructor to initialize the Skip List with a given maximum height
    public SkipList(int maxHeight) {
        this.random = new Random();
        this.maxHeight = maxHeight;
        this.head = new SkipListNode(Integer.MIN_VALUE, maxHeight); // Initialize the head node
    }

    // Method to insert a value into the Skip List
    public void insert(int value) {
        // Generate a random height for the new node
        int height = getRandomHeight();
        // Create a new node with the given value and random height
        SkipListNode newNode = new SkipListNode(value, height);
        // Update pointers at each level to insert the new node into the Skip List
        for (int i = 0; i <= height; i++) {
            newNode.next[i] = head.next[i];
            head.next[i] = newNode;
        }
    }

    // Method to search for a value in the Skip List
    public boolean search(int value) {
        // Start from the top level and traverse down to find the value
        SkipListNode current = head;
        for (int i = maxHeight; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].value < value) {
                current = current.next[i];
            }
            if (current.next[i] != null && current.next[i].value == value) {
                return true; // Value found
            }
        }
        return false; // Value not found
    }

    // Method to generate a random height for a new node
    private int getRandomHeight() {
        int height = 0;
        // Generate a random height until it is less than the maximum height
        while (random.nextDouble() < 0.5 && height < maxHeight) {
            height++;
        }
        return height;
    }

    // Method to print the contents of the Skip List
    public void print() {
        for (int i = maxHeight; i >= 0; i--) {
            SkipListNode current = head.next[i];
            System.out.print("Level " + i + ": ");
            while (current != null) {
                System.out.print(current.value + " ");
                current = current.next[i];
            }
            System.out.println();
        }
    }

    // Main method to test the Skip List implementation
    public static void main(String[] args) {
        SkipList skipList = new SkipList(4); // Create a Skip List with maximum height 4
        // Insert some values into the Skip List
        skipList.insert(3);
        skipList.insert(6);
        skipList.insert(7);
        skipList.insert(9);
        skipList.insert(12);
        skipList.insert(19);
        skipList.insert(17);
        skipList.insert(26);
        skipList.insert(21);
        skipList.insert(25);
        // Print the contents of the Skip List
        skipList.print();

        // Search for values in the Skip List
        System.out.println("Search for 17: " + skipList.search(17)); // true
        System.out.println("Search for 30: " + skipList.search(30)); // false
    }
}

4. B-Tree

A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient search, insertion, and deletion operations in logarithmic time. Unlike other self-balancing binary search trees, B-trees have the ability to deal with much larger data sets and are commonly used in storage systems such as databases and file systems. They generalize binary search trees by allowing nodes to have more than two children and have a fixed maximum size, referred to as the order, which determines the number of keys that can be stored in each node.

In a B-tree, internal nodes can have a variable number of child nodes within an ordered range, with each node storing keys and pointers to other nodes. The keys within a node are ordered, and the pointers are used to navigate between nodes during search operations. At the leaf level, actual data is stored in sorted order.

B-trees are designed to maintain balance, which ensures efficient search operations, and they achieve this through a process of node splitting and merging. When a new key is inserted, or a key is removed, the B-tree is rebalanced so that the number of levels in the tree remains relatively constant.

B-trees have logarithmic time complexity for search, insertion, and deletion operations, which makes them a popular choice for applications that require quick access to large data sets. They are also used extensively in modern database systems to provide fast indexing and querying capabilities.

Btree java implementation

import java.util.ArrayList;
import java.util.List;

// Class representing a node in the B-Tree
class BTreeNode {
    int[] keys; // Array to store keys
    int t; // Minimum degree (defines the range for number of keys)
    BTreeNode[] children; // Array to store child pointers
    int numKeys; // Current number of keys in the node
    boolean leaf; // Flag to indicate if the node is a leaf

    // Constructor to initialize a node
    public BTreeNode(int t, boolean leaf) {
        this.t = t;
        this.leaf = leaf;
        this.keys = new int[2 * t - 1];
        this.children = new BTreeNode[2 * t];
        this.numKeys = 0;
    }
}

// Class representing the B-Tree
public class BTree {
    private BTreeNode root; // Root node of the B-Tree
    private int t; // Minimum degree of the B-Tree

    // Constructor to initialize the B-Tree with a given minimum degree
    public BTree(int t) {
        this.t = t;
        root = new BTreeNode(t, true); // Create a new root node
    }

    // Method to insert a key into the B-Tree
    public void insert(int key) {
        if (root.numKeys == 2 * t - 1) {
            BTreeNode newRoot = new BTreeNode(t, false); // Create a new root node
            newRoot.children[0] = root; // Make the old root as child of the new root
            splitChild(newRoot, 0); // Split the old root and move 1 key to the new root
            insertNonFull(newRoot, key); // Insert the key into the B-Tree with the new root
            root = newRoot; // Update the root of the B-Tree
        } else {
            insertNonFull(root, key); // Insert the key into the B-Tree with the current root
        }
    }

    // Method to insert a key into a non-full B-Tree node
    private void insertNonFull(BTreeNode node, int key) {
        int i = node.numKeys - 1; // Start from the rightmost key
        if (node.leaf) {
            // If the node is a leaf, find the correct position for the new key
            while (i >= 0 && key < node.keys[i]) {
                node.keys[i + 1] = node.keys[i];
                i--;
            }
            // Insert the new key at the correct position
            node.keys[i + 1] = key;
            node.numKeys++; // Increase the number of keys in the node
        } else {
            // If the node is not a leaf, find the child to insert the new key
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;
            if (node.children[i].numKeys == 2 * t - 1) {
                // If the child is full, split it
                splitChild(node, i);
                if (key > node.keys[i]) {
                    i++;
                }
            }
            // Insert the new key into the appropriate child node
            insertNonFull(node.children[i], key);
        }
    }

    // Method to split a full child of a B-Tree node
    private void splitChild(BTreeNode parent, int childIndex) {
        BTreeNode child = parent.children[childIndex];
        BTreeNode newChild = new BTreeNode(t, child.leaf);
        newChild.numKeys = t - 1;
        for (int i = 0; i < t - 1; i++) {
            newChild.keys[i] = child.keys[i + t];
        }
        if (!child.leaf) {
            for (int i = 0; i < t; i++) {
                newChild.children[i] = child.children[i + t];
            }
        }
        child.numKeys = t - 1;
        for (int i = parent.numKeys; i > childIndex; i--) {
            parent.children[i + 1] = parent.children[i];
        }
        parent.children[childIndex + 1] = newChild;
        for (int i = parent.numKeys - 1; i >= childIndex; i--) {
            parent.keys[i + 1] = parent.keys[i];
        }
        parent.keys[childIndex] = child.keys[t - 1];
        parent.numKeys++;
    }

    // Method to search for a key in the B-Tree
    public boolean search(int key) {
        return search(root, key);
    }

    // Method to search for a key in a B-Tree node
    private boolean search(BTreeNode node, int key) {
        int i = 0;
        while (i < node.numKeys && key > node.keys[i]) {
            i++;
        }
        if (i < node.numKeys && key == node.keys[i]) {
            return true; // Key found in the current node
        }
        if (node.leaf) {
            return false; // Key not found in the leaf node
        }
        // Recursively search for the key in the appropriate child node
        return search(node.children[i], key);
    }

    // Method to print the contents of the B-Tree
    public void print() {
        print(root, "");
    }

    // Method to print the contents of a B-Tree node
    private void print(BTreeNode node, String prefix) {
        System.out.print(prefix); // Print the current prefix
        for (int i = 0; i < node.numKeys; i++) {
            System.out.print(node.keys[i] + " "); // Print the keys in the current node
        }
        System.out.println();
        if (!node.leaf) {
            for (int i = 0; i <= node.numKeys; i++) {
                print(node.children[i], prefix + "  "); // Recursively print the child nodes
            }
        }
    }

    // Main method to test the B-Tree implementation
    public static void main(String[] args) {
        BTree tree = new BTree(3); // Create a B-Tree with minimum degree 3
        // Insert some keys into the B-Tree
        tree.insert(1);
        tree.insert(3);
        tree.insert(7);
        tree.insert(10);
        tree.insert(11);
        tree.insert(13);
        tree.insert(14);
        tree.insert(15);
        tree.insert(18);
        tree.insert(16);
        tree.insert(19);
        tree.insert(24);
        tree.insert(25);
        tree.insert(26);
        tree.insert(21);
        tree.insert(4);
        tree.insert(5);
        tree.insert(20);
        tree.insert(22);
        tree.insert(2);
        tree.insert(17);
        // Print the contents of the B-Tree
        tree.print();

        // Search for keys in the B-Tree
        System.out.println("Search for 4: " + tree.search(4)); // true
        System.out.println("Search for 8: " + tree.search(8)); // false
    }
}

A B+ tree is an extended version of a B-tree, where each non-leaf node contains a fixed number(m) of pointers to child nodes(m-ways). The B+ tree has better performance compared to binary search trees and B-trees when searching and inserting data. The B+ tree is often used in databases and file systems where the data is stored in external storage. In a B+ tree, all the data is stored in the leaf node, whereas the internal nodes only store index keys. The leaf nodes are linked, and a sequential access can be made along the leaf nodes. Because of its many pointers, the B+ tree has good space utilization, as well as good performance for range queries. It is also self-balancing to ensure that the time complexity for searching, insertion, and deletion is logarithmic in most cases.

B+ tree

import java.util.LinkedList;
import java.util.Queue;

// Node class representing a node in the B+ tree
class BPlusTreeNode {
    int[] keys; // Array to store keys
    BPlusTreeNode[] children; // Array to store child pointers
    int numKeys; // Current number of keys in the node
    boolean leaf; // Flag to indicate if the node is a leaf
    BPlusTreeNode next; // Pointer to the next leaf node

    // Constructor to initialize a node with a given degree and leaf status
    public BPlusTreeNode(int degree, boolean leaf) {
        this.keys = new int[2 * degree - 1];
        this.children = new BPlusTreeNode[2 * degree];
        this.numKeys = 0;
        this.leaf = leaf;
        this.next = null;
    }
}

// B+ tree class
public class BPlusTree {
    private BPlusTreeNode root; // Root node of the tree
    private int degree; // Degree of the tree

    // Constructor to initialize the B+ tree with a given degree
    public BPlusTree(int degree) {
        this.degree = degree;
        this.root = new BPlusTreeNode(degree, true); // Initialize the root as a leaf node
    }

    // Method to insert a key into the B+ tree
    public void insert(int key) {
        if (root.numKeys == 2 * degree - 1) {
            // If the root is full, split it and create a new root
            BPlusTreeNode newRoot = new BPlusTreeNode(degree, false);
            newRoot.children[0] = root;
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, key);
    }

    // Method to recursively insert a key into a non-full node
    private void insertNonFull(BPlusTreeNode node, int key) {
        int i = node.numKeys - 1;
        if (node.leaf) {
            // If the node is a leaf, insert the key into its sorted position
            while (i >= 0 && key < node.keys[i]) {
                node.keys[i + 1] = node.keys[i];
                i--;
            }
            node.keys[i + 1] = key;
            node.numKeys++;
        } else {
            // If the node is not a leaf, find the child to insert the key
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;
            if (node.children[i].numKeys == 2 * degree - 1) {
                // If the child is full, split it
                splitChild(node, i);
                if (key > node.keys[i]) {
                    i++;
                }
            }
            insertNonFull(node.children[i], key);
        }
    }

    // Method to split a full child node
    private void splitChild(BPlusTreeNode parent, int childIndex) {
        BPlusTreeNode child = parent.children[childIndex];
        BPlusTreeNode newChild = new BPlusTreeNode(degree, child.leaf);
        newChild.numKeys = degree - 1;
        for (int i = 0; i < degree - 1; i++) {
            newChild.keys[i] = child.keys[i + degree];
        }
        if (!child.leaf) {
            for (int i = 0; i < degree; i++) {
                newChild.children[i] = child.children[i + degree];
            }
        }
        child.numKeys = degree - 1;
        for (int i = parent.numKeys; i > childIndex; i--) {
            parent.children[i + 1] = parent.children[i];
        }
        parent.children[childIndex + 1] = newChild;
        for (int i = parent.numKeys - 1; i >= childIndex; i--) {
            parent.keys[i + 1] = parent.keys[i];
        }
        parent.keys[childIndex] = child.keys[degree - 1];
        parent.numKeys++;
    }

    // Method to search for a key in the B+ tree
    public boolean search(int key) {
        return search(root, key);
    }

    // Method to recursively search for a key in the B+ tree
    private boolean search(BPlusTreeNode node, int key) {
        int i = 0;
        while (i < node.numKeys && key > node.keys[i]) {
            i++;
        }
        if (i < node.numKeys && key == node.keys[i]) {
            return true;
        }
        if (node.leaf) {
            return false;
        }
        return search(node.children[i], key);
    }

    // Method to print the B+ tree
    public void print() {
        print(root, "");
    }

    // Method to recursively print a node and its children in the B+ tree
    private void print(BPlusTreeNode node, String prefix) {
        System.out.print(prefix);
        for (int i = 0; i < node.numKeys; i++) {
            System.out.print(node.keys[i] + " ");
        }
        System.out.println();
        if (!node.leaf) {
            for (int i = 0; i <= node.numKeys; i++) {
                print(node.children[i], prefix + "  ");
            }
        }
    }

    // Main method to test the B+ tree implementation
    public static void main(String[] args) {
        BPlusTree bPlusTree = new BPlusTree(3); // Create a B+ tree with degree 3
        // Insert some keys into the B+ tree
        bPlusTree.insert(1);
        bPlusTree.insert(3);
        bPlusTree.insert(7);
        bPlusTree.insert(10);
        bPlusTree.insert(11);
        bPlusTree.insert(13);
        bPlusTree.insert(14);
        bPlusTree.insert(15);
        bPlusTree.insert(18);
        bPlusTree.insert(16);
        bPlusTree.insert(19);
        bPlusTree.insert(24);
        bPlusTree.insert(25);
        bPlusTree.insert(26);
        bPlusTree.insert(21);
        bPlusTree.insert(4);
        bPlusTree.insert(5);
        bPlusTree.insert(20);
        bPlusTree.insert(22);
        bPlusTree.insert(2);
        bPlusTree.insert(17);
        // Print the B+ tree
        bPlusTree.print();

        // Search for keys in the B+ tree
        System.out.println("Search for 4: " + bPlusTree.search(4)); // true
        System.out.println("Search for 8: " + bPlusTree.search(8)); // false
    }
}

5. LRU and LFU

In a typical LRU implementation, you maintain a map of key-value pairs and a linked list of keys in the order of their access. Whenever an item is accessed, you move its corresponding key to the head of the list. If you need to evict an item due to capacity constraints, you simply remove the least recently accessed item from the tail of the list.

LFU eviction policy can be implemented using a combination of a hash map and a priority queue. In this implementation, you maintain a hash map of key-value pairs and a priority queue of entries ordered by the least frequency of usage. Whenever an entry is accessed, you increment its usage count and update its position in the priority queue. If you need to evict an item due to capacity constraints, you simply remove the least frequently used item from the head of the priority queue

The choice between LRU and LFU eviction policies depends on the specific use case and access patterns of the cache. LRU is typically a good choice when you have a large cache with high locality of reference, i.e., the most recently accessed items are likely to be accessed again in the near future. LFU is a good choice when you have a small cache with many frequently accessed items that you want to keep in memory at all times. However, there are many variations of both eviction policies, and other policies such as LRU-K and Adaptive Replacement Cache (ARC) that combine the benefits of both LRU and LFU policies.

import java.util.LinkedHashMap;
import java.util.Map;

// LRU Cache class
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity; // Capacity of the cache

    // Constructor to initialize the LRU cache with a given capacity
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true); // Set access order to true for LRU behavior
        this.capacity = capacity;
    }

    // Method to check if the cache contains a key
    @Override
    public boolean containsKey(Object key) {
        return super.containsKey(key);
    }

    // Method to get the value of a key in the cache
    @Override
    public V get(Object key) {
        return super.getOrDefault(key, null);
    }

    // Method to put a key-value pair into the cache
    @Override
    public V put(K key, V value) {
        return super.put(key, value);
    }

    // Method to remove the least recently used entry if the cache is full
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    // Method to print the contents of the cache (for debugging)
    public void printCache() {
        System.out.println("LRU Cache: " + super.toString());
    }

    // Main method to test the LRU cache implementation
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2); // Create an LRU cache with capacity 2
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.printCache(); // Output: LRU Cache: {1=One, 2=Two}

        System.out.println("Get key 1: " + cache.get(1)); // Output: Get key 1: One
        cache.printCache(); // Output: LRU Cache: {2=Two, 1=One}

        cache.put(3, "Three");
        cache.printCache(); // Output: LRU Cache: {1=One, 3=Three}
        
        System.out.println("Get key 2: " + cache.get(2)); // Output: Get key 2: null
    }
}

import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

// LFU Cache class
public class LFUCache<K, V> {
    private final int capacity; // Capacity of the cache
    private final Map<K, V> cache; // Map to store key-value pairs
    private final Map<K, Integer> counts; // Map to store frequency counts of keys
    private final Map<Integer, Set<K>> frequencyMap; // Map to store keys grouped by frequency
    private int minFrequency; // Minimum frequency among all keys

    // Constructor to initialize the LFU cache with a given capacity
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.counts = new HashMap<>();
        this.frequencyMap = new HashMap<>();
        this.minFrequency = 0;
    }

    // Method to get the value of a key in the cache
    public V get(K key) {
        if (!cache.containsKey(key)) {
            return null; // Key not found in the cache
        }
        int count = counts.get(key); // Get the current frequency count of the key
        counts.put(key, count + 1); // Increment the frequency count
        frequencyMap.get(count).remove(key); // Remove the key from its current frequency group
        if (count == minFrequency && frequencyMap.get(count).isEmpty()) {
            minFrequency++; // Update the minimum frequency if necessary
        }
        frequencyMap.putIfAbsent(count + 1, new LinkedHashSet<>()); // Create a new frequency group if necessary
        frequencyMap.get(count + 1).add(key); // Add the key to its new frequency group
        return cache.get(key); // Return the value of the key
    }

    // Method to put a key-value pair into the cache
    public void put(K key, V value) {
        if (capacity <= 0) {
            return; // Cache capacity is 0 or negative, do nothing
        }
        if (cache.containsKey(key)) {
            cache.put(key, value); // Update the value of the existing key
            get(key); // Increment the frequency count of the key
            return;
        }
        if (cache.size() >= capacity) {
            K evictKey = frequencyMap.get(minFrequency).iterator().next(); // Get the least frequently used key
            cache.remove(evictKey); // Remove the least frequently used key from the cache
            counts.remove(evictKey); // Remove the corresponding frequency count
            frequencyMap.get(minFrequency).remove(evictKey); // Remove the key from its frequency group
        }
        cache.put(key, value); // Put the new key-value pair into the cache
        counts.put(key, 1); // Set the frequency count of the new key to 1
        minFrequency = 1; // Reset the minimum frequency to 1
        frequencyMap.putIfAbsent(1, new LinkedHashSet<>()); // Create a new frequency group for the new key
        frequencyMap.get(1).add(key); // Add the new key to its frequency group
    }

    // Method to print the contents of the cache (for debugging)
    public void printCache() {
        System.out.println("LFU Cache: " + cache.toString());
    }

    // Main method to test the LFU cache implementation
    public static void main(String[] args) {
        LFUCache<Integer, String> cache = new LFUCache<>(2); // Create an LFU cache with capacity 2
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.printCache(); // Output: LFU Cache: {1=One, 2=Two}

        System.out.println("Get key 1: " + cache.get(1)); // Output: Get key 1: One
        cache.printCache(); // Output: LFU Cache: {2=Two, 1=One}

        cache.put(3, "Three");
        cache.printCache(); // Output: LFU Cache: {1=One, 3=Three}
        
        System.out.println("Get key 2: " + cache.get(2)); // Output: Get key 2: null
    }
}