HashMap源码个人理解

HashMap<Integer, String> map = new HashMap<>();
map.put(11,"张三");
map.put(12,"李四");
map.put(13,"王五");
map.put(12,"赵六");
map.put(14,"陈皮");
System.out.println(map.size()); //长度为4  说明相同key存在某种操作(是替换还是不替换(丢弃))？

System.out.println(map.toString());//{11=张三, 12=赵六, 13=王五, 14=陈皮}  这是key-value一起换了 还是只换了value

查看源码(JDK1.8) 只截取出相关代码

有个疑问　　HashMap继承了AbstractMap,而AbstractMap自己也实现了Map<K,V>接口，那为什么HashMap也要实现Map<K,V>接口呢？

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

　　static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //默认初始容量左移4位 也就是2^4=16

　　static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 2^30

　　static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子0.75(也就是当存放的数据达到容量的75%的时候会实现扩容)

　　//静态内部类
　　//HashMap底层其实是数据+链表的结构(1.7之前)　　1.8之后就是数据+链表+红黑树
　　//这个就是节点的类类型(需要掌握点数据结构相关知识)

　　static class Node<K,V> implements Map.Entry<K,V> {
    　　final int hash;
    　　final K key;
    　　V value;
    　　Node<K,V> next;

    　　Node(int hash, K key, V value, Node<K,V> next) {
        　　this.hash = hash;
        　　this.key = key;
        　　this.value = value;
        　　this.next = next;
    　　}

　　}

　　transient int size; //记录当前map中(也就是最上层数组中元素的个数)

　　int threshold; //扩容的临界值(达到这个值的时候数组就要扩容了)

　　final float loadFactor; //加载因子

　　transient Node<K,V>[] table; //hashMap的主数组

　　static final int hash(Object key) { //通过key计算hash值的方法

    　　int h;
    　　return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
　　}

　　//构造方法　　
　　//无参构造初始化加载因子

　　public HashMap() {
    　　this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
　　}
　　//自定义出事容量个加载因子

　　public HashMap(int initialCapacity, float loadFactor) {
　　　　//以下三个if不用看 是为了代码的健壮性考虑
    　　if (initialCapacity < 0) 
　　　　　　throw new IllegalArgumentException("Illegal initial capacity: " + nitialCapacity);
    　　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);
　　}

　　//自定义初始化容量

　　public HashMap(int initialCapacity) {
    　　this(initialCapacity, DEFAULT_LOAD_FACTOR);
　　}
　　
　　//右移对应的位之后进行或(位)运算(无符号右移)　　　　>>这是带符号的右移 注意

　　static final int tableSizeFor(int cap) {
    　　int n = cap - 1;
    　　n |= n >>> 1;
    　　n |= n >>> 2;
    　　n |= n >>> 4;
    　　n |= n >>> 8;
    　　n |= n >>> 16;
    　　return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
　　}
　　解释
　　

　　//这就是向put中添加

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

　　//onlyIfAbsent if true, don"t change existing value　　这是官方注释 如果这个参数为true 就不需要改变现有的把value
　　//evict if false, the table is in creation mode.　　　　如果为false　　就是建表模式

 　　//这是真正实现插入的方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
　　// 判断主数组是不是空
    if ((tab = table) == null || (n = tab.length) == 0)
　　　　　//这是数组的扩容和初始化　　跳到下面的方法
        n = (tab = resize()).length;
　　//这是计算该hash值的数据在数组中的位置　　注意 这是拿数组的最大长度和该key的hash做与运算 所以不可能大于最大长度 不会发生越界问题
    if ((p = tab[i = (n - 1) & hash]) == null)//如果该位置是空 就直接存进去
        tab[i] = newNode(hash, key, value, null);
    else {//该位置不为空判断该数据应该存放在哪里

        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//这里注意 如果hash值相同 key也相同 短路或 后面的value就不用比了
            e = p;//记录下 改原链表中相同的节点
        else if (p instanceof TreeNode)//这是红黑树 不看
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {//这是插入操作 也就是hash值不同或者hash值相同 key不同
            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 这是红黑树 不看
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//找到就break
                    break;
                p = e;//继续往后找
            }
        }
        if (e != null) { // existing mapping for key 
            V oldValue = e.value;//记录被取代的value
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;//返回被取代的value
        }
    }
    ++modCount;
    if (++size > threshold)//map长度+1
        resize();
    afterNodeInsertion(evict);
    return null;
}

//这是数组的扩容方法和初始化

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
　　//判断是初始化还是扩容　　
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
　　//扩容
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }//如果扩容前的数组长度小于最大容量 
　　　　　　//(旧数组的容量左移一位(也就是2倍)赋值给新数组的容量 ，且容量不能大于最大容量 )&& 旧数组的容量要大于等于出事容量 
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
　　　　　　　　//扩容的阈值也扩大两倍
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
　　//这里就是初始化数组
    else {               // zero initial threshold signifies using defaults
　　　　　//初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
　　　　 //初始化加载因子 也就是达到这个值就要扩容
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
　　//这里是数组扩容的时候修改加载因子
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
　　//修改阈值
    threshold = newThr;

    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//主数组
    table = newTab;
    if (oldTab != null) {//如果扩容前的数组不为空 就需要将原来的数据存进去
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;//创建新节点
            if ((e = oldTab[j]) != null) {//判断原来的节点是不是null 取出来存着
                oldTab[j] = null;//再将就数组中的节点清空(原来的数据已经用e存着了)等着gc回收
                if (e.next == null)//判断该数组中的元素 所在的链表是否有后续节点
                    newTab[e.hash & (newCap - 1)] = e;//将该节点重新计算hash值并存入新数组
                else if (e instanceof TreeNode)//这是jdk1.8之后引入的红黑树的概念 这里就不看了 这是因为当链表中的个数大于等于8的时候此时就不再采用链表存储了，而是采用红黑树存储，这是为提高查找效率(时间复杂度)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order(保持顺序)　　这是保持原来的链表顺序
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {//这里说明下 jdk1.7之前采用的是头插法　　1.8之后采用的尾插法
                        next = e.next;//记录后续的链表的头结点
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}