1、LinkedHashMap

• 在HashMap的基础上维护元素的添加顺序，使得遍历的结果是遵从添加顺序的
  假设添加顺序是37、21、31、41、97、95、52、42、83
  
• 删除度为2的节点node时
  需要注意更换node与 前驱\后继节点 的连接位置

1.1、代码实现：

这里要实现LinkedHashMap，则继承HashMap，因为是需要一个链表将所有红黑树的节点进行链接，而且这个链表还需要是一个双向链表，那么之前的HashMap里的Node类里的属性是不够的，因此需要重新第一个子类的Node。

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    
    private static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;
        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}

HashMap里面的put方法里Node节点是写死的，这里还需要特殊处理一下：

public class HashMap<K, V> implements Map<K, V> {
    public V put(K key, V value) {
        ......
        if(root == null) {
            root = createNode(key, value, null);
            table[index] = root;//放入桶中
            size++;
            afterPut(root);// 修复红黑树的性质
            return null;
        }
        ......

        // 看看插入到父节点的哪个位置
        Node<K, V> newNode = createNode(key, value, parent);
        ......
        return null;
    }
     
     protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        return new Node<>(key, value, parent);
    }
}

然后在LinkedHashMap类里重写createNode方法

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;
    
    @Override
    public void clear() {
        super.clear();
        first = null;
        last = null;
    }
    
    @Override
    protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
        LinkedNode node = new LinkedNode(key, value, parent);
        if(first == null) {// 新添加节点
            first = last = node;
        }else {
            last.next = node;// 新节点添加到已有到后面
            node.prev = last;// 指定新节点前驱节点
            last = node;// 更新最后一个节点
        }
        return node;
    }
    
    private static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;
        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}

1.1.1、遍历实现

这里的遍历需要通过链表进行遍历了

public void traversal(Visitor<K, V> visitor) {
    if (visitor == null) return;
    LinkedNode<K, V> node = first;
    while (node != null) {
        if(visitor.visit(node.key, node.value)) return;
        node = node.next;
    }
}

1.1.2、删除操作

如果在删除的时候 ，直接重写HashMap的afterRemove方法是不合理的，因为有下面三方面原因：
1. afterRemove方法是专门用来处理红黑树的。
2. remove方法里并不是每个地方(例如删除的是根节点)都调用了afterRemove方法。
3. afterRemove方法传递的参数并不一定都是被删除节点。
所以这里可以重写remove方法:

protected V remove(Node<K, V> node) {
    if(node == null) return null;
    LinkedNode<K, V> linkedNode = (LinkedNode<K, V>) node;
    
    LinkedNode<K, V> prev = linkedNode.prev;
    LinkedNode<K, V> next = linkedNode.next;
    if(prev == null) {// 被删除节点是头节点
        first = next;
    }else {
        prev.next = next;
    }
    
    if(next == null) {// 被删除节点是尾节点
        last = prev;
    }else {
        next.prev = prev;
    }
    return super.remove(node);
}

上面的删除逻辑如果是删除节点是度为2的就会有问题了，因为度为2的删除的逻辑是找的它的后继节点，然后替换掉，最后在删除它的后继节点。

• 删除度为2的节点node时（比如删除31）

  • 需要注意更换 node 与 前驱\后继节点 的连接位置

    
    image.png

那么这样的话重写remove方法就不适合了。因为afterRemove方法是专门用来处理红黑树的，所以这里将名称修改为fixAfterRemove。

public class HashMap<K, V> implements Map<K, V> {
    
    private V remove(Node<K, V> node) {
        if (node == null) return null;
        
        Node<K, V> willNode = node;
        
        ......
        
        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                table[index] = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }
            
            // 删除节点之后的处理
            fixAfterRemove(replacement);
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            table[index] = null;
        } else { // node是叶子节点，但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
            
            // 删除节点之后的处理
            fixAfterRemove(node);
        }
        
        // 交给子类去处理
        afterRemove(willNode, node);
        return oldValue;
    }
     /**
     * @param willNode 本来想删除的节点
     * @param removedNode 真正删除的节点
     */
    protected void afterRemove(Node<K, V> willNode, Node<K, V> removedNode) { }
}

public class LinkedHashMap<K, V> extends HashMap<K, V> {
    ......
    @Override
    protected void afterRemove(Node<K, V> willNode ,Node<K, V> removedNode) {
        LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
        LinkedNode<K, V> node2 = (LinkedNode<K, V>) removedNode;
        
        if(node1 != node2) {// 度为2的节点
            //  交换linkedWillNode和linkedRemovedNode在链表中的位置
            // 交换prev
            LinkedNode<K, V> tmp = node1.prev;
            node1.prev = node2.prev;
            node2.prev = tmp;
            if (node1.prev == null) {
                first = node1;
            } else {
                node1.prev.next = node1;
            }
            if (node2.prev == null) {
                first = node2;
            } else {
                node2.prev.next = node2;
            }
            
            // 交换next
            tmp = node1.next;
            node1.next = node2.next;
            node2.next = tmp;
            if (node1.next == null) {
                last = node1;
            } else {
                node1.next.prev = node1;
            }
            if (node2.next == null) {
                last = node2;
            } else {
                node2.next.prev = node2;
            }
        }
        
        LinkedNode<K, V> prev = node2.prev;
        LinkedNode<K, V> next = node2.next;
        if(prev == null) {// 被删除节点是头节点
            first = next;
        }else {
            prev.next = next;
        }
        
        if(next == null) {// 被删除节点是尾节点
            last = prev;
        }else {
            next.prev = prev;
        }
    }
 
     ......
}

1.1.3、containsValue方法

public boolean containsValue(V value) {
    LinkedNode<K, V> node = first;
    while (node != null) {
        if (Objects.equals(value, node.value)) return true;
        node = node.next;
    }
    return false;
}

2、HashSet实现

利用HashMap来实现HashSet

public class HashSet<E> implements Set<E> {
    private HashMap<E, Object> map = new HashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E element) {
        return map.containsKey(element);
    }

    @Override
    public void add(E element) {
        map.put(element, null);
    }

    @Override
    public void remove(E element) {
        map.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}

3、LinkedHashSet实现

利用LinkedHashMap来实现LinkedHashSet

public class LinkedHashSet<E> implements Set<E> {
    private LinkedHashMap<E, Object> map = new LinkedHashMap<>();

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public void clear() {
        map.clear();
    }

    @Override
    public boolean contains(E element) {
        return map.containsKey(element);
    }

    @Override
    public void add(E element) {
        map.put(element, null);
    }

    @Override
    public void remove(E element) {
        map.remove(element);
    }

    @Override
    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}