HashMap源码解析-阿里云开发者社区

本解析源码来自JDK1.7，JDK1.7对String类型的key进行了区别处理，但是JDK1.8中已经做出了修改，所以本文不讨论相关内容

HashMap概要

HashMap是基于hash的map接口的非同步实现，与HashTable的区别HashTable是同步的，可以通过Map m = Collections.synchronizedMap(new HashMap(...));的方式对HashMap进行同步，但是推荐使用ConcurrentHashMap来进行线程安全保证
允许使用null键和null值
不保证映射顺序和顺序的不变性
在散列合理的情况下，HashMap的操作时间复杂度是O(1)
遍历HashMap的时间复杂度与HashMap的元素的个数（size）和HashMap的容量（table数组bucket的个数）有关，所以非必须设定较大的初始容量会造成遍历的效率变低
两个重要概念：capacity和loadFactor
- capacity 表示的是HashTable中的桶的数量，也即table数组的大小
- loadFactor 表示的是进行扩容之前，Hash Table的拥挤程度，它代表了HashMap空间和时间权衡，初始为0.75，这个值越大，空间消耗越小，但是put,get等操作的时间效率会降低
- 当HashTable的元素的数量 size>capacity*loadFactor时，HashMap进行扩容，大致会扩容至原先的2倍
- 如果HashMap的size可以预计，应当在初始化的时候设计initialCapacity>=size/loadFactor，从而避免频繁的扩容和rehash(扩容后需要重新计算hash值)操作，提高效率
通过HashMap返回的Iterator对HashMap遍历时，有fast-fail机制，即在遍历过程中如果出现对map的结构上的修改（更新已有key的value值不算结构修改）时会直接抛出异常，以免造成混乱，但是这种机制不保证一定可以正确执行（非同步）
设计初衷
Java中的两种存储结构
数组：寻址容易，插入和删除困难
链表：寻址困难，插入和删除容易
折中方案，链表的数组，即散列表是HashMap的底层存储数据结构

HashMap实现的接口

HashMap类头部

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap的Clone方法为浅拷贝，虽然创建了新的Entry，但是是基于原(key,value)对的，并没有创建新的(key,value)
HashMap实现了特殊的序列化机制，对key和value分别写入，在另一端分别读出(key,value)，然后将(key,value)对put进map的方法进行反序列化
Map接口主要方法

public interface Map<K,V> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    // Modification Operations
    V put(K key, V value);
    V remove(Object key);
    // Bulk Operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    // Views
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
    }
    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();
}

Entry HashMap的基本节点

HashMap的静态内部类Entry，主要成员 Key，Value，next，hash
table Entry的数组，Entry包含指向下一节点的引用next，从而table为链表的数组

 /**
     * 大小必要时可调整的数组。 其长度必须是2的指数次.
     */ 
 transient Entry<K,V>[] table;   //transient 序列化时不被序列化
 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    ...........
}

几个重要成员

默认的capacity（table数组大小）为16
默认loadFactor（装载因子）为0.75
初始化空HashMap时，table为空，不包含元素
HashMap最大容量为 2^30
threshold用来表示扩容的阈值，大致为capacity*loadFactor
modCount用来实现fail-fast机制，通过计数HashMap结构修改的次数来确认在遍历过程中没有被修改
hashSeed用来影响String类型的key的hash值的计算

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final Entry<?,?>[] EMPTY_TABLE = {};
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    transient int size;
    // If table == EMPTY_TABLE then this is the initial capacity at which the
    // table will be created when inflated.
    int threshold;
    final float loadFactor;
    transient int modCount;
    transient int hashSeed = 0;

构造方法

主要包含两种构造方法:

HashMap（int initialCapacity, float loadFactor）
- initialCapacity table数组的初始化大小，默认为16，如果不是2的指数次幂，调整为大于initialCapacity的最小的2的指数幂，但是不能大于MAXIMUM_CAPACITY（默认为2^30）
- loadFactor 影响table容量调整，当数组容量loadFactor<HashMap元素（Entry）个数时进行扩容，默认为0.75，表示HashMap空间换时间的效率，loadFactor越大效率越低，范围0-1
HashMap(Map<? extends K,? extends V> m)
- 按照给定的map的大小与defaultInitialCapacity和defaultLoadFactor进行初始化
- 将原map中的数据拷贝到新的map中
- 这个过程中需要对Hash Table数组进行扩容（inflateTable），首先取大于等于原map size的最小的2的指数作为capacity，然后乘以loadFactor计算threshold
- 这里面有一个小算法Integer.highestbit((number-1)<<1)来求大于等于number的最小2的指数。本来number右移一位取二进制最高位即为所求，但是考虑number本来就是2的指数时直接取number的情况

    /**根据指定容量和负载因子构造HashMap*/ 
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

    /**根据指定的容量和默认的负载因子构造HashMap*/
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    //默认的空的构造器
    public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }
    /**通过指定一个Map对象进行构造*/
    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);  
        putAllForCreate(m);
    }
    private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    } 
    private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

元素存储位置的计算 hash值

String类型的key的hashcode是根据与字符串内容相关的，由于可能引起很多碰撞，所以值单独计算
Object类型的key的HashCode是基于其内存地址的。为了充分利用Integer值的高位，需要将高位的影响引入低位，（由于多数map的length是比较小的）
由于length是2的指数倍，所以可以用hash&（length-1）代替 hash%length，位运算有更高的效率

    final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }  
    static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

存入更新元素 put(key,value)

如果是key为null，遍历查找table中key是否有null，如果有更新value，否则添加null，value节点
如果key不为null，根据Key的hashcode获取Hash值，根据Hash计算其在table中的索引，hash值计算时利用高位与低位进行异或操作，加入高位因素，来减少Hash碰撞
由于tablelength 都是2的指数次幂，所以indexFor用 HashCode&（table.lenght-1）取HashCode的低位
如果table[i]不为null(并不表示Hash值相同，HashCode不同也可能碰撞)，也就是发生了Hash碰撞，如果存在与keyHash相等（equals）或相同（==）的key，那么更新value
如果table[i]为null，或者table[i]链表中不存在Hash值与Key相同且equals函数返回true的情况就根据Hash值添加新的节点
addEntry()方法首先判断大小是否超过阈值，然后使用头插法，插入元素
此外HashMap还实现了一个私有的putForCreate()方法，用来在初始化创建map时使用，由于不需要检查hash table是需要扩容以及modcount检查，所以有更高的效率

NOTE
在判断插入Entry是否为覆盖时，会先判断Key的hashCode是否和map中的key相等，然后判断Equals方法或者==，所以如果重写了equals方法，要记得重写hashcode方法，使得其逻辑相同，否则即使equals方法判断相等也不会发生覆盖

public V put(K key, V value) {
    // HashMap允许存放null键和null值。
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。
    if (key == null)
        return putForNullKey(value);
    // 根据key的keyCode重新计算hash值。
    int hash = hash(key);//注意这里的实现是jdk1.7和以前的版本有区别的
    // 搜索指定hash值在对应table中的索引。
    int i = indexFor(hash, table.length);
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    // 如果i索引处的Entry为null，表明此处还没有Entry。
    modCount++;
    // 将key、value添加到i索引处。
    addEntry(hash, key, value, i);
    return null;
}
/**产生哈希码*/
final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        /*加入高位计算，防止低位不变，高位变化是引起hash冲突*/
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
/**产生索引，由于索引产生是不确定的，因此也就造成了HashMap顺序的不确定性。
   需要注意的是不同的hash产生的索引完全有可能相同的
  该方法的实现十分的巧妙，它通过h & (length-1)来的到对象保存的
  索引，有可知道底层数组为2的n次方，这在速度上就有了明显的优化
  */
static int indexFor(int h, int length) {
        return h & (length-1);
    }
    private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }  
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }  
    private void putForCreate(K key, V value) {
        int hash = null == key ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        /**
         * Look for preexisting entry for key.  This will never happen for
         * clone or deserialize.  It will only happen for construction if the
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
         */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }
        createEntry(hash, key, value, i);
    }

读取元素 get(key)

如果key为null，不能使用hash码来定址，只能通过遍历table的方法来找null
如果key不为null，就可以通过计算key的hash值定位到table数组中对应的链表，然后遍历链表找到hash值和equals方法返回true或==成立的节点

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    } 
    private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }  
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

元素删除 remove(key)

根据key的hash值定位table数组位置，然后遍历链表，找到hash值与equals为true或==成立点，做链表删除操作
其中删除注意头结点的处理（e==prev），直接 table[i]=next

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    } 
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
        return e;
    }

元素查找 containsKey(key) containsValue(value)

containsKey(key) 先用key的hash码定位到table数组中的对应链表，然后遍历链表进行查询，效率取决于链表的长度
containsValue(value) 对table数组进行遍历，然后遍历数组中的每个链表，时间复杂度取决于table数组的长度与map.size()，效率低

    public boolean containsValue(Object value) {
        if (value == null)
            return containsNullValue();
        Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    } 
    private boolean containsNullValue() {
        Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (e.value == null)
                    return true;
        return false;
    }  
    public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

调整大小 resize(newLength)

调整的时机（负载因子）x（容量）>（Map 大小），则调整 Map大小为之前的二倍，该过程包含了table的复制，性能消耗较大，如果map大小已知，可以在初始化时合理设定map的初始大小，避免扩容。
如果数组大小已经到达最大容量，将阈值置为Integer.MAX_VAlUE,不再进行扩容
新申请数组，重新定址并将原数组中的Entry转移到新数组中，由于容量变化，即使Hash值不变，Entry的index也会改变，index=hash&(length-1),hash值对length取余，length变化，index也会变化
transfer使用头插法将原hashtable所有元素进行复制，首先保存原原数组的e.next节点，然后将e头插插入新的hash table，e移动到原数组next

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    } 
    /**
     * Transfers all entries from current table to newTable.
     */
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

迭代器 Iterator

由于数组大小调整后，元素的index都需要重新计算，所以HashMap并不能保证元素的遍历顺序不变

KeyIterator，ValueIterator都是基于HashIterator的，只是重写的next方法
由于hash table 是稀疏的，所以需要找到第一个元素，关键算法while (index < t.length && (next = t[index++]) == null)，从开始找到第一个table[i]不为null的节点
next算法要考虑current为一个链表的尾节点，这时需要查找table中下一个不为null的节点
Iterator只支持删除不支持添加

    private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;        // next entry to return
        int expectedModCount;   // For fast-fail
        int index;              // current slot
        Entry<K,V> current;     // current entry
        HashIterator() {
            expectedModCount = modCount;
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }
        public final boolean hasNext() {
            return next != null;
        }
        final Entry<K,V> nextEntry() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }
        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }  
    private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }
    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }
    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

KeySet视图

通过KeySet视图更改HashMap和通过HashMap做出的更改有同样的效果，会相互影响
set视图支持remove，removeAll，retainAll,clear删除操作但是不支持添加操作（add,addAll）
通过继承Collection的add方法，当调用add方法时直接抛出UnsupportedOperationException，由于addAll方法需要调用add，也就禁止了addAll方法

    public Set<K> keySet() {
        Set<K> ks = keySet;
        return (ks != null ? ks : (keySet = new KeySet()));
    }
    private final class KeySet extends AbstractSet<K> {
        public Iterator<K> iterator() {
            return newKeyIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsKey(o);
        }
        public boolean remove(Object o) {
            return HashMap.this.removeEntryForKey(o) != null;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }  
//Collection.java
    public boolean add(E e) {
        throw new UnsupportedOperationException();
    }

Values视图

Values返回的是Collection而不是Set，因为Values不保证元素不重复
Values更改与HashMap的更改等效，相互影响
Values同样只支持删除操作，不支持添加操作
EntrySet与Values类似

疑问：为什么EntrySet()还要调用EntrySet0()，并没有发现这一步调用的必要性

    public Collection<V> values() {
        Collection<V> vs = values;
        return (vs != null ? vs : (values = new Values()));
    }
    private final class Values extends AbstractCollection<V> {
        public Iterator<V> iterator() {
            return newValueIterator();
        }
        public int size() {
            return size;
        }
        public boolean contains(Object o) {
            return containsValue(o);
        }
        public void clear() {
            HashMap.this.clear();
        }
    }  
    public Set<Map.Entry<K,V>> entrySet() {
        return entrySet0();
    }
    private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet());
    }  
    private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return newEntryIterator();
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;
            Entry<K,V> candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

解决hash碰撞的方法

开放定址法
从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
再哈希法
链地址法（JDK1.7使用）
建立一公共溢出区

modCount fast-fail机制

modCount 记录修改此列表的次数：包括改变列表的结构，改变列表的大小，打乱列表的顺序等使正在进行迭代产生错误的结果.(仅仅设置元素的值并不是结构的修改),如果在使用迭代器的过程中有其他的线程修改了Map就会抛出ConcurrentModificationException这就是Fail-Fast机制。

Clone方法

Clone实现的是浅拷贝，虽然重新创建了Entry但是并没有重新创建key，value，即如果通过原HashMap的key的引用改变了key的属性，clone出来的HashMap的key也会跟着改变，克隆出来的Map的数组的大小也不一定与原Map相同

首先会创建一个空的HashMap对象
然后对该HashMap进行扩容，容量大小取Math.min(当前table大小，HashMap的最大容量，当前的Size*（Math.min(1/loadFactor,4))，克隆出来的HashMap的数组初始大小并不会与当前Map一致，而是考虑合理的初始化loadFactor之后的结果。
最后调用putAllForCreate(this)依次将当前Map的(key,value)放到Map中去，过程中虽然创建了新的Entry但是并没有创建新的key，value，通过原HashMap和通过克隆出来的HashMap改变(key,value)效果是等同的。

    public Object clone() {
        HashMap<K,V> result = null;
        try {
            result = (HashMap<K,V>)super.clone();
        } catch (CloneNotSupportedException e) {
            // assert false;
        }
        if (result.table != EMPTY_TABLE) {
            result.inflateTable(Math.min(
                (int) Math.min(
                    size * Math.min(1 / loadFactor, 4.0f),
                    // we have limits...
                    HashMap.MAXIMUM_CAPACITY),
               table.length));
        }
        result.entrySet = null;
        result.modCount = 0;
        result.size = 0;
        result.init();
        result.putAllForCreate(this);
        return result;
    } 
    private void putAllForCreate(Map<? extends K, ? extends V> m) {
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
            putForCreate(e.getKey(), e.getValue());
    }
    private void putForCreate(K key, V value) {
        int hash = null == key ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        /**
         * Look for preexisting entry for key.  This will never happen for
         * clone or deserialize.  It will only happen for construction if the
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
         */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }
        createEntry(hash, key, value, i);
    }
    void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

序列化

存储hashmap的元素的数组被声明为transient，即在初始化时忽略，因为相同对象的Hash值在不同机器上可能是不同的，所以直接序列化后map的get(key)方法会出现错误
HashMap重写了readObject()和writeObject()方法来保证序列化的正确性
策略在序列化时，针对Entry的key与value分别单独序列化，当反序列化时，再单独处理即可

 transient Entry<K,V>[] table;   //transient 序列化时不被序列化
private void writeObject(java.io.ObjectOutputStream s)
    throws IOException
{
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();

    // Write out number of buckets
    if (table==EMPTY_TABLE) {
        s.writeInt(roundUpToPowerOf2(threshold));
    } else {
       s.writeInt(table.length);
    }

    // Write out size (number of Mappings)
    s.writeInt(size);

    // Write out keys and values (alternating)
    if (size > 0) {
        for(Map.Entry<K,V> e : entrySet0()) {
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }
}

private static final long serialVersionUID = 362498820763181265L;

private void readObject(java.io.ObjectInputStream s)
     throws IOException, ClassNotFoundException
{
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " +
                                           loadFactor);
    }

    // set other fields that need values
    table = (Entry<K,V>[]) EMPTY_TABLE;

    // Read in number of buckets
    s.readInt(); // ignored.

    // Read number of mappings
    int mappings = s.readInt();
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                           mappings);

    // capacity chosen by number of mappings and desired load (if >= 0.25)
    int capacity = (int) Math.min(
                mappings * Math.min(1 / loadFactor, 4.0f),
                // we have limits...
                HashMap.MAXIMUM_CAPACITY);

    // allocate the bucket array;
    if (mappings > 0) {
        inflateTable(capacity);
    } else {
        threshold = capacity;
    }

    init();  // Give subclass a chance to do its thing.

    // Read the keys and values, and put the mappings in the HashMap
    for (int i = 0; i < mappings; i++) {
        K key = (K) s.readObject();
        V value = (V) s.readObject();
        putForCreate(key, value);
    }
}
private void putForCreate(K key, V value) {
    int hash = null == key ? 0 : hash(key);
    int i = indexFor(hash, table.length);

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }

    createEntry(hash, key, value, i);
}

与HashTable的区别

继承的对象不同 HashMap extends AbstractMap HashTable extends Dictionary
HashTable 是同步的，且不允许key为null，其根据hash值获得索引的方法也不同，都是取模，但是HashMap采用位运算更高效

  public synchronized V put(K key, V value) {  //###### 注意这里1
    // Make sure the value is not null
    if (value == null) { //###### 注意这里 2
      throw new NullPointerException();
    }
    // Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode(); //###### 注意这里 3
    int index = (hash & 0x7FFFFFFF) % tab.length;### 注意这里 4
    for (Entry e = tab[index]; e != null; e = e.next) {
      if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
      }
    }
    modCount++;
    if (count >= threshold) {
      // Rehash the table if the threshold is exceeded
      rehash();
      tab = table;
      index = (hash & 0x7FFFFFFF) % tab.length;
    }
    // Creates the new entry.
    Entry e = tab[index];
    tab[index] = new Entry(hash, key, value, e);
    count++;
    return null; 
}

与JDK1.8的区别

JDK1.8不再单纯使用链表来进行存储，而是使用链表（元素较少）与红黑树（元素较多）
在jdk8中，仍然会根据key.hashCode()计算出hash值，再通过这个hash值去定位这个key，但是不同的是，当发生冲突时，会采用链表和红黑树两种方法去处理，当结点个数较少时用链表（用Node存储），个数较多时用红黑树（用TreeNode存储），同时结点也不叫Entry了，而是分成了Node和TreeNode。再最坏的情况下，链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。jdk8中的HashMap中定义了一个变量TREEIFY_THRESHOLD，当节点个数>= TREEIFY_THRESHOLD - 1时，HashMap将采用红黑树存储
不再区别对待String类key
由于String对象的Hash值计算方法较弱，jdk7中在面对key为String的时候采用了区别对待，会有alternative hashing，但是这个在jdk8中已经被删除了

HashMap源码解析