Java集合深度解析之全面解析HashMap

电玩女神 2022-03-31 08:16 319阅读 0赞

**目录**

一、概述：

二、hashcode详解

一、hashcode是什么？

1、hash和hash表是什么？

2、hashcode

二、hashcode有什么作用呢？

三、equals方法和hashcode的关系？

四、为什么equals方法重写的话，建议也一起重写hashcode方法？

三、HashMap源码剖析

四、总结与详解

1、首先要清楚HashMap的存储结构

2、首先看链表中节点的数据结构：

3、初始容量和加载因子

详细理解加载因子

4、HashMap中key和value都允许为null

5、重点分析下HashMap中用的最多两个的方法put和get

6、关于扩容

7、注意containsKey方法和containsValue方法

8、重点来分析下求hash值和索引值的方法

9、为什么初始化容量为2的次幂

10、为什么最大容量是2的30次方

五、java1.8改进

--------------------

# 一、概述： #

HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70][]

HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

原理图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 1][]

# 二、hashcode详解 #

## 一、hashcode是什么？ ##

### 1、hash和hash表是什么？ ###

想要知道这个hashcode，首先得知道hash，通过百度百科看一下

![20190102191019620.png][]

![20190102191035853.png][]

hash是一个函数，该函数中的实现就是一种算法，就是通过一系列的算法来得到一个hash值，这个时候，我们就需要知道另一个东西，hash表，通过hash算法得到的hash值就在这张hash表中，也就是说，hash表就是所有的hash值组成的，有很多种hash函数，也就代表着有很多种算法得到hash值，如上面截图的三种，等会我们就拿第一种来说。

### 2、hashcode ###

有了前面的基础，这里讲解就简单了，hashcode就是通过hash函数得来的，通俗的说，就是通过某一种算法得到的，hashcode就是在hash表中有对应的位置。

每个对象都有hashcode，对象的hashcode怎么得来的呢？

首先一个对象肯定有物理地址，在别的博文中会hashcode说成是代表对象的地址，这里肯定会让读者形成误区，对象的物理地址跟这个hashcode地址不一样，hashcode代表对象的地址说的是对象在hash表中的位置，物理地址说的对象存放在内存中的地址，那么对象如何得到hashcode呢？通过对象的内部地址(也就是物理地址)转换成一个整数，然后该整数通过hash函数的算法就得到了hashcode，所以，hashcode是什么呢？就是在hash表中对应的位置。这里如果还不是很清楚的话，举个例子，hash表中有 hashcode为1、hashcode为2、(...)3、4、5、6、7、8这样八个位置，有一个对象A，A的物理地址转换为一个整数17(这是假如)，就通过直接取余算法，17%8=1，那么A的hashcode就为1，且A就在hash表中1的位置。肯定会有其他疑问，接着看下面，这里只是举个例子来让你们知道什么是hashcode的意义。

## 二、hashcode有什么作用呢？ ##

前面说了这么多关于hash函数，和hashcode是怎么得来的，还有hashcode对应的是hash表中的位置，可能大家就有疑问，为什么hashcode不直接写物理地址呢，还要另外用一张hash表来代表对象的地址？接下来就告诉你hashcode的作用，

1、HashCode的存在主要是为了查找的快捷性，HashCode是用来在散列存储结构中确定对象的存储地址的(后半句说的用hashcode来代表对象就是在hash表中的位置)

为什么hashcode就查找的更快，比如：我们有一个能存放1000个数这样大的内存中，在其中要存放1000个不一样的数字，用最笨的方法，就是存一个数字，就遍历一遍，看有没有相同得数，当存了900个数字，开始存901个数字的时候，就需要跟900个数字进行对比，这样就很麻烦，很是消耗时间，用hashcode来记录对象的位置，来看一下。hash表中有1、2、3、4、5、6、7、8个位置，存第一个数，hashcode为1，该数就放在hash表中1的位置，存到100个数字，hash表中8个位置会有很多数字了，1中可能有20个数字，存101个数字时，他先查hashcode值对应的位置，假设为1，那么就有20个数字和他的hashcode相同，他只需要跟这20个数字相比较(equals)，如果每一个相同，那么就放在1这个位置，这样比较的次数就少了很多，实际上hash表中有很多位置，这里只是举例只有8个，所以比较的次数会让你觉得也挺多的，实际上，如果hash表很大，那么比较的次数就很少很少了。  通过对原始方法和使用hashcode方法进行对比，我们就知道了hashcode的作用，并且为什么要使用hashcode了

## 三、equals方法和hashcode的关系？ ##

通过前面这个例子，大概可以知道，先通过hashcode来比较，如果hashcode相等，那么就用equals方法来比较两个对象是否相等，用个例子说明：上面说的hash表中的8个位置，就好比8个桶，每个桶里能装很多的对象，对象A通过hash函数算法得到将它放到1号桶中，当然肯定有别的对象也会放到1号桶中，如果对象B也通过算法分到了1号桶，那么它如何识别桶中其他对象是否和它一样呢，这时候就需要equals方法来进行筛选了。

1、如果两个对象equals相等，那么这两个对象的HashCode一定也相同

2、如果两个对象的HashCode相同，不代表两个对象就相同，只能说明这两个对象在散列存储结构中，存放于同一个位置

这两条你们就能够理解了。

## 四、为什么equals方法重写的话，建议也一起重写hashcode方法？ ##

（如果对象的equals方法被重写，那么对象的HashCode方法也尽量重写）

举个例子，其实就明白了这个道理，

比如：有个A类重写了equals方法，但是没有重写hashCode方法，看输出结果，对象a1和对象a2使用equals方法相等，按照上面的hashcode的用法，那么他们两个的hashcode肯定相等，但是这里由于没重写hashcode方法，他们两个hashcode并不一样，所以，我们在重写了equals方法后，尽量也重写了hashcode方法，通过一定的算法，使他们在equals相等时，也会有相同的hashcode值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 2][]

实例：现在来看一下String的源码中的equals方法和hashcode方法。这个类就重写了这两个方法，现在为什么需要重写这两个方法了吧？

equals方法：其实跟我上面写的那个例子是一样的原理，所以通过源码又知道了String的equals方法验证的是两个字符串的值是否一样。还有Double类也重写了这些方法。很多类有比较这类的，都重写了这两个方法，因为在所有类的父类Object中。equals的功能就是 “==”号的功能。你们还可以比较String对象的equals和==的区别啦。这里不再说明。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 3][]

hashcode方法

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 4][]

来源：[https://www.cnblogs.com/whgk/p/6071617.html][https_www.cnblogs.com_whgk_p_6071617.html]

# **三、HashMap源码剖析** #

HashMap的源码如下(加入了比较详细的注释)：

package java.util;
    
    import java.io.*;
    
    public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>,
            Cloneable, Serializable {
    
        // 默认的初始容量（容量为HashMap中槽的数目）是16，且实际容量必须是2的整数次幂。
        static final int DEFAULT_INITIAL_CAPACITY = 16;
    
        // 最大容量（必须是2的幂且小于2的30次方，传入容量过大将被这个值替换）
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        // 默认加载因子为0.75
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        // 存储数据的Entry数组，长度是2的幂。
        // HashMap采用链表法解决冲突，每一个Entry本质上是一个单向链表
        transient Entry[] table;
    
        // HashMap的底层数组中已用槽的数量
        transient int size;
    
        // HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
        int threshold;
    
        // 加载因子实际大小
        final float loadFactor;
    
        // HashMap被改变的次数
        transient volatile int modCount;
    
        // 指定“容量大小”和“加载因子”的构造函数
        public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: "
                        + initialCapacity);
            // HashMap的最大容量只能是MAXIMUM_CAPACITY
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            // 加载因此不能小于0
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: "
                        + loadFactor);
    
            // 找出“大于initialCapacity”的最小的2的幂
            int capacity = 1;
            while (capacity < initialCapacity)
                capacity <<= 1;
    
            // 设置“加载因子”
            this.loadFactor = loadFactor;
            // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
            threshold = (int) (capacity * loadFactor);
            // 创建Entry数组，用来保存数据
            table = new Entry[capacity];
            init();
        }
    
        // 指定“容量大小”的构造函数
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        // 默认构造函数。
        public HashMap() {
            // 设置“加载因子”为默认加载因子0.75
            this.loadFactor = DEFAULT_LOAD_FACTOR;
            // 设置“HashMap阈值”，当HashMap中存储数据的数量达到threshold时，就需要将HashMap的容量加倍。
            threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
            // 创建Entry数组，用来保存数据
            table = new Entry[DEFAULT_INITIAL_CAPACITY];
            init();
        }
    
        // 包含“子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);
            // 将m中的全部元素逐个添加到HashMap中
            putAllForCreate(m);
        }
    
        // 求hash值的方法，重新计算hash值
        static int hash(int h) {
            h ^= (h >>> 20) ^ (h >>> 12);
            return h ^ (h >>> 7) ^ (h >>> 4);
        }
    
        // 返回h在数组中的索引值，这里用&代替取模，旨在提升效率
        // h & (length-1)保证返回值的小于length
        static int indexFor(int h, int length) {
            return h & (length - 1);
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        // 获取key对应的value
        public V get(Object key) {
            if (key == null)
                return getForNullKey();
            // 获取key的hash值
            int hash = hash(key.hashCode());
            // 在“该hash值对应的链表”上查找“键值等于key”的元素
            for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
                Object k;
                // 判断key是否相同
                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                    return e.value;
            }
            // 没找到则返回null
            return null;
        }
    
        // 获取“key为null”的元素的值
        // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！
        private V getForNullKey() {
            for (Entry<K, V> e = table[0]; e != null; e = e.next) {
                if (e.key == null)
                    return e.value;
            }
            return null;
        }
    
        // HashMap是否包含key
        public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        // 返回“键为key”的键值对
        final Entry<K, V> getEntry(Object key) {
            // 获取哈希值
            // HashMap将“key为null”的元素存储在table[0]位置，“key不为null”的则调用hash()计算哈希值
            int hash = (key == null) ? 0 : hash(key.hashCode());
            // 在“该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;
        }
    
        // 将“key-value”添加到HashMap中
        public V put(K key, V value) {
            // 若“key为null”，则将该键值对添加到table[0]中。
            if (key == null)
                return putForNullKey(value);
            // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
            int hash = hash(key.hashCode());
            int i = indexFor(hash, table.length);
            for (Entry<K, V> e = table[i]; e != null; e = e.next) {
                Object k;
                // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
            modCount++;
            // 将key-value添加到table[i]处
            addEntry(hash, key, value, i);
            return null;
        }
    
        // putForNullKey()的作用是将“key为null”键值对添加到table[0]位置
        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;
                }
            }
            // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!
            modCount++;
            addEntry(0, null, value, 0);
            return null;
        }
    
        // 创建HashMap对应的“添加方法”，
        // 它和put()不同。putForCreate()是内部方法，它被构造函数等调用，用来创建HashMap
        // 而put()是对外提供的往HashMap中添加元素的方法。
        private void putForCreate(K key, V value) {
            int hash = (key == null) ? 0 : hash(key.hashCode());
            int i = indexFor(hash, table.length);
    
            // 若该HashMap表中存在“键值等于key”的元素，则替换该元素的value值
            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;
                }
            }
    
            // 若该HashMap表中不存在“键值等于key”的元素，则将该key-value添加到HashMap中
            createEntry(hash, key, value, i);
        }
    
        // 将“m”中的全部元素都添加到HashMap中。
        // 该方法被内部的构造HashMap的方法所调用。
        private void putAllForCreate(Map<? extends K, ? extends V> m) {
            // 利用迭代器将元素逐个添加到HashMap中
            for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
                    .entrySet().iterator(); i.hasNext();) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                putForCreate(e.getKey(), e.getValue());
            }
        }
    
        // 重新调整HashMap的大小，newCapacity是调整后的容量
        void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            // 如果就容量已经达到了最大值，则不能再扩容，直接返回
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，
            // 然后，将“新HashMap”赋值给“旧HashMap”。
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable);
            table = newTable;
            threshold = (int) (newCapacity * loadFactor);
        }
    
        // 将HashMap中的全部元素都添加到newTable中
        void transfer(Entry[] newTable) {
            Entry[] src = table;
            int newCapacity = newTable.length;
            for (int j = 0; j < src.length; j++) {
                Entry<K, V> e = src[j];
                if (e != null) {
                    src[j] = null;
                    do {
                        Entry<K, V> next = e.next;
                        int i = indexFor(e.hash, newCapacity);
                        e.next = newTable[i];
                        newTable[i] = e;
                        e = next;
                    } while (e != null);
                }
            }
        }
    
        // 将"m"的全部元素都添加到HashMap中
        public void putAll(Map<? extends K, ? extends V> m) {
            // 有效性判断
            int numKeysToBeAdded = m.size();
            if (numKeysToBeAdded == 0)
                return;
    
            // 计算容量是否足够，
            // 若“当前阀值容量 < 需要的容量”，则将容量x2。
            if (numKeysToBeAdded > threshold) {
                int targetCapacity = (int) (numKeysToBeAdded / loadFactor + 1);
                if (targetCapacity > MAXIMUM_CAPACITY)
                    targetCapacity = MAXIMUM_CAPACITY;
                int newCapacity = table.length;
                while (newCapacity < targetCapacity)
                    newCapacity <<= 1;
                if (newCapacity > table.length)
                    resize(newCapacity);
            }
    
            // 通过迭代器，将“m”中的元素逐个添加到HashMap中。
            for (Iterator<? extends Map.Entry<? extends K, ? extends V>> i = m
                    .entrySet().iterator(); i.hasNext();) {
                Map.Entry<? extends K, ? extends V> e = i.next();
                put(e.getKey(), e.getValue());
            }
        }
    
        // 删除“键为key”元素
        public V remove(Object key) {
            Entry<K, V> e = removeEntryForKey(key);
            return (e == null ? null : e.value);
        }
    
        // 删除“键为key”的元素
        final Entry<K, V> removeEntryForKey(Object key) {
            // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
            int hash = (key == null) ? 0 : hash(key.hashCode());
            int i = indexFor(hash, table.length);
            Entry<K, V> prev = table[i];
            Entry<K, V> e = prev;
    
            // 删除链表中“键为key”的元素
            // 本质是“删除单向链表中的节点”
            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;
        }
    
        // 删除“键值对”
        final Entry<K, V> removeMapping(Object o) {
            if (!(o instanceof Map.Entry))
                return null;
    
            Map.Entry<K, V> entry = (Map.Entry<K, V>) o;
            Object key = entry.getKey();
            int hash = (key == null) ? 0 : hash(key.hashCode());
            int i = indexFor(hash, table.length);
            Entry<K, V> prev = table[i];
            Entry<K, V> e = prev;
    
            // 删除链表中的“键值对e”
            // 本质是“删除单向链表中的节点”
            while (e != null) {
                Entry<K, V> next = e.next;
                if (e.hash == hash && e.equals(entry)) {
                    modCount++;
                    size--;
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    e.recordRemoval(this);
                    return e;
                }
                prev = e;
                e = next;
            }
    
            return e;
        }
    
        // 清空HashMap，将所有的元素设为null
        public void clear() {
            modCount++;
            Entry[] tab = table;
            for (int i = 0; i < tab.length; i++)
                tab[i] = null;
            size = 0;
        }
    
        // 是否包含“值为value”的元素
        public boolean containsValue(Object value) {
            // 若“value为null”，则调用containsNullValue()查找
            if (value == null)
                return containsNullValue();
    
            // 若“value不为null”，则查找HashMap中是否有值为value的节点。
            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;
        }
    
        // 是否包含null值
        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;
        }
    
        // 克隆一个HashMap，并返回Object对象
        public Object clone() {
            HashMap<K, V> result = null;
            try {
                result = (HashMap<K, V>) super.clone();
            } catch (CloneNotSupportedException e) {
                // assert false;
            }
            result.table = new Entry[table.length];
            result.entrySet = null;
            result.modCount = 0;
            result.size = 0;
            result.init();
            // 调用putAllForCreate()将全部元素添加到HashMap中
            result.putAllForCreate(this);
    
            return result;
        }
    
        // Entry是单向链表。
        // 它是 “HashMap链式存储法”对应的链表。
        // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value),
        // equals(Object o), hashCode()这些函数
        static class Entry<K, V> implements Map.Entry<K, V> {
            final K key;
            V value;
            // 指向下一个节点
            Entry<K, V> next;
            final int hash;
    
            // 构造函数。
            // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"
            Entry(int h, K k, V v, Entry<K, V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    
            public final K getKey() {
                return key;
            }
    
            public final V getValue() {
                return value;
            }
    
            public final V setValue(V newValue) {
                V oldValue = value;
                value = newValue;
                return oldValue;
            }
    
            // 判断两个Entry是否相等
            // 若两个Entry的“key”和“value”都相等，则返回true。
            // 否则，返回false
            public final boolean equals(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry e = (Map.Entry) o;
                Object k1 = getKey();
                Object k2 = e.getKey();
                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
                    Object v1 = getValue();
                    Object v2 = e.getValue();
                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
                        return true;
                }
                return false;
            }
    
            // 实现hashCode()
            public final int hashCode() {
                return (key == null ? 0 : key.hashCode())
                        ^ (value == null ? 0 : value.hashCode());
            }
    
            public final String toString() {
                return getKey() + "=" + getValue();
            }
    
            // 当向HashMap中添加元素时，绘调用recordAccess()。
            // 这里不做任何处理
            void recordAccess(HashMap<K, V> m) {
            }
    
            // 当从HashMap中删除元素时，绘调用recordRemoval()。
            // 这里不做任何处理
            void recordRemoval(HashMap<K, V> m) {
            }
        }
    
        // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
        void addEntry(int hash, K key, V value, int bucketIndex) {
            // 保存“bucketIndex”位置的值到“e”中
            Entry<K, V> e = table[bucketIndex];
            // 设置“bucketIndex”位置的元素为“新Entry”，
            // 设置“e”为“新Entry的下一个节点”
            table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
            // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小
            if (size++ >= threshold)
                resize(2 * table.length);
        }
    
        // 创建Entry。将“key-value”插入指定位置。
        void createEntry(int hash, K key, V value, int bucketIndex) {
            // 保存“bucketIndex”位置的值到“e”中
            Entry<K, V> e = table[bucketIndex];
            // 设置“bucketIndex”位置的元素为“新Entry”，
            // 设置“e”为“新Entry的下一个节点”
            table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
            size++;
        }
    
        // HashIterator是HashMap迭代器的抽象出来的父类，实现了公共了函数。
        // 它包含“key迭代器(KeyIterator)”、“Value迭代器(ValueIterator)”和“Entry迭代器(EntryIterator)”3个子类。
        private abstract class HashIterator<E> implements Iterator<E> {
            // 下一个元素
            Entry<K, V> next;
            // expectedModCount用于实现fast-fail机制。
            int expectedModCount;
            // 当前索引
            int index;
            // 当前元素
            Entry<K, V> current;
    
            HashIterator() {
                expectedModCount = modCount;
                if (size > 0) { // advance to first entry
                    Entry[] t = table;
                    // 将next指向table中第一个不为null的元素。
                    // 这里利用了index的初始值为0，从0开始依次向后遍历，直到找到不为null的元素就退出循环。
                    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();
    
                // 注意！！！
                // 一个Entry就是一个单向链表
                // 若该Entry的下一个节点不为空，就将next指向下一个节点;
                // 否则，将next指向下一个链表(也是下一个Entry)的不为null的节点。
                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;
            }
    
        }
    
        // value的迭代器
        private final class ValueIterator extends HashIterator<V> {
            public V next() {
                return nextEntry().value;
            }
        }
    
        // key的迭代器
        private final class KeyIterator extends HashIterator<K> {
            public K next() {
                return nextEntry().getKey();
            }
        }
    
        // Entry的迭代器
        private final class EntryIterator extends HashIterator<Map.Entry<K, V>> {
            public Map.Entry<K, V> next() {
                return nextEntry();
            }
        }
    
        // 返回一个“key迭代器”
        Iterator<K> newKeyIterator() {
            return new KeyIterator();
        }
    
        // 返回一个“value迭代器”
        Iterator<V> newValueIterator() {
            return new ValueIterator();
        }
    
        // 返回一个“entry迭代器”
        Iterator<Map.Entry<K, V>> newEntryIterator() {
            return new EntryIterator();
        }
    
        // HashMap的Entry对应的集合
        private transient Set<Map.Entry<K, V>> entrySet = null;
    
        // 返回“key的集合”，实际上返回一个“KeySet对象”
        public Set<K> keySet() {
            Set<K> ks = keySet;
            return (ks != null ? ks : (keySet = new KeySet()));
        }
    
        // Key对应的集合
        // KeySet继承于AbstractSet，说明该集合中没有重复的Key。
        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();
            }
        }
    
        // 返回“value集合”，实际上返回的是一个Values对象
        public Collection<V> values() {
            Collection<V> vs = values;
            return (vs != null ? vs : (values = new Values()));
        }
    
        // “value集合”
        // Values继承于AbstractCollection，不同于“KeySet继承于AbstractSet”，
        // Values中的元素能够重复。因为不同的key可以指向相同的value。
        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();
            }
        }
    
        // 返回“HashMap的Entry集合”
        public Set<Map.Entry<K, V>> entrySet() {
            return entrySet0();
        }
    
        // 返回“HashMap的Entry集合”，它实际是返回一个EntrySet对象
        private Set<Map.Entry<K, V>> entrySet0() {
            Set<Map.Entry<K, V>> es = entrySet;
            return es != null ? es : (entrySet = new EntrySet());
        }
    
        // EntrySet对应的集合
        // EntrySet继承于AbstractSet，说明该集合中没有重复的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();
            }
        }
    
        // java.io.Serializable的写入函数
        // 将HashMap的“总的容量，实际容量，所有的Entry”都写入到输出流中
        private void writeObject(java.io.ObjectOutputStream s) throws IOException {
            Iterator<Map.Entry<K, V>> i = (size > 0) ? entrySet0().iterator()
                    : null;
    
            // Write out the threshold, loadfactor, and any hidden stuff
            s.defaultWriteObject();
    
            // Write out number of buckets
            s.writeInt(table.length);
    
            // Write out size (number of Mappings)
            s.writeInt(size);
    
            // Write out keys and values (alternating)
            if (i != null) {
                while (i.hasNext()) {
                    Map.Entry<K, V> e = i.next();
                    s.writeObject(e.getKey());
                    s.writeObject(e.getValue());
                }
            }
        }
    
        private static final long serialVersionUID = 362498820763181265L;
    
        // java.io.Serializable的读取函数：根据写入方式读出
        // 将HashMap的“总的容量，实际容量，所有的Entry”依次读出
        private void readObject(java.io.ObjectInputStream s) throws IOException,
                ClassNotFoundException {
            // Read in the threshold, loadfactor, and any hidden stuff
            s.defaultReadObject();
    
            // Read in number of buckets and allocate the bucket array;
            int numBuckets = s.readInt();
            table = new Entry[numBuckets];
    
            init(); // Give subclass a chance to do its thing.
    
            // Read in size (number of Mappings)
            int size = s.readInt();
    
            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < size; i++) {
                K key = (K) s.readObject();
                V value = (V) s.readObject();
                putForCreate(key, value);
            }
        }
    
        // 返回“HashMap总的容量”
        int capacity() {
            return table.length;
        }
    
        // 返回“HashMap的加载因子”
        float loadFactor() {
            return loadFactor;
        }
    }

# **四、总结与详解** #

## **1、**首先要清楚HashMap的存储结构 ##

如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 5][]

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 6][]

Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），请看下图（横排表示数组，纵排表示数组元素【实际上是一个链表】）。

## 2、首先看链表中节点的数据结构： ##

// Entry是单向链表。    
    // 它是 “HashMap链式存储法”对应的链表。    
    // 它实现了Map.Entry 接口，即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数    
    static class Entry<K,V> implements Map.Entry<K,V> {    
        final K key;    
        V value;    
        // 指向下一个节点    
        Entry<K,V> next;    
        final int hash;    
    
        // 构造函数。    
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    
        Entry(int h, K k, V v, Entry<K,V> n) {    
            value = v;    
            next = n;    
            key = k;    
            hash = h;    
        }    
    
        public final K getKey() {    
            return key;    
        }    
    
        public final V getValue() {    
            return value;    
        }    
    
        public final V setValue(V newValue) {    
            V oldValue = value;    
            value = newValue;    
            return oldValue;    
        }    
    
        // 判断两个Entry是否相等    
        // 若两个Entry的“key”和“value”都相等，则返回true。    
        // 否则，返回false    
        public final boolean equals(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry e = (Map.Entry)o;    
            Object k1 = getKey();    
            Object k2 = e.getKey();    
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
                Object v1 = getValue();    
                Object v2 = e.getValue();    
                if (v1 == v2 || (v1 != null && v1.equals(v2)))    
                    return true;    
            }    
            return false;    
        }    
    
        // 实现hashCode()    
        public final int hashCode() {    
            return (key==null   ? 0 : key.hashCode()) ^    
                   (value==null ? 0 : value.hashCode());    
        }    
    
        public final String toString() {    
            return getKey() + "=" + getValue();    
        }    
    
        // 当向HashMap中添加元素时，绘调用recordAccess()。    
        // 这里不做任何处理    
        void recordAccess(HashMap<K,V> m) {    
        }    
    
        // 当从HashMap中删除元素时，绘调用recordRemoval()。    
        // 这里不做任何处理    
        void recordRemoval(HashMap<K,V> m) {    
        }    
    }

它的结构元素除了key、value、hash外，还有next，next指向下一个节点。另外，这里覆写了equals和hashCode方法来保证键值对的独一无二。

## 3、初始容量和加载因子 ##

HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数

*  其中容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16），加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。
 *  加载因子 如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认
    
    加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。
 *  另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方

当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小\*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16\*0.75=12的时候，就把数组的大小扩展为2\*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75\*1000 < 1000, 也就是说为了让0.75 \* size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。

### **详细理解加载因子** ###

**可追溯hashmap整个过程：**

hashmap 是这样存的；先利用hashcode  找到需要存的地方；但是 存的地方肯定是有限的 就是hashMap分配到的空间  比如是  10现在你 第一个元素来了 那么他会根据 你 hashcode%10 得到你 在 10个位置中该存到哪里？

这个时候就有一个问题，就是，如果hashcode%10 找到存的地方   当你要存进去时候 你发现里面已经有另外一个对象了，

那么这时候就要调用 equals方法 进行比较，如果相同，就说明是一个相同的对象。就替换掉。

如果不同，那么就 形成散列桶，  就是2个对象一起， 不过有先后， 后进来的 在后面。

hashmap 查询对象，要的是效率，直接通过hashcode找到存放的地址，直接取出，只需一次。

但是像我们前面说的这种情况，是会让操作数增加的，

你找到了 hashcode 所对应的物理地址，发现里面有2个对象， 这时就不能确定那个是你要找的，那么就要通过equals和你传入的key进行比对，相同 则返回。

前面的讲述已经发现  当你空间只有仅仅为10的时候 是很容易造成，2个对象的hashcode 所对应的地址是一个位置的情况

这样就造成 2个 对象 会形成散列桶，使查询和插入的时间增加。

这时就有一个加载因子的参数，如果加载因子为0.75 ，如果你hashmap的 空间有 100  那么  当你插入了75个元素的时候 hashmap就需要扩容了，不然的话 会形成很长散列桶 ， 对于查询和插入都会增加时间，因为 他要一个一个的equals。

但是你又不能让加载因子很小，0.01 这样是不合适的，因为 他会大大消耗你的 内存， 你一加入一个对象hashmap就扩容。

这时就存在着一个平衡，，jdk中默认是0.75   可以根据自己的实际情况进行调整

详细案例可参考：[http://www.cnblogs.com/huangfox/archive/2012/07/06/2579614.html][http_www.cnblogs.com_huangfox_archive_2012_07_06_2579614.html]

## 4、HashMap中key和value都允许为null ##

## 5、重点分析下HashMap中用的最多两个的方法put和get ##

先从比较简单的get方法着手，源码如下：

// 获取key对应的value    
    public V get(Object key) {    
        if (key == null)    
            return getForNullKey();    
        // 获取key的hash值    
        int hash = hash(key.hashCode());    
        // 在“该hash值对应的链表”上查找“键值等于key”的元素    
        for (Entry<K,V> e = table[indexFor(hash, table.length)];    
             e != null;    
             e = e.next) {    
            Object k;    
    /判断key是否相同  
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))    
                return e.value;    
        }  
    没找到则返回null  
        return null;    
    }    
    
    // 获取“key为null”的元素的值    
    // HashMap将“key为null”的元素存储在table[0]位置，但不一定是该链表的第一个位置！    
    private V getForNullKey() {    
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {    
            if (e.key == null)    
                return e.value;    
        }    
        return null;    
    }

首先，如果key为null，则直接从哈希表的第一个位置table\[0\]对应的链表上查找。记住，key为null的键值对永远都放在以table\[0\]为头结点的链表中，当然不一定是存放在头结点table\[0\]中。  
如果key不为null，则先求的key的hash值，根据hash值找到在table中的索引，在该索引对应的单链表中查找是否有键值对的key与目标key相等，有就返回对应的value，没有则返回null。

put方法稍微复杂些，代码如下：

public V put(K key, V value) {
      // 若“key为null”，则将该键值对添加到table[0]中。
      if (key == null)
        return putForNullKey(value);
      // 若“key不为null”，则计算该key的哈希值，然后将其添加到该哈希值对应的链表中。
      int hash = hash(key.hashCode());
      int i = indexFor(hash, table.length);
      for (Entry<K, V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 若“该key”对应的键值对已经存在，则用新的value取代旧的value。然后退出！
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
          V oldValue = e.value;
          e.value = value;
          e.recordAccess(this);
          return oldValue;
        }
      }
    
      // 若“该key”对应的键值对不存在，则将“key-value”添加到table中
      modCount++;
      // 将key-value添加到table[i]处
      addEntry(hash, key, value, i);
      return null;
    }

如果key为null，则将其添加到table\[0\]对应的链表中，putForNullKey的源码如下：

// putForNullKey()的作用是将“key为null”键值对添加到table[0]位置    
        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;    
                }    
            }    
            // 如果没有存在key为null的键值对，则直接题阿见到table[0]处!    
            modCount++;    
            addEntry(0, null, value, 0);    
            return null;    
        }

如果key不为null，则同样先求出key的hash值，根据hash值得出在table中的索引，而后遍历对应的单链表，如果单链表中存在与目标key相等的键值对，则将新的value覆盖旧的value，比将旧的value返回，如果找不到与目标key相等的键值对，或者该单链表为空，则将该键值对插入到改单链表的头结点位置（每次新插入的节点都是放在头结点的位置），该操作是有addEntry方法实现的，它的源码如下：

// 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。    
        void addEntry(int hash, K key, V value, int bucketIndex) {    
            // 保存“bucketIndex”位置的值到“e”中    
            Entry<K,V> e = table[bucketIndex];    
            // 设置“bucketIndex”位置的元素为“新Entry”，    
            // 设置“e”为“新Entry的下一个节点”    
            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);    
            // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小    
            if (size++ >= threshold)    
                resize(2 * table.length);    
        }

> 注意这里倒数第三行的构造方法，将key-value键值对赋给table\[bucketIndex\]，并将其next指向元素e，这便将key-value放到了头结点中，并将之前的头结点接在了它的后面。该方法也说明，每次put键值对的时候，总是将新的该键值对放在table\[bucketIndex\]处（即头结点处）。  
>   
> 两外注意最后两行代码，每次加入键值对时，都要判断当前已用的槽的数目是否大于等于阀值（容量\*加载因子），如果大于等于，则进行扩容，将容量扩为原来容量的2倍。

## 6、关于扩容 ##

resize方法，它的源码如下：

// 重新调整HashMap的大小，newCapacity是调整后的单位    
        void resize(int newCapacity) {    
            Entry[] oldTable = table;    
            int oldCapacity = oldTable.length;    
            if (oldCapacity == MAXIMUM_CAPACITY) {    
                threshold = Integer.MAX_VALUE;    
                return;    
            }    
    
            // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，    
            // 然后，将“新HashMap”赋值给“旧HashMap”。    
            Entry[] newTable = new Entry[newCapacity];    
            transfer(newTable);    
            table = newTable;    
            threshold = (int)(newCapacity * loadFactor);    
        }

很明显，是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。

transfer方法的源码如下：

// 将HashMap中的全部元素都添加到newTable中    
    void transfer(Entry[] newTable) {    
        Entry[] src = table;    
        int newCapacity = newTable.length;    
        for (int j = 0; j < src.length; j++) {    
            Entry<K,V> e = src[j];    
            if (e != null) {    
                src[j] = null;    
                do {    
                    Entry<K,V> next = e.next;    
                    int i = indexFor(e.hash, newCapacity);    
                    e.next = newTable[i];    
                    newTable[i] = e;    
                    e = next;    
                } while (e != null);    
            }    
        }    
    }

很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

## 7、注意containsKey方法和containsValue方法 ##

前者直接可以通过key的哈希值将搜索范围定位到指定索引对应的链表，而后者要对哈希数组的每个链表进行搜索

## 8、重点来分析下求hash值和索引值的方法 ##

方法便是HashMap设计的最为核心的部分，二者结合能保证哈希表中的元素尽可能均匀地散列

*  计算哈希值的方法如下：
    
        static int hash(int h) {  
                h ^= (h >>> 20) ^ (h >>> 12);  
                return h ^ (h >>> 7) ^ (h >>> 4);  
            }
    
    > 它只是一个数学公式，IDK这样设计对hash值的计算，自然有它的好处，至于为什么这样设计，我们这里不去追究，只要明白一点，用的位的操作使hash值的计算效率很高。

*  由hash值找到对应索引的方法如下

static int indexFor(int h, int length) {  
            return h & (length-1);  
        }

这个我们要重点说下，我们一般对哈希表的散列很自然地会想到用hash值对length取模（即除法散列法），Hashtable中也是这样实现的，这种方法基本能保证元素在哈希表中散列的比较均匀，但取模会用到除法运算，效率很低，HashMap中则通过h&(length-1)的方法来代替取模，同样实现了均匀的散列，但效率要高很多，这也是HashMap对Hashtable的一个改进。

接下来，我们分析下为什么哈希表的容量一定要是2的整数次幂。

*  首先，length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；
 *  其次，length为2的整数次幂的话，为偶数，这样length-1为奇数，奇数的最后一位是1，这样便保证了h&(length-1)的最后一位可能为0，也可能为1（这取决于h的值），即与后的结果可能为偶数，也可能为奇数，这样便可以保证散列的均匀性，而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间，因此，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列

## 9、为什么初始化容量为2的次幂 ##

请看几个不错的详细解释：[为什么hashMap的容量扩容时一定是2的幂次][hashMap_2]

## 10、为什么最大容量是2的30次方 ##

hashMap最大容量必须是2的幂且小于2的30次方，传入容量过大将被这个值替换;

static final int MAXIMUM\_CAPACITY = 1 << 30;

当看到 1<<30 时，对“<<” 有点模糊，当了解“<<”的用法之后，又有一个问题；

int类型不是4个字节共32位吗，为什么不是 1<<31呢？

首先介绍下等号右边数字及字符的含义:

1、"<<"为左移运算符，1表示十进制中的“1”，30表示十进制数字1转化为二进制后向左移动30位。在数值上等同于2的30次幂。

2、为什么是2的30次幂?

以一个字节为例：1<<2 = 4

0000 0001(十进制1)

向左移动两位之后变成

0000 0100（十进制4）

可见 1<<30 等同于十进制中2的30次幂。

回到题目，为什么会是2的30次幂，而不是2的31次幂呢？

首先：JAVA规定了该static final 类型的静态变量为int类型，至于为什么不是byte、long等类型，原因是由于考虑到HashMap的性能问题而作的折中处理！

由于int类型限制了该变量的长度为4个字节共32个二进制位，按理说可以向左移动31位即2的31次幂。但是事实上由于二进制数字中最高的一位也就是最左边的一位是符号位，用来表示正负之分（0为正，1为负），所以只能向左移动30位，而不能移动到处在最高位的符号位！

# 五、java1.8改进 #

参考：[https://blog.csdn.net/USTC\_Zn/article/details/78173217][https_blog.csdn.net_USTC_Zn_article_details_78173217]

[https://www.cnblogs.com/akaneblog/p/7139935.html][https_www.cnblogs.com_akaneblog_p_7139935.html]

[https://blog.csdn.net/weixin\_37356262/article/details/80543218][https_blog.csdn.net_weixin_37356262_article_details_80543218]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 7][]

在java jdk8中对HashMap的源码进行了优化，在jdk7中，HashMap处理“碰撞”的时候，都是采用链表来存储，当碰撞的结点很多时，查询时间是O（n）。

在jdk8中，HashMap处理“碰撞”增加了红黑树这种数据结构，当碰撞结点较少时，采用链表存储，当较大时（>8个），采用红黑树（特点是查询时间是O（logn））存储（有一个阀值控制，大于阀值(8个)，将链表存储转换成红黑树存储）

![20160605110353076][]

问题分析：

你可能还知道哈希碰撞会对hashMap的性能带来灾难性的影响。如果多个hashCode()的值落到同一个桶内的时候，这些值是存储到一个链表中的。最坏的情况下，所有的key都映射到同一个桶中，这样hashmap就退化成了一个链表——查找时间从O(1)到O(n)。

随着HashMap的大小的增长，get()方法的开销也越来越大。由于所有的记录都在同一个桶里的超长链表内，平均查询一条记录就需要遍历一半的列表。

JDK1.8HashMap的红黑树是这样解决的：

如果某个桶中的记录过大的话（当前是TREEIFY\_THRESHOLD = 8），HashMap会动态的使用一个专门的treemap实现来替换掉它。这样做的结果会更好，是O(logn)，而不是糟糕的O(n)。

它是如何工作的？前面产生冲突的那些KEY对应的记录只是简单的追加到一个链表后面，这些记录只能通过遍历来进行查找。但是超过这个阈值后HashMap开始将列表升级成一个二叉树，使用哈希值作为树的分支变量，如果两个哈希值不等，但指向同一个桶的话，较大的那个会插入到右子树里。如果哈希值相等，HashMap希望key值最好是实现了Comparable接口的，这样它可以按照顺序来进行插入。这对HashMap的key来说并不是必须的，不过如果实现了当然最好。如果没有实现这个接口，在出现严重的哈希碰撞的时候，你就并别指望能获得性能提升了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 8][]

![20190104170444931.png][]

①.判断键值对数组table\[i\]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引i，如果table\[i\]==null，直接新建节点添加，转向⑥，如果table\[i\]不为空，转向③；

③.判断table\[i\]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table\[i\] 是否为treeNode，即table\[i\] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table\[i\]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

对于高并发情况下的扩容，下面有篇文章讲解的很好

[https://mp.weixin.qq.com/s?\_\_biz=MzIxMjE5MTE1Nw==&mid=2653192000&idx=1&sn=118cee6d1c67e7b8e4f762af3e61643e&chksm=8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzIxMjE5MTE1Nw_mid_2653192000_idx_1_sn_118cee6d1c67e7b8e4f762af3e61643e_chksm_8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d_scene_21_wechat_redirect]

链接引用：

[https://mp.weixin.qq.com/s?\_\_biz=MzU5OTMyODAyNg==&mid=2247484165&idx=1&sn=86fd57261c492f9badf136d577bfa0d2&scene=21\#wechat\_redirect][https_mp.weixin.qq.com_s_biz_MzU5OTMyODAyNg_mid_2247484165_idx_1_sn_86fd57261c492f9badf136d577bfa0d2_scene_21_wechat_redirect]

[https://blog.csdn.net/mxw2552261/article/details/79545717][https_blog.csdn.net_mxw2552261_article_details_79545717]

[http://www.javacui.com/Theory/377.html][http_www.javacui.com_Theory_377.html]

[http://blog.csdn.net/zhangerqing/article/details/8193118][http_blog.csdn.net_zhangerqing_article_details_8193118]

[http://www.cnblogs.com/matrix-skygirl/archive/2013/01/17/2864919.html][http_www.cnblogs.com_matrix-skygirl_archive_2013_01_17_2864919.html]

[http://www.iteye.com/topic/539465][http_www.iteye.com_topic_539465]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70]: /images/20220331/0137eb25e64547b48b1a78826a0af4bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 1]: /images/20220331/b469e182ce2f4d09b5be0be0e7e1d72f.png
[20190102191019620.png]: /images/20220331/d37914db1f554232b799ad4c2f795794.png
[20190102191035853.png]: /images/20220331/829b71ae1a3d4fb3b41e44b3e9cf9e17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 2]: /images/20220331/33863277afed447a91adbacb88d4d8b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 3]: /images/20220331/f8ddc51a27d54e66b18f001e9d3d55f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 4]: /images/20220331/4eefb390a4874feebb43c42e5d01c328.png
[https_www.cnblogs.com_whgk_p_6071617.html]: https://www.cnblogs.com/whgk/p/6071617.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 5]: /images/20220331/af6457b2e11440fcbfc91214df7c4984.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 6]: /images/20220331/0c41536ccb544a90a186281b2460e067.png
[http_www.cnblogs.com_huangfox_archive_2012_07_06_2579614.html]: http://www.cnblogs.com/huangfox/archive/2012/07/06/2579614.html
[hashMap_2]: https://blog.csdn.net/gududedabai/article/details/85784161
[https_blog.csdn.net_USTC_Zn_article_details_78173217]: https://blog.csdn.net/USTC_Zn/article/details/78173217
[https_www.cnblogs.com_akaneblog_p_7139935.html]: https://www.cnblogs.com/akaneblog/p/7139935.html
[https_blog.csdn.net_weixin_37356262_article_details_80543218]: https://blog.csdn.net/weixin_37356262/article/details/80543218
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 7]: /images/20220331/675bfb1393fd4d7aa2541cf6c24d6bc1.png
[20160605110353076]: /images/20220331/72143c5bc3f24fa6828734d50992692f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2d1ZHVkZWRhYmFp_size_16_color_FFFFFF_t_70 8]: /images/20220331/ddb765ac790046d59ec0d68748a1887b.png
[20190104170444931.png]: /images/20220331/ed974ce37d2e4f96841d80cf8bdd23fd.png
[https_mp.weixin.qq.com_s_biz_MzIxMjE5MTE1Nw_mid_2653192000_idx_1_sn_118cee6d1c67e7b8e4f762af3e61643e_chksm_8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653192000&idx=1&sn=118cee6d1c67e7b8e4f762af3e61643e&chksm=8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d&scene=21#wechat_redirect
[https_mp.weixin.qq.com_s_biz_MzU5OTMyODAyNg_mid_2247484165_idx_1_sn_86fd57261c492f9badf136d577bfa0d2_scene_21_wechat_redirect]: https://mp.weixin.qq.com/s?__biz=MzU5OTMyODAyNg==&mid=2247484165&idx=1&sn=86fd57261c492f9badf136d577bfa0d2&scene=21#wechat_redirect
[https_blog.csdn.net_mxw2552261_article_details_79545717]: https://blog.csdn.net/mxw2552261/article/details/79545717
[http_www.javacui.com_Theory_377.html]: http://www.javacui.com/Theory/377.html
[http_blog.csdn.net_zhangerqing_article_details_8193118]: http://blog.csdn.net/zhangerqing/article/details/8193118
[http_www.cnblogs.com_matrix-skygirl_archive_2013_01_17_2864919.html]: http://www.cnblogs.com/matrix-skygirl/archive/2013/01/17/2864919.html
[http_www.iteye.com_topic_539465]: http://www.iteye.com/topic/539465