Java类源码学习(2)-HashMap-2

本文是上一篇的继续，补全HashMap剩余部分源码

主要是KeySet实现以及一些java8特性方法签名（实现省略了）

    /**
     * 返回键值集合的一个视图
     * 
     * <pre>
     * 实际是实现key集合的一个引用迭代子，HashMap本身的变更可以在keySet中直接反映出来
     * 
     * 如果HashMap在keySet在遍历过程中发生改变（keySet本身的remove除外），则遍历会失败（fast-fail）
     * 
     * 注意keySet不是一个全功能的java.util.Set的实现，仅支持remove、removeAll、retainAll、clear，不支持add、addAll
     * 如果调用add，会抛出UnsupportedOperationException，参见AbstracCollection.add()
     */
    @Override
    public Set<K> keySet() {
        Set<K> ks;
        // 实际返回的就是KeySet，这里判断下只是实现lazy load
        return (ks = keySet) == null ? (keySet = new KeySet()) : ks;
    }

    /**
     * keySet实现内嵌类，基于HashMap本身的。注意不是全功能的set
     */
    final class KeySet extends AbstractSet<K> {

        // 大部分支持的操作直接调用HashMap对应方法
        @Override
        public final int size() {
            return size;
        }

        @Override
        public final void clear() {
            HashMap.this.clear();
        }

        @Override
        public final boolean contains(Object o) {
            return containsKey(o);
        }

        @Override
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }

        /**
         * java8新增的Collection方法实现
         */
        @Override
        public final void forEach(Consumer<? super K> action) {
            Node<K, V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K, V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }

                // 这步是fast-fail特性，这里相当于乐观锁。操作过程中不发生结构变更，才认为才做有效
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        // 迭代子

        @Override
        public final Iterator<K> iterator() {
            return new KeyIterator();
        }

        @Override
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }

    }

    @Override
    public Collection<V> values() {
    }

    final class Values extends AbstractCollection<V> {
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
    }

    final class EntrySet extends AbstractSet<Map.Entry<K, V>> {
    }

    // java8 的Map default方法的重写，未注释的方法含义都是自明////////////////////////

    @Override
    public V getOrDefault(Object key, V defaultValue) {
    }

    @Override
    public V putIfAbsent(K key, V value) {
    }

    /**
     * key和value都匹配时删除
     */
    @Override
    public boolean remove(Object key, Object value) {
    }

    /**
     * key和value都匹配时，替换为newValue
     */
    @Override
    public boolean replace(K key, V oldValue, V newValue) {
    }

    /**
     * key存在时替换value
     */
    @Override
    public V replace(K key, V value) {
    }

    /**
     * 带默认处理方式的get，如果key存在，则同get，否则就根据mappingFunction计算出value然后put
     */
    @Override
    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
    }

    /**
     * 相当于回调方式的replace，如果key不存在不做处理。key存在则根据remappingFunction算出新的value，如果为null，则删除，否则替换
     * 
     * @param remappingFunction BiFunction是双参数的Function版本
     */
    @Override
    public
            V
            computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    }

    /**
     * 全功能的compute，apply(k,null)表示k不存在的默认值回调 apply(k,v)表示k存在的replace回调 apply()返回null表示删除节点
     */
    @Override
    public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
    }

    /**
     * 与compute类似，不同是key存在的时候用apply(oldValue,value)来计算（BiFunction全部根据value来）
     */
    @Override
    public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
    }

    /**
     * 遍历处理所有元素
     */
    @Override
    public void forEach(BiConsumer<? super K, ? super V> action) {
    }

    /**
     * 双参数版的forEach()
     */
    @Override
    public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
    }

    // clone/serialized ///////////////////////

    /**
     * 浅克隆，复制所有kv的引用，不复制kv本身的属性
     */
    @SuppressWarnings("unchecked")
    @Override
    public Object clone() {
        HashMap<K, V> result;
        try {
            result = (HashMap<K, V>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
        result.reinitialize();
        result.putMapEntries(this, false);
        return result;
    }

    final int capacity() {
        return (table != null) ? table.length : (threshold > 0) ? threshold
                : DEFAULT_INITIAL_CAPACITY;
    }

    /**
     * 序列化到流
     *
     * @serialData 4字节capacity+4字节size+(keyObject+valueObject)*
     */
    private void writeObject(java.io.ObjectOutputStream s) throws IOException {
        int buckets = capacity();
        s.defaultWriteObject();
        s.writeInt(buckets);
        s.writeInt(size);
        internalWriteEntries(s);
    }

    // 迭代子 ////////////////////////////////

    /**
     * 基类，注意add是不支持的
     */
    abstract class HashIterator {
        Node<K, V> next; // 下一节点
        Node<K, V> current; // 当前节点
        int expectedModCount; // for fast-fail
        int index; // 当前节点下标

        HashIterator() {
            expectedModCount = modCount;
            Node<K, V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {
                    // 找到第一个非空节点
                } while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Node<K, V> nextNode() {
            Node<K, V>[] t;
            Node<K, V> e = next;
            if (modCount != expectedModCount) { // fast-fail
                throw new ConcurrentModificationException();
            }
            if (e == null) {
                throw new NoSuchElementException();
            }
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {
                    // 注意遍历次数是Capacity，不是size
                } while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            Node<K, V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            // 迭代子触发删除节点
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

    /**
     * 遍历Key
     */
    final class KeyIterator extends HashIterator implements Iterator<K> {
    }

    final class ValueIterator extends HashIterator implements Iterator<V> {
    }

    final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K, V>> {
    }

    // 分片迭代子（java8） ///////////////////////

    static class HashMapSpliterator<K, V> {
    }

    static final class KeySpliterator<K, V> extends HashMapSpliterator<K, V> implements
            Spliterator<K> {
    }

    static final class ValueSpliterator<K, V> extends HashMapSpliterator<K, V> implements
            Spliterator<V> {
    }

    static final class EntrySpliterator<K, V> extends HashMapSpliterator<K, V> implements
            Spliterator<Map.Entry<K, V>> {
    }

    // 为LinkedHashMap预留的可重写的方法 //////////////////////

    Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node<>(hash, key, value, next);
    }

    // TreeNode转为普通Node用
    Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
        return new Node<>(p.hash, p.key, p.value, next);
    }

    // 根据kv生成TreeNode，普通node转TreeNode
    TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {
        return new TreeNode<>(hash, key, value, next);
    }

    // 根据单个普通节点生成TreeNode
    TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K, V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }

    /**
     * 重置为空表，clone和readObject调用
     */
    void reinitialize() {
        table = null;
        entrySet = null;
        keySet = null;
        values = null;
        modCount = 0;
        threshold = 0;
        size = 0;
    }

    // LinkedHashMap重写的回调
    void afterNodeAccess(Node<K, V> p) {
    }

    void afterNodeInsertion(boolean evict) {
    }

    void afterNodeRemoval(Node<K, V> p) {
    }

    // 序列化表内容
    void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
        Node<K, V>[] tab;
        if (size > 0 && (tab = table) != null) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K, V> e = tab[i]; e != null; e = e.next) {
                    s.writeObject(e.key);
                    s.writeObject(e.value);
                }
            }
        }
    }