Java源码HashMap

 HashMap类

　　https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

　　public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

　　子类：LinkedHashMap，PrinterStateReasons

　　一、介绍

　　HashMap继承了AbstractMap类，AbstractMap类实现Map接口中的一些方法，是为了最大限度地减少实现Map接口需要进行的工作量，提高代码重用。　　

　　Cloneable接口可以理解为一个标记接口，它并没有定义方法。当一个对象调用Object的clone方法时，如果这个对象没有实现Cloneable接口，会引发CloneNotSupportedException异常。（关于对象的拷贝，有深拷贝和浅拷贝的知识）clone方法执行的是浅拷贝，这个接口就是指示可以使用Object的clone方法。

　　HashMap类实现了Map接口中所有的“可选操作”，允许key和value为null，非同步。

　　HashTable类与HashMap几乎一致，区别在于HashTable不允许key和value为null，而且是同步的。

　　HashMap无法保证其中键值对的顺序，即它无法保证键值对的顺序会一直保持不变。

　　HashMap类为基本的get和put操作，提供了常数时间的性能。

　　HashMap的集合视图上的迭代器所需要的时间和（HashMap实例的容量加上键值对的数量）成正比。所以，当需要考虑迭代器的性能时，不要把HashMap实例的容量（capacity属性）设置得太高，或者别把load factor设置得太低。

　　如上提到的，一个HashMap实例有两个最重要的参数影响着它的性能：初始的capacity值和load factor值。

　　capacity是哈希表中桶的数量，它的初始值代表着HashMap实例创建时桶的数量。

　　load factor，在这个哈希表实例进行容量自动增长前，用来度量这个哈希表“满”的程度。

　　当哈希表中中键值对条目的数量超过load-factor和当前capacity的乘积时，哈希表就会被重新映射（is rehashed），这意味着它内部的数据结构被重建了，结果便是“新”的哈希表拥有了两倍的桶数。（像数组的自动扩容）

　　通常，HashMap的默认load-factor是0.75，这在时间代价和空间代价提供了一个很好的平衡。

　　load-factor过高会减少空间开销，但会增加查找成本，这体现在类中的大部分操作中，包括get和put。

　　因此，在设置初始的capacity值时，需要好好考虑HashMap中键值条目的数量以及负载因子，以尽可能减少重新散列的次数。如果初始capacity大于（最大入口数除以负载因子），哈希表就不会进行重新散列。

　　如果你有比较多的键值对需要存进HashMap，最好在创建它时配置一个足够大的capacity，比起容量不足然后进行重散列，这样可以更有效地存储映射。

　　需要注意的是，如果多个key的hashcode()值相同，会降低哈希表的性能。为了改善这种情况，若key实现了Comparable接口，HashMap可能会利用key之间的比较顺序（comparison order）来消除“并列”（break ties）。

　　由于HashMap是不同步的，当多个线程并发访问一个HashMap时，若其中至少一个线程对HashMap进行了结构性的修改，那么就必须在外部进行同步（it must be synchronized externally）。这通常是通过自然封装了HashMap的对象上完成的，如果这样的对象不存在，那么这个HashMap就应该通过Collections.synchronizedMap方法装饰，并且最好在创建时就进行，以防止这个HashMap上有以外的非同步访问：

Map m = Collections.synchronizedMap(new HashMap(...));

　　（所谓的结构性修改（structural modification）是增加or删除键值记录的操作，如果仅仅是改变其中某个key关联的value，不属于结构性操作。）

　　HashMap类的所有集合视图的产生方法所返回的迭代器都具有“快速失效”属性：当一个实例在迭代器被创建后被进行了结构性的修改（除了通过迭代器的remove方法），迭代器会抛出一个 ConcurrentModificationException。所以，面对并发修改，迭代器会明确而快速地失效，而不是仍然承担着并不确定的行为的风险。


　　需要注意的是，迭代器并不保证它的“快速失效”属性，因为在存在非同步并发修改的情形下，不可能做出任何硬性保证。

　　所以，迭代器的快速失效行为应该仅用于检测错误。

　　二、HashMap的嵌套类

　　继承自AbstractMap的嵌套类：AbstractMap.SimpleEntry, AbstractMap.SimpleImmutableEntry

　　继承自Map接口的嵌套类：Map.Entry

　　事实是，HashMap中有许多嵌套类：

　　如图：

　　Node类实现了Map.Entry接口，源码描述为“Basic hash bin node, used for most entries”，即为存储单条键值映射记录的数据结构；

　　TreeNode类是“Entry for Tree bins”，这个是在某些情况下可以用来替代Node的（when bins get too large, they are transformed into bins of TreeNodes），该类继承自LinkedHashMap.Entry。

　　KeySet、Values、EntrySet的嵌套类和返回集合视图的三个方法相关；

　　本来不打算解析嵌套类的，但是它们和很多方法息息相关，所以干脆好好分析一波！

　　1、HashMap的属性

　　如图，基本可以通过名称判断相关属性的作用。

　　size，表示当前map中键值映射记录的条数；

　　带treeify字段的属性，好像是和Node转换成TreeNode的操作有关的；

　　threshold意思是门槛、开始，用于判断map是否进行resize操作的标准。

　　table，一个包含Node元素的数组，会在第一次使用时被初始化。这个数组的长度，总是整数2的幂。

　　modCount，记录这个map被结构性修改的次数；

　　2、 static class Node implements Map.Entry　

　　注意到，其中key为final，但是value不为final，关注下put方法中包含相同key时的处理方法。

　　这里的hash暂时没明白干嘛的；

　　next是不是表明了，键值映射记录的存储方式是链表？

/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;

        Node(int hash, K key, V value, Node 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() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        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;
        }
    }

　　三、构造器

　　根据Java集合框架的规约，集合类都应该提供一个无参构造器和一个Collection or Map类型的单参构造器，前者用于构造空的集合，后者用于复制另一个集合。

• 　　HashMap()，构造一个空的HashMap实例，默认capacity为16，默认load-factor是0.75。
• 　　HashMap(Map m)，这里的初始capacity，满足需求即可。
• 　　HashMap(int initialCapacity)
• 　　HashMap(int initialCapacity, float loadFactor)

　　四、方法

　　1、public int size()

　　返回键map中值映射记录的条数；

　　2、public boolean isEmpty()

　　如果map中还没有存储键值映射的记录，返回true。

public boolean isEmpty() {
        return size == 0;
    }

　　3、static final int hash(Object key)

　　待会看看它的用法。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

　　4、public V get(Object key)

　　返回指定key所映射的value值；若map不包含此key的映射，返回null。

　　特殊的情况是，这个key所映射的value值恰好为null，这时就需要利用containKey()来区分这两种情况了。

　　5、public boolean containsKey(Object key)

　　查询map中是否包含指定的key

　　6、public V put(K key, V value)

　　关联指定的key和value，即是他们称为map中的键值对，可以通过key查到这个value。

　　如果key存在，对value进行替换。

　　7、public void putAll(Map m)

　　将指定map中的所有映射复制到此map。

　　如果key已存在，则其值会被新的替换。

　　8、public V remove(Object key)

　　9、public void clear()

　　清空map

　　10、public boolean containsValue(Object value)

　　判断是否map中有一个或者多个key的映射值为指定的value。

　　11、public Set keySet()

　　Returns a Set view of the keys contained in this map.

　　12、public Collection values()

　　Returns a Collection view of the values contained in this map.

　　13、public Set> entrySet()

　　Returns a Set view of the mappings contained in this map

　　14、public V putIfAbsent(K key, V value)

　　If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.

　　15、public boolean remove(Object key, Object value)

　　16、public boolean replace(K key, V oldValue, V newValue)

　　Replaces the entry for the specified key only if currently mapped to the specified value.