jdk/test/java/util/Map/Get.java
author mduigou
Wed, 30 May 2012 22:18:37 -0700
changeset 12859 c44b88bb9b5e
parent 5506 202f599c92aa
child 14342 8435a30053c1
permissions -rw-r--r--
7126277: Alternative String hashing implementation Summary: All of the hashing based Map implementations: HashMap, Hashtable, LinkedHashMap, WeakHashMap and ConcurrentHashMap are modified to use an enhanced hashing algorithm for string keys when the capacity of the hash table has ever grown beyond 512 entries. The enhanced hashing implementation uses the murmur3 hashing algorithm along with random hash seeds and index masks. These enhancements mitigate cases where colliding String hash values could result in a performance bottleneck. Reviewed-by: alanb, forax, dl
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     2
 * Copyright (c) 2005, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
90ce3da70b43 Initial load
duke
parents:
diff changeset
     7
 * published by the Free Software Foundation.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     9
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    19
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    20
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    21
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    22
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    23
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
/*
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
 * @test
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
 * @bug 6306829
90ce3da70b43 Initial load
duke
parents:
diff changeset
    27
 * @summary Verify assertions in get() javadocs
90ce3da70b43 Initial load
duke
parents:
diff changeset
    28
 * @author Martin Buchholz
90ce3da70b43 Initial load
duke
parents:
diff changeset
    29
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    30
90ce3da70b43 Initial load
duke
parents:
diff changeset
    31
import java.io.*;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    32
import java.util.*;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    33
import java.util.concurrent.*;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
import java.util.concurrent.atomic.*;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    35
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
public class Get {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
90ce3da70b43 Initial load
duke
parents:
diff changeset
    38
    private static void realMain(String[] args) throws Throwable {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
        testMap(new Hashtable<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    40
        testMap(new HashMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    41
        testMap(new IdentityHashMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    42
        testMap(new LinkedHashMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
        testMap(new ConcurrentHashMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
        testMap(new WeakHashMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    45
        testMap(new TreeMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
        testMap(new ConcurrentSkipListMap<Character,Boolean>());
90ce3da70b43 Initial load
duke
parents:
diff changeset
    47
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
    private static void put(Map<Character,Boolean> m,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
                            Character key, Boolean value,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
                            Boolean oldValue) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
        if (oldValue != null) {
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    53
            check("containsValue(oldValue)", m.containsValue(oldValue));
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    54
            check("values.contains(oldValue)", m.values().contains(oldValue));
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    55
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
        equal(m.put(key, value), oldValue);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
        equal(m.get(key), value);
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    58
        check("containsKey", m.containsKey(key));
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    59
        check("keySet.contains", m.keySet().contains(key));
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    60
        check("containsValue", m.containsValue(value));
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    61
        check("values.contains",  m.values().contains(value));
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    62
        check("!isEmpty", ! m.isEmpty());
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    63
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    64
90ce3da70b43 Initial load
duke
parents:
diff changeset
    65
    private static void testMap(Map<Character,Boolean> m) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    66
        // We verify following assertions in get(Object) method javadocs
90ce3da70b43 Initial load
duke
parents:
diff changeset
    67
        boolean permitsNullKeys = (! (m instanceof ConcurrentMap ||
90ce3da70b43 Initial load
duke
parents:
diff changeset
    68
                                      m instanceof Hashtable     ||
90ce3da70b43 Initial load
duke
parents:
diff changeset
    69
                                      m instanceof SortedMap));
90ce3da70b43 Initial load
duke
parents:
diff changeset
    70
        boolean permitsNullValues = (! (m instanceof ConcurrentMap ||
90ce3da70b43 Initial load
duke
parents:
diff changeset
    71
                                        m instanceof Hashtable));
90ce3da70b43 Initial load
duke
parents:
diff changeset
    72
        boolean usesIdentity = m instanceof IdentityHashMap;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    73
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    74
        System.err.println(m.getClass());
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    75
        put(m, 'A', true,  null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
        put(m, 'A', false, true);       // Guaranteed identical by JLS
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
        put(m, 'B', true,  null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
        put(m, new Character('A'), false, usesIdentity ? null : false);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
        if (permitsNullKeys) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
            try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
                put(m, null, true,  null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
                put(m, null, false, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
            }
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    84
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
        } else {
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    86
            try { m.get(null); fail(m.getClass().getName() + " did not reject null key"); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
            catch (NullPointerException e) {}
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    88
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    90
            try { m.put(null, true); fail(m.getClass().getName() + " did not reject null key"); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
            catch (NullPointerException e) {}
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
    92
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
        if (permitsNullValues) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
            try {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
                put(m, 'C', null, null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    97
                put(m, 'C', true, null);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    98
                put(m, 'C', null, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
            }
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   100
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
        } else {
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   102
            try { m.put('A', null); fail(m.getClass().getName() + " did not reject null key"); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
            catch (NullPointerException e) {}
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   104
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   106
            try { m.put('C', null); fail(m.getClass().getName() + " did not reject null key"); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
            catch (NullPointerException e) {}
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   108
            catch (Throwable t) { unexpected(m.getClass().getName(), t); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
        }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
    //--------------------- Infrastructure ---------------------------
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
    static volatile int passed = 0, failed = 0;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   114
    static void pass() { passed++; }
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   115
    static void fail() { failed++; (new Error("Failure")).printStackTrace(System.err); }
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   116
    static void fail(String msg) { failed++; (new Error("Failure: " + msg)).printStackTrace(System.err); }
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   117
    static void unexpected(String msg, Throwable t) { System.err.println("Unexpected: " + msg); unexpected(t); }
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   118
    static void unexpected(Throwable t) { failed++; t.printStackTrace(System.err); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   119
    static void check(boolean cond) { if (cond) pass(); else fail(); }
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   120
    static void check(String desc, boolean cond) { if (cond) pass(); else fail(desc); }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   121
    static void equal(Object x, Object y) {
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   122
        if(Objects.equals(x,y)) pass(); else fail(x + " not equal to " + y);
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   123
    }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   124
90ce3da70b43 Initial load
duke
parents:
diff changeset
   125
    public static void main(String[] args) throws Throwable {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   126
        try { realMain(args); } catch (Throwable t) { unexpected(t); }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   127
90ce3da70b43 Initial load
duke
parents:
diff changeset
   128
        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
12859
c44b88bb9b5e 7126277: Alternative String hashing implementation
mduigou
parents: 5506
diff changeset
   129
        if (failed > 0) throw new Error("Some tests failed");
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   130
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
}