不吹牛，吃下我这篇，面试第一关算是过了（3）

上一篇 / 下一篇  2022-02-11 10:39:26

查看( 197 ) / 评论( 0 ) / 评分( 0 / 0 )
　　插入与扩容时机的变更
　　1.7 是先判断 put 的键值对是新增还是替换，如果是替换则直接替换，如果是新增会判断当前元素数量是否大于等于阈值，如果超过阈值且命中数组索引的位置已经有元素了，那么就进行扩容。
　　    if ((size >= threshold) && (null != table[bucketIndex])) {
　　        resize(2 * table.length);
　　        hash = (null != key) ? hash(key) : 0;
　　        bucketIndex = indexFor(hash, table.length);
　　    }
　　    createEntry(...)

　　所以 1.7 是先扩容，然后再插入。
　　而 1.8 则是先插入，然后再判断 size 是否大于阈值，若大于则扩容。
　　就这么个差别，至于为什么，好吧，我查了下没查出来，我自己也不知道，我个人觉得两者没差。。可能是重构(引入红黑树)的时候改了下顺序而已...其实没什么影响，我自己也脑补不出什么别的了。
　　网上也没找到什么比较有信服力的答案，所以如果有谁知道可以再教我一下。
　　HashMap 大概就这么些个点了，建议看下源码，再巩固一下。
　　LinkedHashMap
　　LinkedHashMap 的父类是 HashMap，所以 HashMap 有的它都有，然后基于 HashMap 做了一些扩展。
　　首先它把 HashMap 的 Entry 加了两个指针：before 和 after。
　　这目的已经很明显了，就是要把塞入的 Entry 之间进行关联，串成双向链表，如下图红色的就是新增的两个指针

　　并且内部还有个 accessOrder 成员，默认是 false， 代表链表是顺序是按插入顺序来排的，如果是 true 则会根据访问顺序来进行调整，就是咱们熟知的 LRU 那种，如果哪个节点访问了，就把它移到最后，代表最近访问的节点。
　　具体实现其实就是 HashMap 埋了几个方法，然后 LinkedHashMap 实现了这几个方法做了操作，比如以下这三个，从方法名就能看出了：访问节点之后干啥;插入节点之后干啥;删除节点之后干啥。
　　举个 afterNodeInsertion 的例子，它埋在 HashMap 的 put 里，在塞入新节点之后，会调用这个方法
　　然后 LinkedHashMap 实现了这个方法，可以看到这个方法主要用来移除最老的节点。
　　看到这你能想到啥?假如你想用 map 做个本地缓存，由于缓存的数量不可能无限大，所以你就能继承 LinkedHashMap 来实现，当节点超过一定数量的时候，在插入新节点的同时，移除最老最久没有被访问的节点，这样就实现了一个 LRU 了。
　　具体做法是把 accessOrder 设置为 true，这样每次访问节点就会把刚访问的节点移动到尾部，然后再重写 removeEldestEntry 方法，LinkedHashMap 默认的实现是直接返回 true。

　　你可以搞个：

　　 protected boolean removeEldestEntry(Entry<K, V> eldest) {
　　       return this.size() > this.maxCacheSize;
　　   }

　　这样就简单的实现一个 LRU 了!下面展示下完整的代码，非常简单：
　　    private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
　　        private final int maxCacheSize;
　　        LRUCache(int initialCapacity, int maxCacheSize) {
　　            super(initialCapacity, 0.75F, true);
　　            this.maxCacheSize = maxCacheSize;
　　        }
　　        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
　　            return this.size() > this.maxCacheSize;
　　        }
　　    }

　　这里还能引申出一个笔试题，手写实现一个 LRU 算法，来我给你写!
　　public class LRUCache<K,V> {
　　    class Node<K,V> {
　　        K key;
　　        V value;
　　        Node<K,V> prev, next;
　　        public Node(){}
　　        public Node(K key, V value) {
　　            this.key = key;
　　            this.value = value;
　　        }
　　    }
　　    private int capacity;
　　    private HashMap<K,Node> map;
　　    private Node<K,V> head;
　　    private Node<K,V> tail;
　　    public LRUCache(int capacity) {
　　        this.capacity = capacity;
　　        map = new HashMap<>(capacity);
　　        head = new Node<>();
　　        tail = new Node<>();
　　        head.next = tail;
　　        tail.prev = head;
　　    }
　　    public V get(K key) {
　　        Node<K,V> node = map.get(key);
　　        if (node == null) {
　　            return null;
　　        }
　　        moveNodeToHead(node);
　　        return node.value;
　　    }
　　    public void put(K key, V value) {
　　         Node<K,V> node = map.get(key);
　　       if (node == null) {
　　            if (map.size() >= capacity) {
　　                map.remove(tail.prev.key);
　　                removeTailNode();
　　            }
　　            Node<K,V> newNode = new Node<>(key, value);
　　            map.put(key, newNode);
　　            addToHead(newNode);
　　        } else {
　　            node.value = value;
　　            moveNodeToHead(node);
　　        }
　　    }
　　    private void addToHead(Node<K,V> newNode) {
　　        newNode.prev = head;
　　        newNode.next = head.next;
　　        head.next.prev = newNode;
　　        head.next = newNode;
　　    }
　　    private void moveNodeToHead(Node<K,V> node) {
　　        removeNode(node);
　　        addToHead(node);
　　    }
　　    private void removeNode(Node<K,V> node) {
　　        node.prev.next = node.next;
　　        node.next.prev = node.prev;
　　    }
　　    private void removeTailNode() {
　　        removeNode(tail.prev);
　　    }
　　    public static void main(String[] args) {
　　        LRUCache<Integer,Integer> lruCache = new LRUCache<>(3);
　　        lruCache.put(1,1);
　　        lruCache.put(2,2);
　　        lruCache.put(3,3);
　　        lruCache.get(1);
　　        lruCache.put(4,4);
　　        System.out.println(lruCache); // toString 我就没贴了，代码太长了
　　    }
　　}

　　TreeMap
　　TreeMap 内部是通过红黑树实现的，可以让 key 的实现 Comparable 接口或者自定义实现一个 comparator 传入构造函数，这样塞入的节点就会根据你定义的规则进行排序。
　　这个用的比较少，我常用在跟**有关的时候，有些**需要根据字母序排，然后再拼接成字符串排序，在这个时候就可以把业务上的值统一都塞到 TreeMap 里维护，取出来就是有序的。
　　具体就不深入了，一般不会问太多。
　　IdentityHashMap
　　理解这个 map 的关键就在于它的名字 Identity，也就是它判断是否相等的依据不是靠 equals ，而是对象本身是否是它自己。
　　什么意思呢?
　　首先看它覆盖的 hash 方法：
　　可以看到，它用了个 System.identityHashCode(x)，而不是x.hashCode()。
　　而这个方法会返回原来默认的 hashCode 实现，不管对象是否重写了 hashCode 方法
　　默认的实现返回的值是：对象的内存地址转化成整数，是不是有点感觉了?
　　然后我们再看下它的 get 方法：
　　可以看到，它判断 key 是否相等并不靠 hash 值和 equals，而是直接用了 ==。
　　而 == 其实就是地址判断!
　　只有相同的对象进行 == 才会返回 true。
　　因此我们得知，IdentityHashMap 的中的 key 只认它自己(对象本身)。
　　即便你伪造个对象，就算值都相等也没用，put 进去 IdentityHashMap 只会多一个键值对，而不是替换，这就是 Identity 的含义。
　　比如以下代码，identityHashMap 会存在两个 Yes：
　　Map<String, String> identityHashMap = new IdentityHashMap<>();
　　identityHashMap.put(new Yes("1"), "1");
　　identityHashMap.put(new Yes("1"), "2");

　　这里眼尖的小伙伴发现，为什么返回值是tab[i+1]?
　　这是因为 IdentityHashMap 的存储方式有点不一样，它是将 value 存在 key 的后面。
　　认识到这就差不多了，具体不深入了，有兴趣的小伙伴们自行研究~
　　最后
　　集合认识这么多估计就差不多了，不过推荐自己看一遍源码，心里更有数点。

收藏 举报

TAG: 软件开发 Java

 

评分：0

我来说两句

Open Toolbar