HashMap

hash

取N(1<N<10)個(gè)數(shù) (數(shù)值范圍1~10000000) 判斷某個(gè)數(shù) x是否存在于這個(gè)N個(gè)數(shù)中

開辟數(shù)組 A[10] a[]初始化為{0,0,0,0,0,0,0,0,0,0}
取10的模 4%10 a[4] = 4;
        11%10 a[1] = 11;
        10%10 a[0] = 10;
        判斷x值  即可取 a[x%10] == x來判斷
但是比如 10 和 20 與 10 取摸相等  即hash沖突

解決hash沖突 鏈路地址法

hashmap

jdk1.8 數(shù)組+鏈表+紅黑樹

jdk1.7 數(shù)組+鏈表

圖片.png

定義鏈表

public class Entry<K,V>{
    K key;
    V value;
    Entry<k,V> next;
    int cap;
}

定義hashmap

public class HashMap<K,V>{
    private static final int DEFAULT_SIZE = 1 << 4;
    private Entry<K,V>[] data;//構(gòu)造時(shí)初始化
    private int size = 0;
    private int cap;//初始化空間  默認(rèn)用DEFAULT_SIZE
}

has值

private int has(K key){
    int h = 0;
    if (key == null){
        h = 0;
    }else{
        h = key.hashCode() ^ (h >>> 16);//16位右移后 與運(yùn)算 散列操作
    }
    return h%cap;
}

put操作

public void put(K key,V value){
    int hash = hash(key);
    Entry<K,V> newE = new Entry<>(key,value,null);
    Entry<K,V> hashM = data[hash];
    while(hashM!= null){//遍歷鏈表
        if(hashM.key.equals(key)){
            hashM.value = value;
            break;
        }
        hashM = hashM.next;
    }
    newE.next = data[hash];
    data[hash]= newE;//鏈表的插入]
    size++;
}

get操作

public void get(K key){
    int hash = hash(key);
    Entry<K,V> entry = data[hash];
    while(entry != null){
         if(entry.key.equals(key)){
             return entry.value;
         }
        entry= entry.value;
    }
    return null;
}

hashmap線程不安全原因 put過程中存在擴(kuò)容 擴(kuò)容時(shí)hash值重建

解決方式 put方法中加 synchronized (HashTable)

HashTable 默認(rèn)的初始大小為11 擴(kuò)容機(jī)制 *2+1 (側(cè)重hash分布均勻)

HashMap 默認(rèn)的初始大小為11 擴(kuò)容機(jī)制是 *2 (側(cè)重計(jì)算效率)

ConCurrentHashMap 既高效又線程安全(分段鎖)

大量數(shù)據(jù)存放使用 BitMap 以及 布隆過濾器