java-集合类学习

LinkedHashMap

A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order).
This kind of map is well-suited to building LRU caches. Invoking the put, putIfAbsent, get, getOrDefault, compute, computeIfAbsent, computeIfPresent, or merge methods results in an access to the corresponding entry (assuming it exists after the invocation completes). The replace methods only result in an access of the entry if the value is replaced.

这里的注释说了 , 由于特殊的构造方法可以使得初始化进来的map 可以保持当初的位置, 这个特点, 让 LinkedHashMap 非常适合实现 LRU caches

LinkedHashMap 继承 HashMap , 同时重写了 newNode 方法 , LinkedHashMap 本身没有 put 方法 , 使用的是父类 HashMap , 然后在 put 和 get 方法都使用前后双向链表连接 , 使得它可以知道元素的前后顺序 .

使用 LinkedHashMap 实现一个 LRU

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

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }

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

在LRUCache的构造函数中，调用了LinkedHashMap的构造函数并传入了三个参数：maxSize、0.75f和true。其中，maxSize表示缓存的最大容量，0.75f表示负载因子，true表示按照访问顺序排序。

在LRUCache中重写了removeEldestEntry方法，当LRUCache中的元素数量超过maxSize时，removeEldestEntry方法会返回true，从而触发LinkedHashMap自动移除最老的元素。

通过使用LRUCache类，可以方便地实现LRU缓存功能。例如，可以使用以下代码创建一个最大容量为10的LRU缓存：

LRUCache<String, String> cache = new LRUCache<>(10);

然后，可以使用put方法向缓存中添加元素，使用get方法从缓存中获取元素，LRUCache会自动维护缓存中元素的顺序。

TreeMap & TreeSet

TreeMap是有序的 ，就是外表表现的是一个 Map 但是是有序的 ， 看下面的例子学习一下

 public void test1 (){
        SortedMap<Integer, String> treeMap = new TreeMap<>();
        // 添加元素
        treeMap.put(3, "C");
        treeMap.put(1, "A");
        treeMap.put(4, "D");
        treeMap.put(2, "B");

        // 遍历元素
        for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }


运行方法后的结果 ： 
1: A
2: B
3: C
4: D

TreeMap查询写入的时间复杂度多少？其key对象为什么必须要实现Compare接口、如何用它实现一致性哈希

TreeMap 底层是红黑树 ， 所以他的平均时间复杂度为 O(log(n)) ，空间复杂度为 O(n) ，key对象为什么必须要实现Compare接口用于比较大小 ，方便插入到红黑树算法里面

一致性hash算法 ： 是一种将数据分布到多个节点的算法，它可以在节点的增减或者故障时，最小化数据的迁移量。一致性哈希算法的核心思想是将节点和数据都映射到一个环上，然后根据节点在环上的位置来划分数据的范围。

结题思路 ： 主要考虑它的增删改查

import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash<T> {
    private final SortedMap<Integer, T> circle = new TreeMap<>();
    private final HashFunction hashFunction;
    private final int numberOfReplicas;

    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Iterable<T> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;

        for (T node : nodes) {
            addNode(node);
        }
    }

    public void addNode(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = hashFunction.hash(node.toString() + i);
            circle.put(hash, node);
        }
    }

    public void removeNode(T node) {
        for (int i = 0; i < numberOfReplicas; i++) {
            int hash = hashFunction.hash(node.toString() + i);
            circle.remove(hash);
        }
    }

    public T get(Object key) {
        if (circle.isEmpty()) {
            return null;
        }

        int hash = hashFunction.hash(key.toString());
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, T> tailMap = circle.tailMap(hash);
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }

        return circle.get(hash);
    }

    public interface HashFunction {
        int hash(String key);
    }
}

参考资料