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源码解析

HashMap概要

HashMap实现的接口

Entry HashMap的基本节点

几个重要成员

构造方法

元素存储位置的计算 hash值

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

读取元素 get(key)

元素删除 remove(key)

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

调整大小 resize(newLength)

迭代器 Iterator

KeySet视图

Values视图

解决hash碰撞的方法

modCount fast-fail机制

Clone方法

序列化

与HashTable的区别

与JDK1.8的区别

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

HashMap源码解析

HashMap概要

HashMap实现的接口

Entry HashMap的基本节点

几个重要成员

构造方法

元素存储位置的计算 hash值

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

读取元素 get(key)

元素删除 remove(key)

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

调整大小 resize(newLength)

迭代器 Iterator

KeySet视图

Values视图

解决hash碰撞的方法

modCount fast-fail机制

Clone方法

序列化

与HashTable的区别

与JDK1.8的区别

热门文章

最新文章

相关课程

相关电子书

相关实验场景

推荐镜像