HashMap

HashMap

hash

取N(1<N<10)个数 (数值范围1~10000000) 判断某个数 x是否存在于这个N个数中

开辟数组 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 数组+链表+红黑树

jdk1.7 数组+链表

图片.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;//构造时初始化
    private int size = 0;
    private int cap;//初始化空间  默认用DEFAULT_SIZE
}

has值

private int has(K key){
    int h = 0;
    if (key == null){
        h = 0;
    }else{
        h = key.hashCode() ^ (h >>> 16);//16位右移后 与运算 散列操作
    }
    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过程中存在扩容 扩容时hash值重建

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

HashTable 默认的初始大小为11 扩容机制 *2+1 (侧重hash分布均匀)

HashMap 默认的初始大小为11 扩容机制是 *2 (侧重计算效率)

ConCurrentHashMap 既高效又线程安全(分段锁)

大量数据存放使用 BitMap 以及 布隆过滤器