changeset 14380:c5467b18921b

8139233: add initial compact immutable collection implementations Reviewed-by: plevart, forax, dfuchs, chegar, alanb, scolebourne
author smarks
date Fri, 06 May 2016 11:33:32 -0700
parents b9760b7afe0d
children b9ed1a4feefb 963fa7af5548
files src/java.base/share/classes/java/util/ImmutableCollections.java src/java.base/share/classes/java/util/List.java src/java.base/share/classes/java/util/Map.java src/java.base/share/classes/java/util/Set.java test/java/util/Map/EntrySetIterator.java
diffstat 5 files changed, 792 insertions(+), 278 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/java.base/share/classes/java/util/ImmutableCollections.java	Fri May 06 11:33:32 2016 -0700
@@ -0,0 +1,657 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+package java.util;
+
+import java.io.IOException;
+import java.io.InvalidObjectException;
+import java.io.ObjectInputStream;
+import java.io.ObjectStreamException;
+import java.io.Serializable;
+
+/**
+ * Container class for immutable collections. Not part of the public API.
+ * Mainly for namespace management and shared infrastructure.
+ *
+ * Serial warnings are suppressed throughout because all implementation
+ * classes use a serial proxy and thus have no need to declare serialVersionUID.
+ */
+@SuppressWarnings("serial")
+class ImmutableCollections {
+    /**
+     * A "salt" value used for randomizing iteration order. This is initialized once
+     * and stays constant for the lifetime of the JVM. It need not be truly random, but
+     * it needs to vary sufficiently from one run to the next so that iteration order
+     * will vary between JVM runs.
+     */
+    static final int SALT;
+    static {
+        SALT = new Random().nextInt();
+    }
+
+    /** No instances. */
+    private ImmutableCollections() { }
+
+    /**
+     * The reciprocal of load factor. Given a number of elements
+     * to store, multiply by this factor to get the table size.
+     */
+    static final double EXPAND_FACTOR = 2.0;
+
+    // ---------- List Implementations ----------
+
+    static final class List0<E> extends AbstractList<E> implements RandomAccess, Serializable {
+        List0() { }
+
+        @Override
+        public int size() {
+            return 0;
+        }
+
+        @Override
+        public E get(int index) {
+            Objects.checkIndex(index, 0); // always throws IndexOutOfBoundsException
+            return null;                  // but the compiler doesn't know this
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_LIST);
+        }
+    }
+
+    static final class List1<E> extends AbstractList<E> implements RandomAccess, Serializable {
+        private final E e0;
+
+        List1(E e0) {
+            this.e0 = Objects.requireNonNull(e0);
+        }
+
+        @Override
+        public int size() {
+            return 1;
+        }
+
+        @Override
+        public E get(int index) {
+            Objects.checkIndex(index, 1);
+            // assert index == 0
+            return e0;
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_LIST, e0);
+        }
+    }
+
+    static final class List2<E> extends AbstractList<E> implements RandomAccess, Serializable {
+        private final E e0;
+        private final E e1;
+
+        List2(E e0, E e1) {
+            this.e0 = Objects.requireNonNull(e0);
+            this.e1 = Objects.requireNonNull(e1);
+        }
+
+        @Override
+        public int size() {
+            return 2;
+        }
+
+        @Override
+        public E get(int index) {
+            Objects.checkIndex(index, 2);
+            if (index == 0) {
+                return e0;
+            } else { // index == 1
+                return e1;
+            }
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_LIST, e0, e1);
+        }
+    }
+
+    static final class ListN<E> extends AbstractList<E> implements RandomAccess, Serializable {
+        private final E[] elements;
+
+        @SafeVarargs
+        ListN(E... input) {
+            // copy and check manually to avoid TOCTOU
+            @SuppressWarnings("unchecked")
+            E[] tmp = (E[])new Object[input.length]; // implicit nullcheck of input
+            for (int i = 0; i < input.length; i++) {
+                tmp[i] = Objects.requireNonNull(input[i]);
+            }
+            this.elements = tmp;
+        }
+
+        @Override
+        public int size() {
+            return elements.length;
+        }
+
+        @Override
+        public E get(int index) {
+            Objects.checkIndex(index, elements.length);
+            return elements[index];
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_LIST, elements);
+        }
+    }
+
+    // ---------- Set Implementations ----------
+
+    static final class Set0<E> extends AbstractSet<E> implements Serializable {
+        Set0() { }
+
+        @Override
+        public int size() {
+            return 0;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return super.contains(Objects.requireNonNull(o));
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return Collections.emptyIterator();
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_SET);
+        }
+    }
+
+    static final class Set1<E> extends AbstractSet<E> implements Serializable {
+        private final E e0;
+
+        Set1(E e0) {
+            this.e0 = Objects.requireNonNull(e0);
+        }
+
+        @Override
+        public int size() {
+            return 1;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return super.contains(Objects.requireNonNull(o));
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return Collections.singletonIterator(e0);
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_SET, e0);
+        }
+    }
+
+    static final class Set2<E> extends AbstractSet<E> implements Serializable {
+        private final E e0;
+        private final E e1;
+
+        Set2(E e0, E e1) {
+            Objects.requireNonNull(e0);
+            Objects.requireNonNull(e1);
+
+            if (e0.equals(e1)) {
+                throw new IllegalArgumentException("duplicate element: " + e0);
+            }
+
+            if (SALT >= 0) {
+                this.e0 = e0;
+                this.e1 = e1;
+            } else {
+                this.e0 = e1;
+                this.e1 = e0;
+            }
+        }
+
+        @Override
+        public int size() {
+            return 2;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            return super.contains(Objects.requireNonNull(o));
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return new Iterator<E>() {
+                private int idx = 0;
+
+                @Override
+                public boolean hasNext() {
+                    return idx < 2;
+                }
+
+                @Override
+                public E next() {
+                    if (idx == 0) {
+                        idx = 1;
+                        return e0;
+                    } else if (idx == 1) {
+                        idx = 2;
+                        return e1;
+                    } else {
+                        throw new NoSuchElementException();
+                    }
+                }
+            };
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_SET, e0, e1);
+        }
+    }
+
+    /**
+     * An array-based Set implementation. The element array must be strictly
+     * larger than the size (the number of contained elements) so that at
+     * least one null is always present.
+     * @param <E> the element type
+     */
+    static final class SetN<E> extends AbstractSet<E> implements Serializable {
+        private final E[] elements;
+        private final int size;
+
+        @SafeVarargs
+        @SuppressWarnings("unchecked")
+        SetN(E... input) {
+            size = input.length; // implicit nullcheck of input
+
+            elements = (E[])new Object[(int)Math.ceil(EXPAND_FACTOR * input.length)];
+            for (int i = 0; i < input.length; i++) {
+                E e = Objects.requireNonNull(input[i]);
+                int idx = probe(e);
+                if (idx >= 0) {
+                    throw new IllegalArgumentException("duplicate element: " + e);
+                } else {
+                    elements[-(idx + 1)] = e;
+                }
+            }
+        }
+
+        @Override
+        public int size() {
+            return size;
+        }
+
+        @Override
+        public boolean contains(Object o) {
+            Objects.requireNonNull(o);
+            return probe(o) >= 0;
+        }
+
+        @Override
+        public Iterator<E> iterator() {
+            return new Iterator<E>() {
+                private int idx = 0;
+
+                @Override
+                public boolean hasNext() {
+                    while (idx < elements.length) {
+                        if (elements[idx] != null)
+                            return true;
+                        idx++;
+                    }
+                    return false;
+                }
+
+                @Override
+                public E next() {
+                    if (! hasNext()) {
+                        throw new NoSuchElementException();
+                    }
+                    return elements[idx++];
+                }
+            };
+        }
+
+        // returns index at which element is present; or if absent,
+        // (-i - 1) where i is location where element should be inserted
+        private int probe(Object pe) {
+            int idx = Math.floorMod(pe.hashCode() ^ SALT, elements.length);
+            while (true) {
+                E ee = elements[idx];
+                if (ee == null) {
+                    return -idx - 1;
+                } else if (pe.equals(ee)) {
+                    return idx;
+                } else if (++idx == elements.length) {
+                    idx = 0;
+                }
+            }
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            Object[] array = new Object[size];
+            int dest = 0;
+            for (Object o : elements) {
+                if (o != null) {
+                    array[dest++] = o;
+                }
+            }
+            return new CollSer(CollSer.IMM_SET, array);
+        }
+    }
+
+    // ---------- Map Implementations ----------
+
+    static final class Map0<K,V> extends AbstractMap<K,V> implements Serializable {
+        Map0() { }
+
+        @Override
+        public Set<Map.Entry<K,V>> entrySet() {
+            return Set.of();
+        }
+
+        @Override
+        public boolean containsKey(Object o) {
+            return super.containsKey(Objects.requireNonNull(o));
+        }
+
+        @Override
+        public boolean containsValue(Object o) {
+            return super.containsValue(Objects.requireNonNull(o));
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_MAP);
+        }
+    }
+
+    static final class Map1<K,V> extends AbstractMap<K,V> implements Serializable {
+        private final K k0;
+        private final V v0;
+
+        Map1(K k0, V v0) {
+            this.k0 = Objects.requireNonNull(k0);
+            this.v0 = Objects.requireNonNull(v0);
+        }
+
+        @Override
+        public Set<Map.Entry<K,V>> entrySet() {
+            return Set.of(new KeyValueHolder<>(k0, v0));
+        }
+
+        @Override
+        public boolean containsKey(Object o) {
+            return super.containsKey(Objects.requireNonNull(o));
+        }
+
+        @Override
+        public boolean containsValue(Object o) {
+            return super.containsValue(Objects.requireNonNull(o));
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            return new CollSer(CollSer.IMM_MAP, k0, v0);
+        }
+    }
+
+    /**
+     * An array-based Map implementation. There is a single array "table" that
+     * contains keys and values interleaved: table[0] is kA, table[1] is vA,
+     * table[2] is kB, table[3] is vB, etc. The table size must be even. It must
+     * also be strictly larger than the size (the number of key-value pairs contained
+     * in the map) so that at least one null key is always present.
+     * @param <K> the key type
+     * @param <V> the value type
+     */
+    static final class MapN<K,V> extends AbstractMap<K,V> implements Serializable {
+        private final Object[] table; // pairs of key, value
+        private final int size; // number of pairs
+
+        MapN(Object... input) {
+            Objects.requireNonNull(input);
+            if ((input.length & 1) != 0) {
+                throw new InternalError("length is odd");
+            }
+            size = input.length >> 1;
+
+            int len = (int)Math.ceil(EXPAND_FACTOR * input.length);
+            len = (len + 1) & ~1; // ensure table is even length
+            table = new Object[len];
+
+            for (int i = 0; i < input.length; i += 2) {
+                @SuppressWarnings("unchecked")
+                    K k = Objects.requireNonNull((K)input[i]);
+                @SuppressWarnings("unchecked")
+                    V v = Objects.requireNonNull((V)input[i+1]);
+                int idx = probe(k);
+                if (idx >= 0) {
+                    throw new IllegalArgumentException("duplicate key: " + k);
+                } else {
+                    int dest = -(idx + 1);
+                    table[dest] = k;
+                    table[dest+1] = v;
+                }
+            }
+        }
+
+        @Override
+        public boolean containsKey(Object o) {
+            return probe(Objects.requireNonNull(o)) >= 0;
+        }
+
+        @Override
+        public boolean containsValue(Object o) {
+            return super.containsValue(Objects.requireNonNull(o));
+        }
+
+        @Override
+        @SuppressWarnings("unchecked")
+        public V get(Object o) {
+            int i = probe(o);
+            if (i >= 0) {
+                return (V)table[i+1];
+            } else {
+                return null;
+            }
+        }
+
+        @Override
+        public int size() {
+            return size;
+        }
+
+        @Override
+        public Set<Map.Entry<K,V>> entrySet() {
+            return new AbstractSet<Map.Entry<K,V>>() {
+                @Override
+                public int size() {
+                    return MapN.this.size;
+                }
+
+                @Override
+                public Iterator<Map.Entry<K,V>> iterator() {
+                    return new Iterator<Map.Entry<K,V>>() {
+                        int idx = 0;
+
+                        @Override
+                        public boolean hasNext() {
+                            while (idx < table.length) {
+                                if (table[idx] != null)
+                                    return true;
+                                idx += 2;
+                            }
+                            return false;
+                        }
+
+                        @Override
+                        public Map.Entry<K,V> next() {
+                            if (hasNext()) {
+                                @SuppressWarnings("unchecked")
+                                Map.Entry<K,V> e =
+                                    new KeyValueHolder<>((K)table[idx], (V)table[idx+1]);
+                                idx += 2;
+                                return e;
+                            } else {
+                                throw new NoSuchElementException();
+                            }
+                        }
+                    };
+                }
+            };
+        }
+
+        // returns index at which the probe key is present; or if absent,
+        // (-i - 1) where i is location where element should be inserted
+        private int probe(Object pk) {
+            int idx = Math.floorMod(pk.hashCode() ^ SALT, table.length >> 1) << 1;
+            while (true) {
+                @SuppressWarnings("unchecked")
+                K ek = (K)table[idx];
+                if (ek == null) {
+                    return -idx - 1;
+                } else if (pk.equals(ek)) {
+                    return idx;
+                } else if ((idx += 2) == table.length) {
+                    idx = 0;
+                }
+            }
+        }
+
+        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
+            throw new InvalidObjectException("not serial proxy");
+        }
+
+        private Object writeReplace() {
+            Object[] array = new Object[2 * size];
+            int len = table.length;
+            int dest = 0;
+            for (int i = 0; i < len; i += 2) {
+                if (table[i] != null) {
+                    array[dest++] = table[i];
+                    array[dest++] = table[i+1];
+                }
+            }
+            return new CollSer(CollSer.IMM_MAP, array);
+        }
+    }
+}
+
+// ---------- Serialization Proxy ----------
+
+/**
+ * Serialization proxy class for immutable collections.
+ */
+final class CollSer implements Serializable {
+    private static final long serialVersionUID = 6309168927139932177L;
+
+    static final int IMM_LIST = 1;
+    static final int IMM_SET = 2;
+    static final int IMM_MAP = 3;
+
+    private final int flags;
+    private final Object[] array;
+
+    CollSer(int f, Object... a) {
+        flags = f;
+        array = a;
+    }
+
+    private Object readResolve() throws ObjectStreamException {
+        try {
+            if (array == null) {
+                throw new InvalidObjectException("null array");
+            }
+
+            // use low order 8 bits to indicate "kind"
+            // ignore high order bits
+            switch (flags & 0xff) {
+                case IMM_LIST:
+                    return List.of(array);
+                case IMM_SET:
+                    return Set.of(array);
+                case IMM_MAP:
+                    if (array.length == 0) {
+                        return new ImmutableCollections.Map0<>();
+                    } else if (array.length == 2) {
+                        return new ImmutableCollections.Map1<>(array[0], array[1]);
+                    } else {
+                        return new ImmutableCollections.MapN<>(array);
+                    }
+                default:
+                    throw new InvalidObjectException(String.format("invalid flags 0x%x", flags));
+            }
+        } catch (NullPointerException|IllegalArgumentException ex) {
+            InvalidObjectException ioe = new InvalidObjectException("invalid object");
+            ioe.initCause(ex);
+            throw ioe;
+        }
+    }
+}
--- a/src/java.base/share/classes/java/util/List.java	Fri May 06 12:48:19 2016 +0000
+++ b/src/java.base/share/classes/java/util/List.java	Fri May 06 11:33:32 2016 -0700
@@ -765,7 +765,7 @@
      * @since 9
      */
     static <E> List<E> of() {
-        return Collections.emptyList();
+        return new ImmutableCollections.List0<>();
     }
 
     /**
@@ -781,7 +781,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1) {
-        return Collections.singletonList(Objects.requireNonNull(e1));
+        return new ImmutableCollections.List1<>(e1);
     }
 
     /**
@@ -798,9 +798,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2)));
+        return new ImmutableCollections.List2<>(e1, e2);
     }
 
     /**
@@ -818,10 +816,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3);
     }
 
     /**
@@ -840,11 +835,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4);
     }
 
     /**
@@ -864,12 +855,7 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5);
     }
 
     /**
@@ -890,13 +876,8 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5),
-                          Objects.requireNonNull(e6)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+                                                e6);
     }
 
     /**
@@ -918,14 +899,8 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5),
-                          Objects.requireNonNull(e6),
-                          Objects.requireNonNull(e7)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+                                                e6, e7);
     }
 
     /**
@@ -948,15 +923,8 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5),
-                          Objects.requireNonNull(e6),
-                          Objects.requireNonNull(e7),
-                          Objects.requireNonNull(e8)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+                                                e6, e7, e8);
     }
 
     /**
@@ -980,16 +948,8 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5),
-                          Objects.requireNonNull(e6),
-                          Objects.requireNonNull(e7),
-                          Objects.requireNonNull(e8),
-                          Objects.requireNonNull(e9)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+                                                e6, e7, e8, e9);
     }
 
     /**
@@ -1014,17 +974,8 @@
      * @since 9
      */
     static <E> List<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
-        return Collections.unmodifiableList(
-            Arrays.asList(Objects.requireNonNull(e1),
-                          Objects.requireNonNull(e2),
-                          Objects.requireNonNull(e3),
-                          Objects.requireNonNull(e4),
-                          Objects.requireNonNull(e5),
-                          Objects.requireNonNull(e6),
-                          Objects.requireNonNull(e7),
-                          Objects.requireNonNull(e8),
-                          Objects.requireNonNull(e9),
-                          Objects.requireNonNull(e10)));
+        return new ImmutableCollections.ListN<>(e1, e2, e3, e4, e5,
+                                                e6, e7, e8, e9, e10);
     }
 
     /**
@@ -1055,10 +1006,16 @@
     @SafeVarargs
     @SuppressWarnings("varargs")
     static <E> List<E> of(E... elements) {
-        elements = elements.clone(); // throws NPE if es is null
-        for (E e : elements) {
-            Objects.requireNonNull(e);
+        Objects.requireNonNull(elements);
+        switch (elements.length) {
+            case 0:
+                return new ImmutableCollections.List0<>();
+            case 1:
+                return new ImmutableCollections.List1<>(elements[0]);
+            case 2:
+                return new ImmutableCollections.List2<>(elements[0], elements[1]);
+            default:
+                return new ImmutableCollections.ListN<>(elements);
         }
-        return Collections.unmodifiableList(Arrays.asList(elements));
     }
 }
--- a/src/java.base/share/classes/java/util/Map.java	Fri May 06 12:48:19 2016 +0000
+++ b/src/java.base/share/classes/java/util/Map.java	Fri May 06 11:33:32 2016 -0700
@@ -1282,7 +1282,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of() {
-        return Collections.emptyMap();
+        return new ImmutableCollections.Map0<>();
     }
 
     /**
@@ -1299,7 +1299,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of(K k1, V v1) {
-        return Collections.singletonMap(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
+        return new ImmutableCollections.Map1<>(k1, v1);
     }
 
     /**
@@ -1319,13 +1319,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2) {
-        Map<K, V> map = new HashMap<>(3); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        if (map.size() != 2) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2);
     }
 
     /**
@@ -1347,14 +1341,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
-        Map<K, V> map = new HashMap<>(5); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        if (map.size() != 3) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3);
     }
 
     /**
@@ -1378,15 +1365,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
-        Map<K, V> map = new HashMap<>(6); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        if (map.size() != 4) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4);
     }
 
     /**
@@ -1412,16 +1391,7 @@
      * @since 9
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
-        Map<K, V> map = new HashMap<>(7); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        if (map.size() != 5) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
     }
 
     /**
@@ -1450,17 +1420,8 @@
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
                                K k6, V v6) {
-        Map<K, V> map = new HashMap<>(9); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
-        if (map.size() != 6) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+                                               k6, v6);
     }
 
     /**
@@ -1491,18 +1452,8 @@
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
                                K k6, V v6, K k7, V v7) {
-        Map<K, V> map = new HashMap<>(10); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
-        map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
-        if (map.size() != 7) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+                                               k6, v6, k7, v7);
     }
 
     /**
@@ -1535,19 +1486,8 @@
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
                                K k6, V v6, K k7, V v7, K k8, V v8) {
-        Map<K, V> map = new HashMap<>(11); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
-        map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
-        map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
-        if (map.size() != 8) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+                                               k6, v6, k7, v7, k8, v8);
     }
 
     /**
@@ -1582,20 +1522,8 @@
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9) {
-        Map<K, V> map = new HashMap<>(13); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
-        map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
-        map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
-        map.put(Objects.requireNonNull(k9), Objects.requireNonNull(v9));
-        if (map.size() != 9) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+                                               k6, v6, k7, v7, k8, v8, k9, v9);
     }
 
     /**
@@ -1632,21 +1560,8 @@
      */
     static <K, V> Map<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5,
                                K k6, V v6, K k7, V v7, K k8, V v8, K k9, V v9, K k10, V v10) {
-        Map<K, V> map = new HashMap<>(14); // specify number of buckets to avoid resizing
-        map.put(Objects.requireNonNull(k1), Objects.requireNonNull(v1));
-        map.put(Objects.requireNonNull(k2), Objects.requireNonNull(v2));
-        map.put(Objects.requireNonNull(k3), Objects.requireNonNull(v3));
-        map.put(Objects.requireNonNull(k4), Objects.requireNonNull(v4));
-        map.put(Objects.requireNonNull(k5), Objects.requireNonNull(v5));
-        map.put(Objects.requireNonNull(k6), Objects.requireNonNull(v6));
-        map.put(Objects.requireNonNull(k7), Objects.requireNonNull(v7));
-        map.put(Objects.requireNonNull(k8), Objects.requireNonNull(v8));
-        map.put(Objects.requireNonNull(k9), Objects.requireNonNull(v9));
-        map.put(Objects.requireNonNull(k10), Objects.requireNonNull(v10));
-        if (map.size() != 10) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
+        return new ImmutableCollections.MapN<>(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5,
+                                               k6, v6, k7, v7, k8, v8, k9, v9, k10, v10);
     }
 
     /**
@@ -1683,15 +1598,21 @@
     @SafeVarargs
     @SuppressWarnings("varargs")
     static <K, V> Map<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
-        Map<K, V> map = new HashMap<>(entries.length * 4 / 3 + 1); // throws NPE if entries is null
-        for (Entry<? extends K, ? extends V> e : entries) {
-            // next line throws NPE if e is null
-            map.put(Objects.requireNonNull(e.getKey()), Objects.requireNonNull(e.getValue()));
+        Objects.requireNonNull(entries);
+        if (entries.length == 0) {
+            return new ImmutableCollections.Map0<>();
+        } else if (entries.length == 1) {
+            return new ImmutableCollections.Map1<>(entries[0].getKey(),
+                                                   entries[0].getValue());
+        } else {
+            Object[] kva = new Object[entries.length << 1];
+            int a = 0;
+            for (Entry<? extends K, ? extends V> entry : entries) {
+                kva[a++] = entry.getKey();
+                kva[a++] = entry.getValue();
+            }
+            return new ImmutableCollections.MapN<>(kva);
         }
-        if (map.size() != entries.length) {
-            throw new IllegalArgumentException("duplicate keys");
-        }
-        return Collections.unmodifiableMap(map);
     }
 
     /**
--- a/src/java.base/share/classes/java/util/Set.java	Fri May 06 12:48:19 2016 +0000
+++ b/src/java.base/share/classes/java/util/Set.java	Fri May 06 11:33:32 2016 -0700
@@ -444,7 +444,7 @@
      * @since 9
      */
     static <E> Set<E> of() {
-        return Collections.emptySet();
+        return new ImmutableCollections.Set0<>();
     }
 
     /**
@@ -459,7 +459,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1) {
-        return Collections.singleton(Objects.requireNonNull(e1));
+        return new ImmutableCollections.Set1<>(e1);
     }
 
     /**
@@ -476,12 +476,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2)));
-        if (set.size() != 2) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.Set2<>(e1, e2);
     }
 
     /**
@@ -499,13 +494,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3)));
-        if (set.size() != 3) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3);
     }
 
     /**
@@ -524,14 +513,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4)));
-        if (set.size() != 4) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4);
     }
 
     /**
@@ -551,15 +533,7 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5)));
-        if (set.size() != 5) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5);
     }
 
     /**
@@ -580,16 +554,8 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5),
-                                                 Objects.requireNonNull(e6)));
-        if (set.size() != 6) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+                                               e6);
     }
 
     /**
@@ -611,17 +577,8 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5),
-                                                 Objects.requireNonNull(e6),
-                                                 Objects.requireNonNull(e7)));
-        if (set.size() != 7) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+                                               e6, e7);
     }
 
     /**
@@ -644,18 +601,8 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5),
-                                                 Objects.requireNonNull(e6),
-                                                 Objects.requireNonNull(e7),
-                                                 Objects.requireNonNull(e8)));
-        if (set.size() != 8) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+                                               e6, e7, e8);
     }
 
     /**
@@ -679,19 +626,8 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5),
-                                                 Objects.requireNonNull(e6),
-                                                 Objects.requireNonNull(e7),
-                                                 Objects.requireNonNull(e8),
-                                                 Objects.requireNonNull(e9)));
-        if (set.size() != 9) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+                                               e6, e7, e8, e9);
     }
 
     /**
@@ -716,20 +652,8 @@
      * @since 9
      */
     static <E> Set<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E e7, E e8, E e9, E e10) {
-        Set<E> set = new HashSet<>(Arrays.asList(Objects.requireNonNull(e1),
-                                                 Objects.requireNonNull(e2),
-                                                 Objects.requireNonNull(e3),
-                                                 Objects.requireNonNull(e4),
-                                                 Objects.requireNonNull(e5),
-                                                 Objects.requireNonNull(e6),
-                                                 Objects.requireNonNull(e7),
-                                                 Objects.requireNonNull(e8),
-                                                 Objects.requireNonNull(e9),
-                                                 Objects.requireNonNull(e10)));
-        if (set.size() != 10) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
+        return new ImmutableCollections.SetN<>(e1, e2, e3, e4, e5,
+                                               e6, e7, e8, e9, e10);
     }
 
     /**
@@ -759,15 +683,18 @@
      * @since 9
      */
     @SafeVarargs
+    @SuppressWarnings("varargs")
     static <E> Set<E> of(E... elements) {
-        for (E e : elements) { // throws NPE if es is null
-            Objects.requireNonNull(e);
+        Objects.requireNonNull(elements);
+        switch (elements.length) {
+            case 0:
+                return new ImmutableCollections.Set0<>();
+            case 1:
+                return new ImmutableCollections.Set1<>(elements[0]);
+            case 2:
+                return new ImmutableCollections.Set2<>(elements[0], elements[1]);
+            default:
+                return new ImmutableCollections.SetN<>(elements);
         }
-        @SuppressWarnings("varargs")
-        Set<E> set = new HashSet<>(Arrays.asList(elements));
-        if (set.size() != elements.length) {
-            throw new IllegalArgumentException("duplicate elements");
-        }
-        return Collections.unmodifiableSet(set);
     }
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/Map/EntrySetIterator.java	Fri May 06 11:33:32 2016 -0700
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * @test
+ * @bug 8139233
+ * @summary ensure entry set's iterator doesn't have side effects on the entry set
+ * @run testng EntrySetIterator
+ */
+
+import java.util.*;
+import org.testng.annotations.Test;
+import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.assertEquals;
+
+public class EntrySetIterator {
+    @Test
+    public void main() {
+        Map<String, String> map = Map.of("a", "1", "b", "2", "c", "3");
+        Set<Map.Entry<String, String>> entrySet = map.entrySet();
+        Iterator<Map.Entry<String, String>> iterator = entrySet.iterator();
+
+        assertTrue(iterator.hasNext());
+
+        // copying implicitly iterates an iterator
+        Set<Map.Entry<String, String>> copy1 = new HashSet<>(entrySet);
+        Set<Map.Entry<String, String>> copy2 = new HashSet<>(entrySet);
+
+        assertEquals(copy2, copy1);
+        assertTrue(iterator.hasNext());
+    }
+}