HashMap底层

HashMap简介

1.实现原理

底层是链表+数组，当链表长度大于8自动转化成红黑树。

首先有一个每个元素都是链表的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，同一各链表上的Hash值是相同的，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。

2.hashMap的java构建

transient Entry[] table;
static class Entry<K,V> implements Map.Entry<K,V>{
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;
    ...
}

3.HashMap的put实现

（1）程序先计算该key的hashCode()值

（2）对该哈希码进行再哈希，然后把哈希值和(数组长度-1)进行按位与操作，得到数组的下标

（3）该位置没有链表节点就把<key,value>放入该位置。有节点就对链表进行遍历，看是否有key一样的节点，有则value进行覆盖更新，没有就创建节点，把节点放链表表头（头插法）。

public V put(K key,V value){
    //HashMap 允许存放null键和null值
    //当key为null时，调用putForNullKey,将value放置在数组第一个位置
    if(key==null){
        return putForNullKey(value);
    }
    //根据key的keycode重新计算hash值
    int hash = hash(key.hascode());
    //搜索指定hash值在对应table的索引
    int i = indexFor(hash,table.length);
    //如果i索引处的entry不为null,通过循环不断遍历e元素的下一个元素
    for(Entry<K,V> e = table[i];e!=null;e = e.next){
        Object k;
        if(e.hash == hash && ((k = e.key) == key || ley.equals(k))){
            V.oldValue = e.value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //如果i索引处的entry为null,表明此处还没有entry
    modCount++;
    //将key、value添加到i索引处
    addEntry(hash,key,value,i);
    return null;
}
void addEntry(int hash,K key,V value,int bucketIndex){
    //获取指定bucketIndex索引处的Entry
    Entry<K,V> e = table[bucketIndex];
  //将新创建的Entry放入bucletIndex索引处，并让新的Enrty指向原来的Entry
   table[bucketIndex] = new Entry<K,V> (hash,key,value,e);
   //如果Map中的key-value对数量超过了极限
   if(size++>=threshold)
       //把table对象的长度扩充为2倍
       resize(2*table.length); 
}
//HashMap长度扩充
void resize(int newCapacity){
    Entry[] oldTable  = table;
    int oldCapacity = oldTable.length;
    if(oldCapacity == MAXIMUM_CAPACITY){
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int) (newCapacity*loadFactor);
}
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)   
    }
}
//进行hash计算
static int indexFor(int hash,int length){
    return hash& (length-1);
}

4.HashMap的get方法

（1）通过key的两次hash的值与数组的长度-1进行按位与操作，定位到数组的某个位置

（2）对该列的链表进行遍历

public V get(Object key){
    if(key == null)
        return getForNullKey();  
     int hash = hash(key.hasCode());
     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.equals(k)){
             return e.value;
         }
     } 
     return null; 
}

5.HashMap总结

（1）hashmap可以存储null值，线性不安全

（2）hashmap扩容：当 HashMap 中的结点个数超过数组大小loadFactor（加载因子） 时， 就会进行数组扩容，loadFactor 的默认值为 0.75。也就是说，默认情况下，数组大小为 16，那么当 HashMap中结点个数超过 160.75=12 的时候， 就把数组的大小扩展为 2*16=32， 即扩大一倍，然后重新计算每个元素在数组中的位置，并放进去， 而这是一个非常消耗性能的操作。

（3）多线程 put 操作后， get 操作导致死循环,导致 cpu100%的现象。 主要是多线程同时put 时， 如果同时触发了 rehash 操作，会导致扩容后的 HashMap 中的链表中出现循环节点， 进而使得后面 get 的时候，会死循环。