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 以及 布隆过滤器
