HashMap1.7底层

//1.HashMap的K，V的值，在创建对象的时候确定：K：Integer  V：String
//HashMap的父类AbstractMap已经实现类Map接口，但是源码中又单独实现了Map接口
//这个操作就是一个多余的操作----》集合的创作者承认了
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定义了一个16，就是数组的长度
    static final int MAXIMUM_CAPACITY = 1 << 30;//定义了一个很大很大的数
    static final float DEFAULT_LOAD_FACTOR = 0.75f;//定义了一个值取值0.75  负载因子，加载因子
    transient Entry<K,V>[] table;//底层数组
    transient int size;//添加的元素数量
    int threshold;//定义个变量，没赋值默认为0，---》这个变量用来表示数组扩容的边界值，门槛值
    final float loadFactor;//这个变量用来接收负载因子，加载因子  装填因子
    //一下三个属性为JDK1.8源码下面的
    static final int TREEIFY_THRESHOLD = 8;//红黑树阈值，当链表长度大于8专为红黑树
    static final int UNTREEIFY_THRESHOLD = 6;//红黑树还原链表的阈值
    static final int MIN_TREEIFY_CAPACITY = 64;//当Hash表中
    //空构造器
    public HashMap() {
        //         16                     0.75
        this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR)
    }
    //带参数构造器--》不建议使用者调用这个构造器
    public HashMap(int initialCapacity,float loadFactor){
        if(initialCapacity>MAXIMUM_CAPACITY)
            initialCapacity=MAXIMUM_CAPACITY;
        //capacity最后的结果一定是2的整数倍  （2^n）???
        int capacity=1;
        while(capacity<initialCapacity)
            capacity<<=1;
        //确定了装填因子，负载因子，加载因子：0.75
        this.loadFactor=loadFactor;
        //threshold=capacity*loadFactor=16*0.75=12
        //threshold=12--->数组扩容的边界值
        threshold=(int)Math.min(capacity*loadFactor,MAXIMUM_CAPACITY+1);
        //创建主数组，主数组的长度定义为16
        table=new Entity[capacity];
        
        useAltHashing=sun.misc.VM.isBooted()&&
                (capacity>=Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }
    //存储数据的方法
    public V put(K key, V value){//K :Integer  V:String
        //对空值进行判断---允许key的值为NULL
        if(key==null)
            return putForNullKey(value);
        //获取哈希码
        int hash=hash(key);
        //得到元素在数组中的位置
        int i=indexFor(hash,table.length);
        //如果放入的数组的位置上没有元素的话，那么直接添加就行了，不走这个for循环
        
        //e!=null 满足的话，就证明这个位置上已经有东西了
        for(Entry<K,V> e=table[i];e!=null;e=e.next){
            Object k;
            //发生哈希碰撞的时候，会先比较哈希值
            //比较key是否是一个对象，如果key是一个对象的话，equals就不比较了
            //如果不是同一个对象，会比较equals方法
            //如果hash值一样，equals方法比较的结果也一样，那么才会走这个if方法
            if(e.hash==hash&&((k=e.key)==key||key.equals(k))){
                //获取老的value
                V oldValue=e.value;
                e.value=value;//新value替换老value--》只替换value不替换Key
                e.recordAccess(this);
                return oldValue;//将老value返回
            }
        }
        modCount++;
        addEntry(hash,key,value,i);
        return null;
    }
    
    final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    //二次散列，没有直接用hash的值,解决哈希冲突
    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);
}
//indexFor 根据hash值以及数组长度，获取当前key在数组中下标
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);//结算位置对应的公式，等效于h%length取余数---》效率低用于运算符效率高
}
//添加元的方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果size >= threshold这个变量不满足，这个if不走
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    //走这里创建一个Entry对象
    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    //将下标位置上的元素给e
    Entry<K,V> e = table[bucketIndex];
    //封装对象，将这个对象给table[bucketIndex] --->链表的头插法
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    //元素数量加1操作
    size++;
}


/*经典面试题：
（1）装填因子，负载因子，加载因子为什么是0.75：
装填因子设置为1：空间利用率得到了很大的满足，很容易碰撞，产生链表--》查询效率低
装填因子设置为0.5：碰撞的概率低，产生链表的概率低，查询效率高，空间利用率太低
0.5---1取中间值：0.75
（2）主数组的长度为什么是2^n:
原因1：防止哈希冲突，位置冲突*/