HashMap主要用于存储键值对，是最常用的java集合
原理:HashMap.put(key,values),key 调用hash得出一个HashCode ,由于hash碰撞的原因 将values的值存入链表中.HashMap 特性是增删快,ArrayList 底层是集合 所以会查询快 增删需要扩容 增删慢.
HashMap 在Jdk 1.7 和1.8 区别?
jdk1.7 数组+链表 头插法 头插法
jdk 1.8 数组+链表+红黑树 尾插法 +lamda表达式
查询速度:
数组查询速度是O(1)
链表查询速度是O(n)
红黑树查询速度是O(log(n))
主要记录数据:
加载因子:0.75
泊松分布:8
扩容阈值: 0.75* 16
初始大小:1<<<4 16
最大个数:1<<<30 几十亿
扩容:必须是2的幂 直接扩容一倍
1.Hash碰撞?
hash的值是有限的 数据是无线的,所以会出现多个数据的hash会是同一个hashCode 这就是hash碰撞.
解决方案:
在HashMap中运用链表的形式存储values的数据,将一个HashCode的数据存入链表中.
Jdk 1.7 将数据存储到链表中(链表存储过长,会出现查询慢的问题)
Jdk1.8以后根据泊松分布,链表存储8个以后会变成红黑树存储优化了链表大量查询慢的问题.
注意:泊松分布
* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
2.HashMap扩容?
HashMap 默认大小是 16 加载因子是 0.75(时间和空间的折中选择),当存储的数据达到16*0.75 这个阈值的时候就会扩容.扩容的时候会将数据的key重新hash 然后存储到新的容器中.多线程使用HashMap 扩容的时候有可能在产生环形链表的情况, 因为HashMap 是线程不安全的 所以多线程使用的时候要调用ConcurrentHashMap 一个线程安全的HashMap.
3.Jdk1.8 HashMap 底层 增加了红黑树为什么.
链表存储数据的查询速度是O(n),所以当HashMap values数据大量数据存储再链表中的时候会出现查询慢的问题,所以Jdk1.8 的时候Hamp做出了优化.将数据根据不同情况存储到了链表和红黑树(二叉树的特殊平衡树)中.根据泊松分布 在链表中存储了8个数据以后会将数据换到红黑树的这种形式存储.
网友评论