什么是HashMap?
可以分开来看:
- Hash:散列将一个任意长度通过某种(hash函数算法)算法转换成一个固定值。位移算法(hashCode算法)
- Map:通过hash出来的值,通过该值定位到map,然后value存储到这个map中基本原理
1.HashMap与HashSet的区别
简单回答:HashMap的key就是HashSet
原因:【HashMap】 实现Map接口,Map采用(key value)键值对,使用put方法进行数据保存,hashMap使用键对象计算HashCode值,通过唯一的key,可以快速获取对象值;
【hashSet】 实现Set接口,Set是个数组,用add方法存入数据中,而HashCode的值是通过成员对象,进行equals方法比对,获取的值可能相等
---
2.HashMap的底层数据结构
1.7:数组+链表 头插
1.8:数组+链表+红黑树 尾插
---
HashMap如果遇到相同的Key,怎么处理?
key值不变,value覆盖:
public V put (K key ,V value){
if(table==EMPTY_TABLE){
inflateTable(threshold);
}
/**这里是采用PutForNullKey处理null值null键*/
if (key == null)
return putForNullKey(value);
由于HashMap没有Synchronize,所以存在线程安全问题
HashTab:不会处理,在源代码中,发现value为null,就抛出null异常;
但是有Synchronize修饰,不存在线程安全问题;
他的hash冲突算法是:
(hash&0X7FFFFFFF)%tab.length:
好比值为16;取值就在0~15之间;
public Synchronize v put (K key,V value){
if(value==null){
thorw new NullPonterException()
}
}
---
3.HashMap的数组长度为啥必须是2 的N次幂?
- 保证让key能够落在数组的每一位上
- 2的N次幂 初始长度16
- 保证-1必定为奇数
---
4.Hash冲突算法的原理分析
- (n-1)&HashCode: 数组长度-1 & hashCode
- n-1: 数组长度必须是2*N次幂,-1必定为奇数
- 进行-1操作后,得到的最后一位必定为1;
- 进行 ^ 操作时,1&1=1奇数;1&0=0偶数;
- 那么控制最后的值就取决于HashCode值,保证该参数可落在奇数位上,也可以在偶数位上;
- HashCode:取key的高16位与低16位【左低右高】进行 ^(异或)操作
- ^ 相同情况下,保证0,1平均的可能性最大
- 为了上32位的HashCode值,尽可能的参与运算:防止极端情况出现
---
5.HashMap什么时候将链表转换成红黑树
链表长度 >= 8;
HashSet规则:
1. 调用HashCode方法,判断位置上元素hashCode值是否有
1. 有,调用eqauls方法
1. 相等:不存;
2. 不同:覆盖重写
2. 无,直接保存
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
链表[] 链表对象
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判断数组的长度是为 空或者0 ,数组现在还未初始化
if ((tab = table) == null || (n = tab.length) == 0)
// resize : 1.初始化 2.进行数组的扩容
// 通过resize 初始化完毕后,求得数组的长度 并复制给 n
n = (tab = resize()).length;
//存放节点情况一: 计算出来的索引值上并不存在元素-->直接将这个key 放在数组上
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//key相等,value覆盖
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断是否转换成红黑树
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//遍历链表,看最后落在什么位置
else {
for (int binCount = 0; ; ++binCount) {
//没有相等的就创建新的,挂载
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//这里转换成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 8
treeifyBin(tab, hash);
break;
}
//如果有,不保存
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//初始化情况只能是 0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
阈值 扩容临界条件 // 0
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY; //16
newThr = (int)(DEFAULT_LOAD_FACTOR * //1<<<4 16
DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
ConcurrentHashMap:
1.7:segment(分段锁)
1.8:transaction 保证序列化:在初始化时用到【和volatile(内存可视化,保证是最新的线程)】
>>>2 二进制代码右移动 --->n-(n>>>2) 初始化;放值
所谓的便宜,就是数转换成2进制下,左右移动
---
ConcurrentHashMap:和HashMap的区别
Hashmap线程不安全;在多并发下,put操作会引起【死循环】
HashTable线程安全,由于大量使用synchronize,不能进行多并发操作(不能处理null值;null键)
ConcurrentHashMap处理并发环境下,通过使用大量volatile;final;CAS线程安全问题;【不能处理null值;null键】
阈值计算:HashMap------------------0.75*16
conc urrentHashMap----------------n-(n>>>2);
加synchronize时机:
- HashMap:执行HashCode算法和链表挂载时,将整个线程锁上
- concurrentHashMap:执行HashCode算法和链表挂载时,只将要添加的的链表锁上【锁细化】
【扩容:】{NCPU 类------->cpu的核数/性能---->将线程分成16的倍数----->stride(步伐):最少为16}
|
|