HashMap

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;
}

//getKey
public final K getKey()  {return key;}
public final V getValue() {return value;}
public final String toString() {return key + "=" + value;}
//重点，面试常备问道,求hashCode的值是key和value的异或
public final int hashCode(){return Objects.hashCode(key)^Objects.hashCode(value);}

//需要暂存原始值，最后再返回
public final V setValue(V newValue){
    V oldValue = value;
    value = newValue;
    return oldValue;
}


//需要重写equals，当key，value同时相等时，才相等
public final boolean equals(Object o){
    if(o == this) return true;
    if(o instanceof Map.Entry){
        Map.Entry<?,?> e = (Map.Entry<?,?>) o;
        if(Objects.equals(key,e.getKey()) && Objects.equals(value,e.getValue()))
            return true;
    }
    return false;
}

//hash是key值的hashcode高低16位异或，从这里可以知道jdk1.8hashmap的key是可以为null
//若为null，取0，hashtable中的key是不能为null的
static final int hash(Object key){
    int h;
    return (key == null)?0:(h = key.hashCode()^(h>>>16));
}

//给出一个初始容量，会根据给定的初始容量，给出最近的2的多少平方
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 >= MAXIMU_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//同上，另一种实现方法，得到最近的2的多少的平方
static final int tableSizeFor(int cap){
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMU_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//其中numberOfLeadingZeros方法，采用了从大到小进行判断
public static int numberOfLeadingZeros(int i){
    if(i <= 0){
        return i == 0 ? 32 : 0;
    }
    int n = 31;
    if(i >= 1 << 16) {n -= 16; i >>>= 16;}
    if(i >= 1 << 8) {n -= 8; i >>>= 8;}
    if(i >= 1 << 4) {n -= 4; i >>>= 4;}
    if(i >= 1 << 2) {n -= 2; i>>>= 2;}
    return n - (i >>> 1);
}

//初始化HashMap
public HashMap(int initialCapacity, float loadFactor){
    if(initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
    if(initialCapacity > MAXIMUM_CAPACITY){
        initalCapacity = MAXIMUM_CAPACITY;
    }
    if(loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshlod = tableSizeFor(initialCapacity);
}
//获取特定key的value值
public V get(Object key){
    Node<K,V> e;
    return (e = getNode(hash(key),key)) == null ? null : e.value;
}
//通过hash、key获取Node
final Node<K,V> getNode(int hash, Object key){
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //先判断数组是否是非空
    if((tab = table) != null && (n = tab.length) > 0 &&
      (first = tab[(n-1) & hash]) != null){
        if(first.hash == hash && //总是先检查第一个结点
          ((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);//进行循环，一直比对hash、key是否相等
    }
    return null;
}
//利用getNode进行判断
public boolean containsKey(Object key){return getNode(hash(key),key) != null;}

//put--(key,value)
public V put(K key, V value){
    return putVal(hash(key),key,value,false,true);
}
//重点来看看putVal
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)//如果此时table数据为空，进行扩容
        n = (tab = resize()).length;
    if((p = tab[i = (n - 1)&hash]) == null)  //若找到下标，此时没有值，即为null，则创建结点
        tab[i] = newNode(hash,key,value,null);
    else{//否则将将进行遍历链表
        Node<K,V> e; K k;
        //先检查头结点，如果hash，key相等，则已经插入了该结点
        if(p.hash == hash &&
          ((k = e.key) == key) || (key != null && key.equals(k)))
            e = p;
        //判断插入的结点p是否是树结点
        else if(p isinstanceof 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);
                    //如果binCount>=7时，链表树化为红黑树
                    if(binCount >= TREEIFY_THRESHOLD - 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){//存在映射关系，但是value为空
            V oldValue = e.value;
            if(!onlyIfAbsent || oldValue == value)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if(++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

final Node<K,V>[] resize(){
    //定义oldTab，oldThr
    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;
        }//容量放大两倍，阈值也放大两倍
        else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
               oldCap >= DEFALUT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 阈值放大两倍
    }
    //此时，oldCap等于零，但是阈值oldThr大于零，直接用oldThr进行替换
    else if(oldThr > 0)
        newCap = oldThr;//用thre替换初始容量
    else {//此时，oldCap和oldThr都为零，进行初始值替换，表明第一次扩容
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACOR * DEFAULT_INITIAL)
    }
    //初始化阈值newThr，初始化threshold
    if(newThr == 0){
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY)?(int)ft : Integer.MAX_VALUE;
    }
    threshold = newThr;
    //建立Node型数组，对table进行赋值
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //将oldTab中元素赋值给newTab
    if(oldTab != null){
        for(int j = 0;j < oldCap; ++j){
            Node<K,V> e;
            if((e = oldTab[j]) != null){
                oldTab[j] = null;//释放旧的数组中的内存
                if(e.next == null) //判断原来数组位置是否只有一个节点，则进行赋值
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)//判断是树节点
                    ((TreeNode<K,V>)e).split(this,newTab, j,oldCap);
                else{ //rehash,高位等于索引+oldCap，即：j + oldCap;
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do{
                        next = e.next;
                        if((e.hash & oldCap) == 0){ //表明是原来的位置，看这个地方是否有头结点，若无直接赋值，否则从尾部插入
                            if(loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }//表明需要从新hash到新的位置，同理如上
                        else{
                            if(hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    }while((e = next) != null);
                    if(loTail != null){ //先建立一个链表，之后将这个链表接到j索引处
                        loTail.next = null;
                        newTab[j] = loHead;
                    } // 同理只是更改了索引位置：j + hiHead
                    if(hiTail != null){
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

public V remove(Object key){
    Node<K,V> e;
    return (e = removeNode(hash(key),key,null,false,true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key,Object value,
                          boolean matchValue,boolean movable){
    //定义临时变量
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if((tab = table) != null && (n = tab.length) > 0 &&
      (p = tab[index = (n - 1) & hash]) != null){
        Node<K,V> node = null, e; K k; V v;
        //若是头结点
        if(p.hash == hash && 
           ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //往下遍历
        else if((e = p.next) != null){
            if(p instanceof TreeNode)//是树形节点
                node = ((TreeNode<K,V>) p).getTreeNode(hash,key);
            else {
                do {//进行循环遍历，找到即跳出循环
                    if(e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
                        node = e;
                        break;
                    }
                    p = e;
                } while((e = e.next) != null);
            }
        }
        if(node != null && (!matchValue || (v = node.value) == value ||
                           (value != null && value.equals(v)))){
            if(node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this,tab,movale);
            //若判断是头结点，直接去掉头结点，接在后面
            else if(node == p)
                tab[index] = node.next;
            else
                p.next = node.next;//在链表中间，跳过该节点
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

}