java.util.HashMap是很常见的类,前段时间公司系统由于对HashMap使用不当,导致cpu百分之百,在并发环境下使用HashMap
而没有做同步,可能会引起死循环,关于这一点,sun的官方网站上已有阐述,这并非是bug。 |
|
看到next了吗?next就是为了哈希冲突而存在的。比如通过哈希运算,一个新元素应该在数组的第10个位置,但是第10个位置已经有Entry,那么好吧,将新加的元素也放到第10个位置,将第10个位置的原有Entry赋值给当前新加的
Entry的next属性。数组存储的是链表,链表是为了解决哈希冲突的,这一点要注意。
几个关键的属性
存储数据的数组
transient Entry[] table;
这个上面已经讲到了
默认容量
static final int
DEFAULT_INITIAL_CAPACITY = 16;
最大容量
static final int MAXIMUM_CAPACITY = 1 <<
30;
默认加载因子,加载因子是一个比例,当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容
static final float DEFAULT_LOAD_FACTOR =
0.75f;
当实际数据大小超过threshold时,HashMap会将容量扩容,threshold=容量*加载因子
int threshold;
加载因子
final float
loadFactor;
HashMap的初始过程
构造函数1
public HashMap(int initialCapacity, float
loadFactor) {
if
(initialCapacity <
0)
throw new IllegalArgumentException("Illegal initial capacity: "
+
initialCapacity);
if
(initialCapacity >
MAXIMUM_CAPACITY)
initialCapacity =
MAXIMUM_CAPACITY;
if
(loadFactor <= 0 ||
Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+
loadFactor);
// Find a
power of 2 >=
initialCapacity
int capacity
= 1;
while (capacity <
initialCapacity)
capacity <<= 1;
this.loadFactor =
loadFactor;
threshold =
(int)(capacity *
loadFactor);
table = new
Entry[capacity];
init();
}
重点注意这里
while (capacity <
initialCapacity)
capacity <<=
1;
capacity才是初始容量,而不是initialCapacity,这个要特别注意,如果执行new
HashMap(9,0.75);那么HashMap的初始容量是16,而不是9,想想为什么吧。
构造函数2
public HashMap(int initialCapacity)
{
this(initialCapacity,
DEFAULT_LOAD_FACTOR);
}
构造函数3,全部都是默认值
public HashMap() {
this.loadFactor =
DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY *
DEFAULT_LOAD_FACTOR);
table
= new
Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
构造函数4
public HashMap(Map<? extends K, ? extends
V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) +
1,
DEFAULT_INITIAL_CAPACITY),
DEFAULT_LOAD_FACTOR);
putAllForCreate(m);
}
如何哈希
HashMap并不是直接将对象的hashcode作为哈希值的,而是要把key的hashcode作一些运算以得到最终的哈希值,并且得到的哈希值也不是在数组中的位置哦,无论是get还是put还是别的方法,计算哈希值都是这一句:
int hash =
hash(key.hashCode());
hash函数如下:
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
useNewHash声明如下:
private static final boolean useNewHash;
static {
useNewHash = false; }
这说明useNewHash其实一直为false且不可改变的,hash函数里对
useNewHash的判断真是多余的。
private static int oldHash(int h)
{
h += ~(h <<
9);
h ^= (h
>>> 14);
h +=
(h << 4);
h ^=
(h >>> 10);
return
h;
}
private static int
newHash(int h) {
// This
function ensures that hashCodes that differ only
by
// constant multiples at
each bit position have a
bounded
// number of
collisions (approximately 8 at default load
factor).
h ^= (h
>>> 20) ^ (h >>>
12);
return h ^ (h
>>> 7) ^ (h >>> 4);
}
其实HashMap的哈希函数会一直都是oldHash。
如果确定数据的位置
看下面两行
int hash =
hash(k.hashCode());
int i =
indexFor(hash,
table.length);
第一行,上面讲过了,是得到哈希值,第二行,则是根据哈希指计算元素在数组中的位置了,位置的计算是将哈希值和数组长度按位与运算。
static int indexFor(int h, int length)
{
return h &
(length-1);
}
put方法到底作了什么?
public V put(K key, V value)
{
if (key ==
null)
return
putForNullKey(value);
int
hash = hash(key.hashCode());
int i = indexFor(hash,
table.length);
for
(Entry<K,V> e = table[i]; e != null; e = e.next)
{
Object
k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
{
V oldValue =
e.value;
e.value =
value;
e.recordAccess(this);
return
oldValue;
}
}
modCount++;
addEntry(hash,
key, value, i);
return
null;
}
如果key为NULL,则是单独处理的,看看putForNullKey方法:
private V putForNullKey(V value)
{
int hash =
hash(NULL_KEY.hashCode());
int i = indexFor(hash,
table.length);
for
(Entry<K,V> e = table[i]; e != null; e = e.next)
{
if
(e.key == NULL_KEY)
{
V oldValue =
e.value;
e.value =
value;
e.recordAccess(this);
return
oldValue;
}
}
modCount++;
addEntry(hash,
(K) NULL_KEY, value, i);
return null;
}
NULL_KEY的声明:static final
Object NULL_KEY = new
Object();
这一段代码是处理哈希冲突的,就是说,在数组某个位置的对象可能并不是唯一的,它是一个链表结构,根据哈希值找到链表后,还要对链表遍历,找出key相等的对象,替换它,并且返回旧的值。
for
(Entry<K,V> e = table[i]; e != null; e = e.next)
{
if
(e.key == NULL_KEY)
{
V oldValue =
e.value;
e.value =
value;
e.recordAccess(this);
return
oldValue;
}
}
如果遍历完了该位置的链表都没有找到有key相等的,那么将当前对象增加到链表里面去
modCount++;
addEntry(hash, (K)
NULL_KEY, value, i);
return
null;
且看看addEntry方法
void addEntry(int hash, K key, V
value, int bucketIndex) {
Entry<K,V> e =
table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash,
key, value, e);
if
(size++ >=
threshold)
resize(2 * table.length);
}
table[bucketIndex] = new Entry<K,V>(hash, key, value,
e);新建一个Entry对象,并放在当前位置的Entry链表的头部,看看下面的
Entry构造函数就知道了,注意红色部分。
Entry(int h, K k, V v, Entry<K,V> n)
{
value =
v;
next =
n;
key =
k;
hash = h;
}
如何扩容?
当put一个元素时,如果达到了容量限制,HashMap就会扩容,新的容量永远是原来的2倍。
上面的put方法里有这样的一段:
if (size++ >=
threshold)
resize(2 *
table.length);
这是扩容判断,要注意,并不是数据尺寸达到HashMap的最大容量时才扩容,而是达到
threshold指定的值时就开始扩容, threshold=最大容量*加载因子。 看看resize方法
void resize(int newCapacity)
{
Entry[] oldTable =
table;
int oldCapacity =
oldTable.length;
if
(oldCapacity == MAXIMUM_CAPACITY)
{
threshold =
Integer.MAX_VALUE;
return;
}
Entry[] newTable = new
Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold
= (int)(newCapacity * loadFactor);
}
重点看看红色部分的 transfer方法
void transfer(Entry[] newTable)
{
Entry[] src =
table;
int newCapacity =
newTable.length;
for (int j
= 0; j < src.length; j++)
{
Entry<K,V> e =
src[j];
if (e != null)
{
src[j] =
null;
do
{
Entry<K,V> next =
e.next;
int i = indexFor(e.hash, newCapacity);
e.next =
newTable[i];
newTable[i] =
e;
e =
next;
} while (e !=
null);
}
}
}
tranfer方法将所有的元素重新哈希,因为新的容量变大,所以每个元素的哈希值和位置都是不一样的。
正确的使用HashMap
1:不要在并发场景中使用HashMap
HashMap是线程不安全的,如果被多个线程共享的操作,将会引发不可预知的问题,据sun的说法,在扩容时,会引起链表的闭环,在get元素时,就会无限循环,后果是cpu100%。
看看get方法的红色部分
public V get(Object key) {
if
(key == null)
return
getForNullKey();
int hash =
hash(key.hashCode());
for (Entry<K,V> e =
table[indexFor(hash,
table.length)];
e !=
null;
e = e.next)
{
Object
k;
if (e.hash == hash && ((k = e.key) == key ||
key.equals(k)))
return e.value;
}
return
null;
}
2:如果数据大小是固定的,那么最好给HashMap设定一个合理的容量值
根据上面的分析,HashMap的初始默认容量是16,默认加载因子是0.75,也就是说,如果采用HashMap的默认构造函数,当增加数据时,数据实
际容量超过10*0.75=12时,HashMap就扩容,扩容带来一系列的运算,新建一个是原来容量2倍的数组,对原有元素全部重新哈希,如果你的数据
有几千几万个,而用默认的HashMap构造函数,那结果是非常悲剧的,因为HashMap不断扩容,不断哈希,在使用HashMap的场景里,不会是多
个线程共享一个HashMap,除非对HashMap包装并同步,由此产生的内存开销和cpu开销在某些情况下可能是致命的。
发表评论
-
使用spring的动态路由实现数据库负载均衡[转]
2012-10-19 17:23 853使用spring的动态路由实现数据库负载均衡 系 ... -
JSP+MySQL 乱码问题的总结【转】
2012-09-19 15:29 619转自 “http://www.netjsp.com/ma ... -
java开发常用配置(持续更新)
2012-08-29 17:01 703记性不好的人伤不起,才4个月就把java ide配置忘光了阿 ... -
jedis-双节点可用性自动检测
2012-04-12 15:29 939在jedis的基础上,增加了“2个redis nodes时的故 ... -
java常见知识点收集
2012-02-03 12:04 9221 java 的参数传递方式 : 都是值传递,没有指针传 ... -
关于hashmap的性能实现
2012-01-06 10:25 22431.在哈希术语中,内部数组中的每个位置称作“存储桶”(bu ... -
java hashmap
2012-01-06 10:24 19761、hashmap的数据结构 要知道hashmap是什 ... -
java io in tomcat
2011-12-29 16:36 681java io in tomcat http://www.i ... -
java设计模式(原文作者不详)
2011-10-15 13:12 673这篇文章写的很棒(我 ... -
JVM内存模型
2011-10-12 17:56 687原文地址:http://hi.baidu.com/xuwanb ... -
BufferedReader.readLine()总结
2011-09-24 23:23 25267BufferedReader.readLine() 最近 ... -
如何提高Java 多线程应用性能(转)
2011-09-23 12:39 1280如何提高Java 多线程 ... -
java mail的介绍
2011-09-22 15:24 759以下是转载的关于java mail的介绍 Sess ...
相关推荐
2022年Java中对HashMap的深度分析Java教程.docx
HashMap源码深度剖析,面试必备
在Java的世界里,无论类还是各种数据,其结构的处理是整个程序的逻辑以及性能的关键。由于本人接触了一个有关性能与逻辑同时并存的问题,于是就开始研究这方面的问题。找遍了大大小小的论坛,也把《Java 虚拟机规范...
·全程内容涵盖数据结构、设计模式、JVM内存结构等深度技术 ·企业级笔试面试题目深入源码级讲解,拒绝死记硬背 4.代码量更大、案例更丰富、更贴近实战: ·Java语言基础阶段:12720行代码,Java语言高级阶段:...
java面试笔试资料包括JAVA基础核心知识点深度学习Spring面试题等资料合集: JAVA核心知识点整理-282页 Java与哈希算法.docx Java中Lambda表达式的使用.docx JAVA多线程之线程间的通信方式.docx Java注解详解.docx ...
讨论如何分析和优化Java应用程序的性能等。 通过深入学习和理解这些问题,Java开发者不仅可以提升自己的技术能力,还能更好地应对面试挑战,展现自己的专业素养和问题解决能力。建议读者结合实际代码示例和项目经验...
引领互联网最新技术潮流,手把手带您轻松月入2万+,三年逆袭Java互联网架构师的经验传授与您~ 〖课程目录〗: 01架构师必备技能之设计模式 02架构师必备安全技能 03从零开始学习多线程技术 04架构师必备技能并发编程...
JAVA企业级基础课题(HashMap那些事) 企业架构师必备技能(JAVA核心技术反射) JavaWeb之基础(手写实现Tomcat服务器) java多线程编程 纯手写实现SpringIOC实现过程 JEE企业级开发(企业级项目开发权威指南) 网络爬虫之...
类字节码文件深度剖析 垃圾收集机制详解 十种垃圾收集器详解 JVM调优工具详解 GC日志详细分析 JVM调优实战 Mysql性能调优 SQL执行原理详解 索引底层剖析 执行计划与SQL优化 Mysql锁机制与事务隔离级别详解 并发编程 ...
你可以链接有深度的博客文章 你可以分享自己的学习历程 这个计划需要你们的加入 Peace~Yo 计算机基础篇 常用工具篇 J2SE基础 JVM 虚拟机 基本框架篇 Spring篇 消息队列 缓存中间件 数据库 搜索引擎篇 文件目录中有...
常用集合底层原理深度解析,包括arraylist,hashmap,hashset,linkedarrayList,面试必备!
java lru leetcode Python 的算法游乐场 这是 Python 版,也有 Java 版。...目前,这是一个纯 ...单元测试正在使用内置单元测试(将来可能会更改)...深度优先搜索 基本算法思维 递归 分而治之 贪婪的 回溯 动态规划 先进的数
冒泡排序,插入排序,选择排序,快速排序,堆排序,合并排序,广度优先搜索,深度优先搜索,二进制搜索,lru,dijkstra,A *(计划中) 概念 位操作,OOP,动态编程,图形(计划的) 破解编码面试 (〜2.7。交集) ...
用数组值查找排列位置想要达到O(1),用HashMap--常用技巧。 20有效的括号:【栈】。 21合并两个有序链表:可以【循环】,也可以采用【递归】。 53最大子序和:一次循环,maxEndingHere存储以该点结尾的子序和,...