JDK HashMap ( )

JDK HashMap ( )

0.

HashMap ( )

HashMap

  • HashMap Map key-value HashMap key value null HashMap
  • jdk1.8 HashMap + HashMap hashCode jdk1.8 8 64

HashMap

HashMap == + +

  • HashMap 16 8
  • 64 (2 ) ( )
  • 64 8 ( )
  • 6

8 64( )

( ) i i i = hash & (cap - 1) cap

( )

  • ( ) 64 8 64 treeifyBin()
  • 8 64

HashMap

  1. ;
  2. null null;
  3. ;
  4. jdk1.8 + jdk1.8 + + ;
  5. > 8 ( ) 64 ;

1.HashMap

HashMap debug

@Test public void test01() { HashMap<String, Integer> hashMap = new HashMap(); hashMap.put("a", 3); hashMap.put("b", 4); hashMap.put("c", 5); hashMap.put("a", 88888);// System.out.println(hashMap); }

{a=88888, b=456, c=789}

  1. HashMap<String, Integer> hashMap = new HashMap();
    HashMap HashMap put 16 ( 16 )
    Node[] table
    jdk1.8 Entry[] table

  2. put("a", 3)
    "a"
    String hashCode() ( ) Node
    table[i]
    i Node ( )
    <"a", 3>

    3

  3. <"b", 4>
    hashCode() 3 null( )
    "a"
    "b"
    hash
    <"b", 4>

  4. <"a", 88888>
    "a"
    hashCode() 3
    "a"
    hash hash
    "a"
    String equals()

    • value value
    • key 8 64
  5. 2

  6. hash key jdk1.8 + + 8 64

    + + JDK1.8

  7. jdk1.8

    • jdk1.8 HashMap + HashMap HashMap n O(n)
    • jdk1.8 O(logn)

  • size HashMap ( )
  • threshold = capacity * loadFactor size resize HashMap 2

2.HashMap

  1. HashMap hash hash

    • key hashCode hash key null 0 16
      (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    • 16
  2. hashCode
    key value 8


  3. key jdk8 jdk8 +

  4. hashCode
    equals

    • value value

    • ( )

      • key key value
      • ( )

3.HashMap


  • HashMap Cloneable
  • HashMap Serializable HashMap
  • HashMap AbstractMap Map Map

HashMap AbstractMap AbstractMap Map HashMap Map ArrayList LinkedLis Java Josh Bloch Java Java jdk

( )

Java HashMap + +

hash

O(1) O(k) O(log k) k

2.HashMap

/* * */ private static final long serialVersionUID = 362498820763181265L; /** * HashMap 2 n 16 */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; /** * 2 30 */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * 8 */ static final int TREEIFY_THRESHOLD = 8; /** * 6 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 64 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * Node bucket */ transient Node<K,V>[] table; /** * entrySet() */ transient Set<Map.Entry<K,V>> entrySet; /** * */ transient int size; /** * */ transient int modCount; /** * threshold = capacity * loadFactor */ int threshold; /** * */ final float loadFactor;

1 16 2 30 64

2 0.75

3 64 8 6

2.1 DEFAULT_INITIAL_CAPACITY

2 n :

// 16 1 << 4 1*2 4 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

2 n 2 10 ?

HashMap

// 0.75) HashMap HashMap(int initialCapacity)

HashMap key hash HashMap

hash % length

hash & (length - 1)
hash % length hash & ( length - 1) length 2 n ( )

8

3 & (8 - 1) = 3 2 & (8 - 1) = 2
( )3 2

( ) 2 n

9( 2 n ) hash

hash & (length - 1)
( )

HashMap 2 n


HashMap length 10 2 n

HashMap<String, Integer> hashMap = new HashMap(10);

HashMap tableSizeFor(initialCapacity) length length 2 n ( 10 10 2 n 16)

static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

HashMap initialCapacity HashMap capacity 2

tableSizeFor(initialCapacity);
initialCapacity 2

  1. int n = cap - 1;
    1
    cap 2 cap 2 1 capacity cap 2 ( )

  2. n + 1

    n 0 cap - 1 0 0

    n+1
    capacity 1

  3. 32bit

    n |= n >>> 16;
    32 1 tableSizeFor initialCapacity MAXIMUM_CAPACITY(2 ^ 30) MAXIMUM_CAPACITY MAXIMUM_CAPACITY 30 1 MAXIMUM_CAPACITY 30 1 1 2 ^ 30

tableSizeFor(initialCapacity);
capacity initialCapacity initialCapacity 2 n

2.2 DEFAULT_LOAD_FACTOR

0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

2.3 MAXIMUM_CAPACITY

static final int MAXIMUM_CAPACITY = 1 << 30; //2 30

2.4 TREEIFY_THRESHOLD

8 jdk1.8

// bucket static final int TREEIFY_THRESHOLD = 8;

Map 8

8 HashMap 8 bin( bucket ) 8

HashMap

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins. In usages with well-distributed user hashCodes, tree bins are rarely used. Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution (http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5) * pow(0.5, k)/factorial(k)). The first values are: ( TREEIFY_THRESHOLD) hashCode 0.75 0.5 k (exp(-0.5)*pow(0.5, k)/factorial(k) 0: 0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 more: less than 1 in ten million

TreeNodes( ) Nodes( ) bin(bucket ) TreeNodes TREEIFY_THRESH LD bin(bucket ) bin(bucket ) 8 6 bin(bucket )

TreeNodes TreeNodes

hashCode bin bin bin hashCode jdk hash hashCode bin bin 8 0.00000006 8 30 Java

hashCode 8 8

  • Poisson [ ]

    A

  • log(n) 8 log(8) = 3 n/2 8 8/2 = 4 6 6/2 = 3 log(6) = 2.6

2.5 UNTREEIFY_THRESHOLD

6

// bucket static final int UNTREEIFY_THRESHOLD = 6;

2.6 MIN_TREEIFY_CAPACITY

Map 4*TREEIFY_THRESHOLD(8)

// static final int MIN_TREEIFY_CAPACITY = 64;

2.7 table( )

table n

// transient Node<K,V>[] table;

jdk1.8 HashMap table HashMap jdk8 Entry<K,V> jdk1.8 Node<K,V> Map.Entry<K,V>

2.8 entrySet

// transient Set<Map.Entry<K,V>> entrySet;

2.9 size( )

HashMap

// transient int size;

size HashMap K-V table

2.10 modCount

HashMap

// map transient int modCount;

2.11 threshold( )

*

// * int threshold;

2.12 loadFactor( )

// final float loadFactor;//0.75f

  • loadFactor HashMap HashMap hash HashMap size/capacity capacity capacity table length
  • loadFactor loadFactor 0.75f
  • HashMap HashMap 75% HashMap rehash HashMap
  • HashMap loadFactor
// HashMap HashMap(int initialCapacity, float loadFactor);
  • loadFactor 0.75 threshold 12

    loadFactor 1 (entry) loadFactor 0 (entry)


0.4 16*0.4--->6 6 0.9 16*0.9--->14

0.75

  • threshold capacity( 16) * loadFactor( 0.75)==12

    Size >= threshold(12) resize( ) HashMap

3.

3.1Node

Node hash key hash

static class Node<K,V> implements Map.Entry<K,V> { final int hash;//hash key hash final K key;// V value;// Node<K,V> next;// node Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() {// c++ Key/Value null, 0 return Objects.hashCode(key) ^ Objects.hashCode(value);// Key/Vaule } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }

3.2TreeNode

TreeNode LinkedHashMap Entry LInkedHashMap.Entry TreeNode prev

// HashMap , static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; //red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; //needed to unlink next upon deletion boolean red; } // LinkedHashMap static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

4.HashMap

HashMap

4.1 HashMap()

HashMap 16 0.75

public HashMap() { // 0.75 loadFactor this.loadFactor = DEFAULT_LOAD_FACTOR; }

4.2 HashMap(int initialCapacity)

0.75 HashMap

// public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }

4.3 HashMap(int initialCapacity float loadFactor)

HashMap

/* initialCapacity loadFactor: */ public HashMap(int initialCapacity, float loadFactor) { // initialCapacity 0 if (initialCapacity < 0) // 0 IllegalArgumentException throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // initialCapacity MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY) // MAXIMUM_CAPACITY MAXIMUM_CAPACITY initialCapacity initialCapacity = MAXIMUM_CAPACITY; // loadFactor 0 if (loadFactor <= 0 || Float.isNaN(loadFactor)) // IllegalArgumentException throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // HashMap loadFactor this.loadFactor = loadFactor;// this.threshold = tableSizeFor(initialCapacity); } // tableSizeFor /* cap 2 n ------------------------------------------------------- cap = 10 n = 10 -1 => 9 n |= n >>> 1 n = (n | n >>> 1), ( Java ) 9 => 0b1001 9 >>> 1 => 0b0100 n |= n >>> 1; ===> 0b1001 | 0b0100 => 0b1101 n |= n >>> 2; ===> 0b1101 | 0b0011 => 0b1111 n |= n >>> 4; ===> 0b1111 | 0b0000 => 0b1111 n |= n >>> 8; ===> 0b1111 | 0b0000 => 0b1111 n |= n >>> 16; ===> 0b1111 | 0b0000 => 0b1111 0b1111 => 15 return 15 + 1 => 16 ------------------------------------------------------- cap 1 n cap int n = cap; cap => 16 tableSizeFor(int cap) cap = 16 n = 16 16 => 0b10000 16 >>> 1 => 0b01000 n |= n >>> 1; ===> 0b10000 | 0b01000 => 0b11000 n |= n >>> 2; ===> 0b11000 | 0b00110 => 0b11110 n |= n >>> 4; ===> 0b11110 | 0b00001 => 0b11111 n |= n >>> 8; ===> 0b11111 | 0b00000 => 0b11111 n |= n >>> 16; ===> 0b11111 | 0b00000 => 0b11111 0b11111 => 31 return 31 +1 => 32 cap = 16 , n = cap -1 = 15 15 => 0b1111 n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; 15 return 15 + 1 = 16 cap 2 1 cap(32) cap(16) 2 */ static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

this.threshold = tableSizeFor(initialCapacity);
?

**tableSizeFor(initialCapacity)** 2 n 2 n

tableSizeFor threshold bug

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

threshold HashMap size threshold

jdk8 table table put put threshold

4.4 HashMap(Map<? extends K, ? extends V> m)

Map

// Map HashMap public HashMap(Map<? extends K, ? extends V> m) { // loadFactor 0.75 this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

putMapEntries()

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { // int s = m.size(); if (s > 0) {//0 if (table == null) { // table // s m float ft = ((float)s/loadFactor) + 1.0F;// int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);// float int // t 2 n if (t > threshold) threshold = tableSizeFor(t); } // table m else if (s > threshold) resize(); // m HashMap for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); // key value hashmap putVal(hash(key), key, value, false, evict); } } }

float ft = ((float)s/loadFactor) + 1.0F;
1.0F

(float)s/loadFactor
1.0F (int)ft resize ( ) + 1.0F

6 6/0.75 8 8 2 n

if (t > threshold) threshold = tableSizeFor(t);
8 8 +1 16


\

JDK HashMap ( )