对象池实现

Question

下面是我的一个池的实现。它基于哈希表，支持使用强引用、软引用或弱引用来存储对象。一开始有一个构建器类来配置和创建实例，然后是一个Pool子类，它允许使用多个引用类型。最后，有一个enum定义了可用的引用类型，以及每个引用类型的Node接口(用于存储对象)的实现。

Nodes的存储和访问方式与在HashMap (减去树)和WeakHashMap中存储和访问的方式相同，存储和访问的桶数组长度等于2的幂，索引由&获得，即数组的长度减去1，并修改(只考虑使用较低比特的)哈希代码版本。每个Node都有一个对桶中下一个Node的引用，如果它是最后一个，则为null。

它将Nodes注册为ReferenceQueue，并尝试在调用添加或删除对象或检查池大小的方法时清除队列中的任何对象。其值已最后确定的节点也会在重新大小期间以及在检索对象时被移除。

我对我的代码没有任何具体的担忧，我只是在寻找任何可以改进的方法。

package common.collections;

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.util.Arrays;
import java.util.Objects;
import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.function.UnaryOperator;
import java.util.stream.Stream;

import common.utils.EnumUtils;
import common.utils.StreamUtils;

/** A pool based on a hash table which can store its elements in {@code Reference} objects.
 * <p>
 * Null values are not accepted and will result in a {@code NullPointerException} if you
 * try to add them.
 * <p>
 * This class is not thread safe. */
public class Pool<T> {
    private static final int MAX_CAPACITY = 1 << 30;
    private static final int MIN_CAPACITY = 1;
    private final double growFactor;
    private final double shrinkFactor;
    private final ReferenceQueue<T> queue;
    private final ReferenceType referenceType;
    private int size;
    private Node<T>[] nodes;

    @SuppressWarnings("unchecked")
    private Pool(int capacity, double growFactor, double shrinkFactor,
            ReferenceType referenceType) {
        this.growFactor = growFactor;
        this.shrinkFactor = shrinkFactor;
        this.referenceType = referenceType;
        nodes = new Node[capacity];
        queue = new ReferenceQueue<>();
    }

    public static class Builder<T> {
        private static final int DEFAULT_CAPACITY = 16;
        private static final double DEFAULT_GROW_FACTOR = 0.75;
        private static final double DEFAULT_SHRINK_FACTOR = 0;
        private static final ReferenceType DEFAULT_REFERENCE_TYPE = ReferenceType.WEAK;
        private int capacity;
        private double growFactor;
        private double shrinkFactor;
        private ReferenceType referenceType;

        public Builder() {
            capacity = DEFAULT_CAPACITY;
            growFactor = DEFAULT_GROW_FACTOR;
            shrinkFactor = DEFAULT_SHRINK_FACTOR;
            referenceType = DEFAULT_REFERENCE_TYPE;
        }
        public Pool<T> buildPool() {
            return new Pool<>(capacity, growFactor, shrinkFactor, referenceType);
        }
        public MultiReferenceTypePool<T> buildMultiReferenceTypePool() {
            return new MultiReferenceTypePool<>(capacity, growFactor, shrinkFactor,
                    referenceType);
        }
        /** Initial number of buckets. Will be rounded up (or down if greater than max
         * capacity) to a power of 2. */
        public Builder<T> capacity(int initialCapacity) {
            initialCapacity = Math.max(MIN_CAPACITY,
                    Math.min(MAX_CAPACITY, initialCapacity));
            capacity = 1;
            while (capacity < initialCapacity) {
                capacity <<= 1;
            }
            return this;
        }
        /** When size is greater than grow factor * capacity, capacity is doubled. */
        public Builder<T> growFactor(double f) {
            growFactor = f;
            return this;
        }
        /** Similar to grow factor except as a lower bound which reduces capacity. */
        public Builder<T> shrinkFactor(double f) {
            shrinkFactor = f;
            return this;
        }
        /** Sets the type of reference to use to store objects. */
        public Builder<T> referenceType(ReferenceType type) {
            referenceType = Objects.requireNonNull(type);
            return this;
        }
        @Override
        public String toString() {
            return "Capacity: " + capacity + " Reference Type: " + referenceType
                    + " Grow Factor: " + growFactor + " ShrinkFactor: " + shrinkFactor;
        }
    }

    /** An Extension of Pool which allows multiple reference types to be used. */
    public static class MultiReferenceTypePool<T> extends Pool<T> {

        private MultiReferenceTypePool(int capacity, double growFactor,
                double shrinkFactor, ReferenceType referenceType) {
            super(capacity, growFactor, shrinkFactor, referenceType);
        }
        /** Extension of {@link Pool#Add(T)} which allows the caller to specify the
         * reference type to be used to store the object. If a matching object is found
         * with a different reference type its type is changed to {@code referenceType} if
         * {@code changeCurrent} returns true. If {@code referenceType} is null the pool's
         * reference type is used instead. */
        public void Add(T t, ReferenceType ref,
                Predicate<? super ReferenceType> changeCurrent) {
            getOrCreate(() -> t, t::equals, t.hashCode(), ref, changeCurrent);
        }
        /** Extension of {@link Pool#getOrCreate(Supplier, Predicate, int)} which allows
         * the caller to specify the reference type to be used to store the object. If a
         * matching object is found with a different reference type its type is changed to
         * {@code referenceType} if {@code changeCurrent} returns true. If
         * {@code referenceType} is null the pool's reference type is used instead. */
        public T getOrCreate(Supplier<? extends T> supplier, Predicate<? super T> equals,
                int hash, ReferenceType referenceType,
                Predicate<? super ReferenceType> changeCurrent) {
            ReferenceType type = referenceType == null ? super.referenceType
                    : referenceType;
            hash = fixHash(hash);
            super.removeDeadNodes();
            T t = super.find(equals, hash, n -> n.type() == type ? n
                    : changeCurrent.test(n.type()) ? type.newNode(n.get(), n.hash(), super.queue)
                    : n);
            if (t != null) {
                return t;
            }
            t = Objects.requireNonNull(supplier.get());
            super.insert(type.newNode(t, hash, super.queue));
            super.size++;
            super.resize();
            return t;
        }
    }

    private int largestBucket() {
        return Arrays.stream(nodes)
            .filter(Objects::nonNull)
            .mapToInt(n -> (int) StreamUtils.iterate(n, Node::next).count())
            .max()
            .orElse(0);
    }
    /** Returns a sequential stream with this pool as its source. */
    public Stream<T> stream() {
        return Arrays.stream(nodes)
            .filter(Objects::nonNull)
            .flatMap(n -> StreamUtils.iterate(n, Node::next))
            .map(Node::get)
            .filter(Objects::nonNull);
    }
    @Override
    public String toString() {
        return "Buckets: " + nodes.length + "  Size: " + size + "  Reference Type: "
                + referenceType + "  Largest Bucket: " + largestBucket();
    }
    @SuppressWarnings("unchecked")
    private void removeDeadNodes() {
        Node<T> dead = null;
        outer: while ((dead = (Node<T>) queue.poll()) != null) {
            int index = dead.hash() & (nodes.length - 1);
            Node<T> n = nodes[index];
            Node<T> last = null;
            while (n != dead) {
                if (n == null) {
                    continue outer;
                }
                last = n;
                n = n.next();
            }
            size--;
            if (last == null) {
                nodes[index] = n.next();
            } else {
                last.setNext(n.next());
            }
        }
    }
    /** Removes all objects from this pool. */
    @SuppressWarnings("unchecked")
    public void clear() {
        size = 0;
        int s = getNewSize();
        if (s == nodes.length) {
            Arrays.fill(nodes, null);
        } else {
            nodes = new Node[s];
        }
        while (queue.poll() != null);
    }
    /** Returns an estimate of the number of elements in this pool. This method should not
     * be called during the execution of a stream returned from this pool because it may
     * modify the source of the stream. */
    public int size() {
        removeDeadNodes();
        resize();
        return size;
    }
    /** Adds {@code t} to this pool if an equal object is not already present. This method
     * is equivalent to calling {@code getOrCreate(() -> t, t::equals, t.hashCode());} */
    public void Add(T t) {
        getOrCreate(() -> t, t::equals, t.hashCode());
    }
    /** If an object that has a hash value equal to {@code hash} and {@code equals.test()}
     * returns true when applied to it exists in this pool, it is returned.
     * <p>
     * If a matching value cannot be found, {@code supplier.get()} is called to create one
     * and it is added to the pool, assigned the hash value {@code hash}, and returned.
     * 
     * @throws NullPointerException if {@code supplier.get()} returns null. */
    public T getOrCreate(Supplier<? extends T> supplier, Predicate<? super T> equals,
            int hash) {
        hash = fixHash(hash);
        removeDeadNodes();
        T t = find(equals, hash, n -> n);
        if (t != null) {
            return t;
        }
        t = Objects.requireNonNull(supplier.get());
        insert(referenceType.newNode(t, hash, queue));
        size++;
        resize();
        return t;
    }
    /** Removes from this pool and returns an object equal to {@code t}, or null if no such
     * value is present. This method is equivalent to calling
     * {@code remove(t::equals, t.hashCode())} */
    public T remove(T t) {
        return remove(t::equals, t.hashCode());
    }
    /** Removes from this pool and returns an object with a hash value of {@code hash}
     * which returns true when {@code equals.test()} is applied to it, or null if no
     * matching value is present. */
    public T remove(Predicate<? super T> equals, int hash) {
        hash = fixHash(hash);
        removeDeadNodes();
        return find(equals, hash, n -> null);
    }
    private T find(Predicate<? super T> equals, int hash,
            UnaryOperator<Node<T>> replacement) {
        int index = hash & (nodes.length - 1);
        for (Node<T> n = nodes[index], last = null; n != null; n = n.next()) {
            if (n.hash() != hash) {
                last = n;
                continue;
            }
            T t = n.get();
            if (t == null) {
                size--;
                if (last == null) {
                    nodes[index] = n.next();
                } else {
                    last.setNext(n.next());
                }
                continue;
            }
            if (equals.test(t)) {
                Node<T> newn = replacement.apply(n);
                if (newn == null) {
                    size--;
                    if (last == null) {
                        nodes[index] = n.next();
                    } else {
                        last.setNext(n.next());
                    }
                } else if (newn != n) {
                    newn.setNext(n.next());
                    if (last == null) {
                        nodes[index] = newn;
                    } else {
                        last.setNext(newn);
                    }
                }
                resize();
                return t;
            }
            last = n;
        }
        resize();
        return null;
    }
    /** @see java.util.WeakHashMap#hash */
    private static int fixHash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
    private void resize() {
        int s = getNewSize();
        if (s != nodes.length) {
            resize(s);
        }
    }
    private int getNewSize() {
        int s = nodes.length;
        while (size > s * growFactor && s < MAX_CAPACITY) {
            s <<= 1;
        }
        while (size < s * shrinkFactor && s > MIN_CAPACITY) {
            s >>= 1;
        }
        return s;
    }
    @SuppressWarnings("unchecked")
    private void resize(int length) {
        Node<T>[] oldNodes = nodes;
        nodes = new Node[length];
        for (Node<T> n : oldNodes) {
            while (n != null) {
                Node<T> next = n.next();
                n.setNext(null);
                if (n.get() != null) {
                    insert(n);
                } else {
                    size--;
                }
                n = next;
            }
        }
    };
    private void insert(Node<T> node) {
        int index = node.hash() & (nodes.length - 1);
        Node<T> n = nodes[index];
        if (n == null) {
            nodes[index] = node;
            return;
        }
        while (n.next() != null) {
            n = n.next();
        }
        n.setNext(node);
    }

    private interface Node<T> {
        T get();
        int hash();
        void setNext(Node<T> next);
        Node<T> next();
        ReferenceType type();
    }

    @SuppressWarnings("unchecked")
    public enum ReferenceType {
        WEAK(WeakNode::new), SOFT(SoftNode::new), STRONG(StrongNode::new);
        private final NodeConstructor constructor;

        private ReferenceType(NodeConstructor constructor) {
            this.constructor = constructor;
        }
        private <T> Node<T> newNode(T value, int hash, ReferenceQueue<T> queue) {
            return constructor.create(value, hash, queue);
        }
        @Override
        public String toString() {
            return EnumUtils.toString(this);
        }

        @FunctionalInterface
        private interface NodeConstructor {
            <T> Node<T> create(T value, int hash, ReferenceQueue<T> queue);
        }
    }

    private static class WeakNode<T> extends WeakReference<T> implements Node<T> {
        private final int hash;
        private Node<T> next;

        private WeakNode(T value, int hash, ReferenceQueue<T> queue) {
            super(value, queue);
            this.hash = hash;
        }
        @Override
        public int hash() {
            return hash;
        }
        @Override
        public Node<T> next() {
            return next;
        }
        @Override
        public void setNext(Node<T> next) {
            this.next = next;
        }
        @Override
        public ReferenceType type() {
            return ReferenceType.WEAK;
        }
    }

    private static class SoftNode<T> extends SoftReference<T> implements Node<T> {
        private final int hash;
        private Node<T> next;

        private SoftNode(T value, int hash, ReferenceQueue<T> queue) {
            super(value, queue);
            this.hash = hash;
        }
        @Override
        public int hash() {
            return hash;
        }
        @Override
        public Node<T> next() {
            return next;
        }
        @Override
        public void setNext(Node<T> next) {
            this.next = next;
        }
        @Override
        public ReferenceType type() {
            return ReferenceType.SOFT;
        }
    }

    private static class StrongNode<T> implements Node<T> {
        private final int hash;
        private final T value;
        private Node<T> next;

        private StrongNode(T value, int hash, ReferenceQueue<T> queue) {
            this.hash = hash;
            this.value = value;
        }
        @Override
        public T get() {
            return value;
        }
        @Override
        public int hash() {
            return hash;
        }
        @Override
        public Node<T> next() {
            return next;
        }
        @Override
        public void setNext(Node<T> next) {
            this.next = next;
        }
        @Override
        public ReferenceType type() {
            return ReferenceType.STRONG;
        }
    }
}

Answer 1

/** Removes all objects from this pool. */
@SuppressWarnings("unchecked")
public void clear() {
    size = 0;
    int s = getNewSize();
    if (s == nodes.length) {
        Arrays.fill(nodes, null);
    } else {
        nodes = new Node[s];
    }
    while (queue.poll() != null);
}

该函数除了执行注释的内容外，还执行其他一些操作(即运行一个while循环)。时间循环是用来做什么的？此外，您应该(这是一个挑剔的)写一个注释，为什么您在那里使用@SuppressWarnings注释。

private T find(Predicate<? super T> equals, int hash,
        UnaryOperator<Node<T>> replacement) {
    int index = hash & (nodes.length - 1);
    for (Node<T> n = nodes[index], last = null; n != null; n = n.next()) {
        if (n.hash() != hash) {
            last = n;
            continue;
        }
        T t = n.get();
        if (t == null) {
            size--;
            if (last == null) {
                nodes[index] = n.next();
            } else {
                last.setNext(n.next());
            }
            continue;
        }
        if (equals.test(t)) {
            Node<T> newn = replacement.apply(n);
            if (newn == null) {
                size--;
                if (last == null) {
                    nodes[index] = n.next();
                } else {
                    last.setNext(n.next());
                }
            } else if (newn != n) {
                newn.setNext(n.next());
                if (last == null) {
                    nodes[index] = newn;
                } else {
                    last.setNext(newn);
                }
            }
            resize();
            return t;
        }
        last = n;
    }
    resize();
    return null;
}

这个函数的圈复杂度是10，这有点高，但没关系。你对此无能为力。但是，您应该记住，随着您的函数变得更加复杂，您的变量名应该更具有描述性。newn是什么意思？这是一个新节点吗？不过，我不认为关键字是新的。此外，这样复杂的方法可以使用注释来解释它们到底在做什么(我的这个注释可能会变得不相关，一旦您使变量名更具描述性)。

更多的@SuppressWarnings出现-评论那些可能的维护程序员的解释。

我的个人喜好(挑剔)：

我想补充一条为什么在构建器上使用return this的原因(我知道为什么，它是用于链接的，但其他人可能不会)。

我还将函数growFactor和shrinkFactor重命名为setGrowFactor和setShrinkFactor。这是因为似乎很容易将它们误认为是"growByFactor“和"shrinkByFactor”。然而，文件表明，情况并非如此，这使我个人更倾向于这一点，而不是一个显著的改进。

我会在函数的末尾和记录下一个函数的注释块的开始之间放置空行。这样做给我的感觉是一个函数结束在那里，我可以在继续之前处理我所读过的内容。

private void resize() {
    int s = getNewSize();
    if (s != nodes.length) {
        resize(s);
    }
}
private int getNewSize() {
    int s = nodes.length;
    while (size > s * growFactor && s < MAX_CAPACITY) {
        s <<= 1;
    }
    while (size < s * shrinkFactor && s > MIN_CAPACITY) {
        s >>= 1;
    }
    return s;
}
@SuppressWarnings("unchecked")
private void resize(int length) {

就我个人而言，我更喜欢将相同名称的函数放在一起。这使得查找它们变得更容易。因此，在这种情况下，我会将resize()与getNewSize()交换。

现在我们真的进入了挑剔的境地。

    /** Extension of {@link Pool#Add(T)} which allows the caller to specify the
     * reference type to be used to store the object. If a matching object is found
     * with a different reference type its type is changed to {@code referenceType} if
     * {@code changeCurrent} returns true. If {@code referenceType} is null the pool's
     * reference type is used instead. */

“如果找到具有不同引用类型的匹配对象，则如果referenceType返回true，则将其类型更改为changeCurrent。”

这个句子少了一个逗号。改为“(.)具有不同的引用类型，其类型”。

“如果referenceType为空，则使用池的引用类型。”

也少了一个逗号。更改为“如果‘引用类型为空，则池的(.)”。

在这一点上，我认为我们可以同意，您已经编写了一段了不起的代码。它有很好的文档，充分利用了语言的特性(循环标签！上一次我看到这些是在我为了好玩而阅读规范的时候！)，而且似乎没有任何明显的缺陷。正如您所看到的，除了一些函数的命名之外，我指出的所有内容都与实际代码无关。其余部分都与您的功能的注释和顺序有关。

我建议使用各种工具来分析代码，比如声纳和其他的工具。如果你真的想精益求精的话，我还建议你写一套单元测试。