【JavaSE】Map集合，HashMap的常用方法put、get的源码解析

Map集合

Collection集合的特点是每次进行单个对象的保存，如果现在要进行一对对象(偶对象)的保存就只能使用Map集合来 完成，即Map集合中会一次性保存两个对象，且这两个对象的关系:key=value结构。这种结构最大的特点是可以通 过key找到对应的value内容。
首先来观察Map接口定义：

public interface Map<K,V>

在Map接口中有如下常用方法:

No	方法名称	类型	描述
1.	public V put(K key , V value);	普通	向Map中追加数据
2.	public V get(Object key);	普通	根据Key取得对应的Value，如果没有返回null
3.	public Set KeySet();	普通	取得所有key信息，key不能重复
4.	public Collection values();	普通	取得所有value信息，可以重复
5.	public Set<Map.Entry<K,V>> entrySet();	普通	将Map集合变为Set集合

Map本身是一个接口，要使用Map需要通过子类进行对象实例化。Map接口的常用子类有如下四个： HashMap、 Hashtable、TreeMap、ConcurrentHashMap。
这篇博客重点讲解一下HashMap。

HashMap子类

用法如下:

Map<K,V> map = new HashMap<>();

这样就创建了一个Map集合，可以向里面用put方法添加K,V键值对。
先了解一下HashMap是如何存储键值对的，如图：
它结合了数组查找元素快，链表修改结构快的特点。先用哈希表建立一个数组，然后将产生哈希冲突的元素按照链地址法的方式放在桶里面的链表中。如果链表中的元素太多，链表还会树化，下面再详细说。

HashMap的构造方法

无参构造：

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

static final float DEFAULT_LOAD_FACTOR = 0.75f;

无参构造只是设置了一个哈希表的负载因子，用的是默认值的0.75。
有参构造：

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

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);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

可以发现所有的构造方法都没有分配HashMap的容量，只是简单的进行了负载因子和桶容量的赋值。其中tableSizeFor(initialCapacity)方法是为了将输入的桶容量值，变为大于输入值并且离输入值最近的二次幂，原因下面解释。

常用的方法put()

put方法是将键值对添加到HashMap的数据结构中：

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

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

只是返回了putVal的方法，而hash函数是将key值通过Object的hashCode()计算出来的值再进行处理，因为利用Object的hashCode()返回的值达到2³¹次方的数量，几乎不会发生碰撞，需要的桶个数太多。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果初始的桶容量为空，或者桶个数为0，就调用resize()方法并将返回值赋给n。
        if ((tab = table) == null || (n = tab.length) == 0)
        	//resize()方法主要是进行桶的初始化
            n = (tab = resize()).length;
        //hash & n-1相当于hash%(n-1)这就是为什么保证2次幂，使用位用算比取模速度快，然后判断此下标的桶处是否为null
        if ((p = tab[i = (n - 1) & hash]) == null)
        	//如果为null就在这个桶的地方创建这个K,V节点作为头节点
            tab[i] = newNode(hash, key, value, null);
        //哈希表已经有初始化容量，并且此桶的头节点不为null。
        else {
            Node<K,V> e; K k;
            //从上面可知p是首节点，所以首节点和当前节点如果K,V值相等，则当前节点替换首节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //若此桶已经树化，按照树的方式来存储新节点。
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //此桶仍然是链表，按照链表形式存储新节点
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        	//当前链表个数已经达到树化阈值8-1
                        	//尝试调用树化方法将链表树化
                            treeifyBin(tab, hash);
                        break;
                    }
                    //判断是否有节点和此节点一样，如果一样就break
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;   //节点往后移动
                }
            }
            //替换节点值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //这个值和fail-fast有关
        ++modCount;
        // 添加节点后，整个HashMap的元素个数若要超过容量时，调用resize进行扩容操作
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

关于put方法的详细解释，在注释中已经出现。下面做一个总结：

1. put方法先判断此哈希表是否为null，如果为null就初始化哈希表。(HashMap采用lazy-load策略(当第一次使用put时，才会将哈希表初始化)）
2. 接下来通过HashMap自带的hash函数计算此key值的下标，判断此下标所在的桶是否为null，如果为null，就将此键值对作为头节点。
3. 如果上面两步都否定，那么判断此桶是否已经树化，如果树化就用树化的方式来添加新节点。
4. 否则用链表的方式添加，在遍历链表的过程中，如果发现和此节点一模一样的key节点，就将旧value值替换为新的value值，如果添加完元素之后，桶中的节点数大于等于树化的阈值8-1，就尝试对此链表进行树化（尝试的意思是，调用树化函数之后，还会判断此哈希表中的元素是否大于64，如果不大于64只是进行一次扩容，否则进行树化）
5. 最后一步就是判断添加完所有节点之后，判断是否需要扩容。

常用的方法get()

get方法主要是通过key值获取value值：

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //哈希表已经初始化，并且当前key值的桶的头节点不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //要查找的节点刚好等于头节点，直接返回头节点
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //进行桶的遍历
            if ((e = first.next) != null) {
            	//若树化，使用树的方式查找节点
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //还未树化，使用链表方式遍历查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }