- 浏览: 21610 次
- 性别:
- 来自: 上海
最近访客 更多访客>>
文章分类
最新评论
-
tohsj0806:
http://blog.csdn.net/whuslei/ar ...
java中final的学习笔记 -
tohsj0806:
归纳上述回答的真正核心是:局部内部类对象中包含有要访问的fin ...
java中final的学习笔记 -
tohsj0806:
今天看到,局部内部类要使用局部变量,那么这个局部变量必须是fi ...
java中final的学习笔记 -
冯东伟:
读jar中的properties -
冯东伟:
读jar中的properties
HashMap深入浅出
文章来源:http://www.iteye.com/topic/539465;http://www.iteye.com/topic/754887
Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap的文章很多,但到底是自己学习的总结,就发出来跟大家一起分享,一起讨论。
1、hashmap的数据结构
要知道hashmap是什么,首先要搞清楚它的数据结构,在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,hashmap也不例外。Hashmap实际上是一个数组和链表的结合体(在数据结构中,一般称之为“链表散列“),请看下图(横排表示数组,纵排表示数组元素【实际上是一个链表】)。
从图中我们可以看到一个hashmap就是一个数组结构,当新建一个hashmap的时候,就会初始化一个数组。我们来看看java代码:
Java代码
1./**
2. * The table, resized as necessary. Length MUST Always be a power of two.
3. * FIXME 这里需要注意这句话,至于原因后面会讲到
4. */
5. transient Entry[] table;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* FIXME 这里需要注意这句话,至于原因后面会讲到
*/
transient Entry[] table;
Java代码
1.static class Entry<K,V> implements Map.Entry<K,V> {
2. final K key;
3. V value;
4. final int hash;
5. Entry<K,V> next;
6...........
7.}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
..........
}
上面的Entry就是数组中的元素,它持有一个指向下一个元素的引用,这就构成了链表。
当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的,但是理想总是美好的,现实总是有困难需要我们去克服,哈哈~
2、hash算法
我们可以看到在hashmap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合,所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,能不能找一种更快速,消耗更小的方式那?java中时这样做的,
Java代码
1.static int indexFor(int h, int length) {
2. return h & (length-1);
3. }
static int indexFor(int h, int length) {
return h & (length-1);
}
首先算得key得hashcode值,然后跟数组的长度-1做一次“与”运算(&)。看上去很简单,其实比较有玄机。比如数组的长度是2的4次方,那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高,我以2的4次方举例,来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
看下图,左边两组是数组长度为16(2的4次方),右边两组是数组长度为15。两组的hashcode均为8和9,但是很明显,当它们和1110“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到同一个链表上,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hashcode的值会与14(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!
所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
说到这里,我们再回头看一下hashmap中默认的数组大小是多少,查看源代码可以得知是16,为什么是16,而不是15,也不是20呢,看到上面annegu的解释之后我们就清楚了吧,显然是因为16是2的整数次幂的原因,在小数据量的情况下16比15和20更能减少key之间的碰撞,而加快查询的效率。
所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的,代码如下(HashMap的构造方法中):
Java代码
1.// Find a power of 2 >= initialCapacity
2. int capacity = 1;
3. while (capacity < initialCapacity)
4. capacity <<= 1;
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
3、hashmap的resize
当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。
4、key的hashcode与equals方法改写
在第一部分hashmap的数据结构中,annegu就写了get方法的过程:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。所以,hashcode与equals方法对于找到对应元素是两个关键方法。
Hashmap的key可以是任何类型的对象,例如User这种对象,为了保证两个具有相同属性的user的hashcode相同,我们就需要改写hashcode方法,比方把hashcode值的计算与User对象的id关联起来,那么只要user对象拥有相同id,那么他们的hashcode也能保持一致了,这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素,还需要用key的equals方法在对应位置的链表中找到需要的元素,所以只改写了hashcode方法是不够的,equals方法也是需要改写滴~当然啦,按正常思维逻辑,equals方法一般都会根据实际的业务内容来定义,例如根据user对象的id来判断两个user是否相等。
在改写equals方法的时候,需要满足以下三点:
(1) 自反性:就是说a.equals(a)必须为true。
(2) 对称性:就是说a.equals(b)=true的话,b.equals(a)也必须为true。
(3) 传递性:就是说a.equals(b)=true,并且b.equals(c)=true的话,a.equals(c)也必须为true。
通过改写key对象的equals和hashcode方法,我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
总结:
本文主要描述了HashMap的结构,和hashmap中hash函数的实现,以及该实现的特性,同时描述了hashmap中resize带来性能消耗的根本原因,以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现,可以说是整个HashMap的精髓所在,只有真正理解了这个hash函数,才可以说对HashMap有了一定的理解。
java.util.HashMap是很常见的类,前段时间公司系统由于对HashMap使用不当,导致cpu百分之百,在并发环境下使用HashMap 而没有做同步,可能会引起死循环,关于这一点,sun的官方网站上已有阐述,这并非是bug。
HashMap的数据结构
HashMap主要是用数组来存储数据的,我们都知道它会对key进行哈希运算,哈系运算会有重复的哈希值,对于哈希值的冲突,HashMap采用链表来解决的。在HashMap里有这样的一句属性声明:
transient Entry[] table;
Entry就是HashMap存储数据所用的类,它拥有的属性如下
final K key;
V value;
final int hash;
Entry<K,V> next;
看到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
Java代码
1.public HashMap(int initialCapacity, float loadFactor) {
2. if (initialCapacity < 0)
3. throw new IllegalArgumentException("Illegal initial capacity: " +
4. initialCapacity);
5. if (initialCapacity > MAXIMUM_CAPACITY)
6. initialCapacity = MAXIMUM_CAPACITY;
7. if (loadFactor <= 0 || Float.isNaN(loadFactor))
8. throw new IllegalArgumentException("Illegal load factor: " +
9. loadFactor);
10.
11. // Find a power of 2 >= initialCapacity
12. int capacity = 1;
13. while (capacity < initialCapacity)
14. capacity <<= 1;
15.
16. this.loadFactor = loadFactor;
17. threshold = (int)(capacity * loadFactor);
18. table = new Entry[capacity];
19. init();
20.}
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();
}
重点注意这里
Java代码
1.while (capacity < initialCapacity)
2. capacity <<= 1;
while (capacity < initialCapacity)
capacity <<= 1;
capacity才是初始容量,而不是initialCapacity,这个要特别注意,如果执行new HashMap(9,0.75);那么HashMap的初始容量是16,而不是9,想想为什么吧。
构造函数2
Java代码
1.public HashMap(int initialCapacity) {
2. this(initialCapacity, DEFAULT_LOAD_FACTOR);
3. }
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造函数3,全部都是默认值
Java代码
1.public HashMap() {
2. this.loadFactor = DEFAULT_LOAD_FACTOR;
3. threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
4. table = new Entry[DEFAULT_INITIAL_CAPACITY];
5. init();
6. }
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
构造函数4
Java代码
1.public HashMap(Map<? extends K, ? extends V> m) {
2. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
3. DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
4. putAllForCreate(m);
5. }
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函数如下:
Java代码
1.static int hash(int h) {
2. return useNewHash ? newHash(h) : oldHash(h);
3. }
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
useNewHash声明如下:
Java代码
1.private static final boolean useNewHash;
2. static { useNewHash = false; }
private static final boolean useNewHash;
static { useNewHash = false; }
这说明useNewHash其实一直为false且不可改变的,hash函数里对 useNewHash的判断真是多余的。
Java代码
1.private static int oldHash(int h) {
2. h += ~(h << 9);
3. h ^= (h >>> 14);
4. h += (h << 4);
5. h ^= (h >>> 10);
6. return h;
7.}
8.
9.private static int newHash(int h) {
10. // This function ensures that hashCodes that differ only by
11. // constant multiples at each bit position have a bounded
12. // number of collisions (approximately 8 at default load factor).
13. h ^= (h >>> 20) ^ (h >>> 12);
14. return h ^ (h >>> 7) ^ (h >>> 4);
15.}
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。
如果确定数据的位置
看下面两行
Java代码
1.int hash = hash(k.hashCode());
2. int i = indexFor(hash, table.length);
int hash = hash(k.hashCode());
int i = indexFor(hash, table.length);
第一行,上面讲过了,是得到哈希值,第二行,则是根据哈希指计算元素在数组中的位置了,位置的计算是将哈希值和数组长度按位与运算。
Java代码
1.static int indexFor(int h, int length) {
2. return h & (length-1);
3. }
static int indexFor(int h, int length) {
return h & (length-1);
}
“h & (length-1)”其实这里是很有讲究的,为什么是和(length-1)进行按位与运算呢?这样做是为了提高HashMap的效率。什么?这样能提高效率?且听我细细道来。
首先我们要确定一下,HashMap的数组长度永远都是偶数,即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部,上面也讲过,有这样的一段代码:
Java代码
1.while (capacity < initialCapacity)
2. capacity <<= 1;
while (capacity < initialCapacity)
capacity <<= 1;
所以length-1一定是个奇数,假设现在长度为16,减去1后就是15,对应的二进制是:1111。
假设有两个元素,一个哈希值是8,二进制是1000,一个哈希值是9,二进制是1001。和1111与运算后,分别还是1000和1001,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。
那么,如果数组长度是奇数,减去1后就是偶数了,偶数对应的二进制最低位一定是0了,例如14二进制1110。对上面两个数子分别与运算,得到1000和1000。看到了吗?都是一样的值,哈希值8和9的元素多被存储在数组同一个位置的链表中。在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。所以,一定要哈希均匀分布,尽量减少哈希冲突,减少了哈希冲突,就减少了链表循环,就提高了效率。
put方法到底作了什么?
Java代码
1.public V put(K key, V value) {
2. if (key == null)
3. return putForNullKey(value);
4. int hash = hash(key.hashCode());
5. int i = indexFor(hash, table.length);
6. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
7. Object k;
8. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9. V oldValue = e.value;
10. e.value = value;
11. e.recordAccess(this);
12. return oldValue;
13. }
14. }
15.
16. modCount++;
17. addEntry(hash, key, value, i);
18. return null;
19. }
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方法:
Java代码
1.private V putForNullKey(V value) {
2. int hash = hash(NULL_KEY.hashCode());
3. int i = indexFor(hash, table.length);
4.
5. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
6. if (e.key == NULL_KEY) {
7. V oldValue = e.value;
8. e.value = value;
9. e.recordAccess(this);
10. return oldValue;
11. }
12. }
13.
14. modCount++;
15. addEntry(hash, (K) NULL_KEY, value, i);
16. return null;
17. }
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相等的对象,替换它,并且返回旧的值。
Java代码
1.for (Entry<K,V> e = table[i]; e != null; e = e.next) {
2. if (e.key == NULL_KEY) {
3. V oldValue = e.value;
4. e.value = value;
5. e.recordAccess(this);
6. return oldValue;
7. }
8. }
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相等的,那么将当前对象增加到链表里面去
Java代码
1.modCount++;
2.addEntry(hash, (K) NULL_KEY, value, i);
3.return null;
modCount++;
addEntry(hash, (K) NULL_KEY, value, i);
return null;
且看看addEntry方法
Java代码
1.void addEntry(int hash, K key, V value, int bucketIndex) {
2.Entry<K,V> e = table[bucketIndex];
3. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
4. if (size++ >= threshold)
5. resize(2 * table.length);
6.}
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构造函数就知道了,注意红色部分。
Java代码
1.Entry(int h, K k, V v, Entry<K,V> n) {
2. value = v;
3. next = n;
4. key = k;
5. hash = h;
6. }
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
如何扩容?
当put一个元素时,如果达到了容量限制,HashMap就会扩容,新的容量永远是原来的2倍。
上面的put方法里有这样的一段:
Java代码
1.if (size++ >= threshold)
2. resize(2 * table.length);
if (size++ >= threshold)
resize(2 * table.length);
这是扩容判断,要注意,并不是数据尺寸达到HashMap的最大容量时才扩容,而是达到 threshold指定的值时就开始扩容, threshold=最大容量*加载因子。 看看resize方法
Java代码
1.void resize(int newCapacity) {
2. Entry[] oldTable = table;
3. int oldCapacity = oldTable.length;
4. if (oldCapacity == MAXIMUM_CAPACITY) {
5. threshold = Integer.MAX_VALUE;
6. return;
7. }
8.
9. Entry[] newTable = new Entry[newCapacity];
10. transfer(newTable);
11. table = newTable;
12. threshold = (int)(newCapacity * loadFactor);
13. }
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方法
Java代码
1.void transfer(Entry[] newTable) {
2. Entry[] src = table;
3. int newCapacity = newTable.length;
4. for (int j = 0; j < src.length; j++) {
5. Entry<K,V> e = src[j];
6. if (e != null) {
7. src[j] = null;
8. do {
9. Entry<K,V> next = e.next;
10. int i = indexFor(e.hash, newCapacity);
11. e.next = newTable[i];
12. newTable[i] = e;
13. e = next;
14. } while (e != null);
15. }
16. }
17. }
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的元素查找大致分为三步:
根据key的hasocde()得到哈希值
根据哈希值确定元素在数组中的位置
找到指定位置的链表,循环比较,先“==”比较,如果不等,再“equals”比较,如果有一个比较相等,就说明找到元素了。
所以说到这里,我想大家也明白了,为什么要把一个对象放进HashMap的时候,最好是重写hashcode()方法和equals 方法呢?根据前面的分析,hashcode()可以确定元素在数组中的位置,而equals方法在链表的比较时要用到。
正确的使用HashMap
1:不要在并发场景中使用HashMap
HashMap是线程不安全的,如果被多个线程共享的操作,将会引发不可预知的问题,据sun的说法,在扩容时,会引起链表的闭环,在get元素时,就会无限循环,后果是cpu100%。
看看get方法的红色部分
Java代码
1.public V get(Object key) {
2. if (key == null)
3. return getForNullKey();
4. int hash = hash(key.hashCode());
5. for (Entry<K,V> e = table[indexFor(hash, table.length)];
6. e != null;
7. e = e.next) {
8. Object k;
9. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
10. return e.value;
11. }
12. return null;
13. }
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开销在某些情况下可能是致命的。
Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap的文章很多,但到底是自己学习的总结,就发出来跟大家一起分享,一起讨论。
1、hashmap的数据结构
要知道hashmap是什么,首先要搞清楚它的数据结构,在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,hashmap也不例外。Hashmap实际上是一个数组和链表的结合体(在数据结构中,一般称之为“链表散列“),请看下图(横排表示数组,纵排表示数组元素【实际上是一个链表】)。
从图中我们可以看到一个hashmap就是一个数组结构,当新建一个hashmap的时候,就会初始化一个数组。我们来看看java代码:
Java代码
1./**
2. * The table, resized as necessary. Length MUST Always be a power of two.
3. * FIXME 这里需要注意这句话,至于原因后面会讲到
4. */
5. transient Entry[] table;
/**
* The table, resized as necessary. Length MUST Always be a power of two.
* FIXME 这里需要注意这句话,至于原因后面会讲到
*/
transient Entry[] table;
Java代码
1.static class Entry<K,V> implements Map.Entry<K,V> {
2. final K key;
3. V value;
4. final int hash;
5. Entry<K,V> next;
6...........
7.}
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
final int hash;
Entry<K,V> next;
..........
}
上面的Entry就是数组中的元素,它持有一个指向下一个元素的引用,这就构成了链表。
当我们往hashmap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置(即下标),然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的,但是理想总是美好的,现实总是有困难需要我们去克服,哈哈~
2、hash算法
我们可以看到在hashmap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过hashmap的数据结构是数组和链表的结合,所以我们当然希望这个hashmap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表。
所以我们首先想到的就是把hashcode对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,能不能找一种更快速,消耗更小的方式那?java中时这样做的,
Java代码
1.static int indexFor(int h, int length) {
2. return h & (length-1);
3. }
static int indexFor(int h, int length) {
return h & (length-1);
}
首先算得key得hashcode值,然后跟数组的长度-1做一次“与”运算(&)。看上去很简单,其实比较有玄机。比如数组的长度是2的4次方,那么hashcode就会和2的4次方-1做“与”运算。很多人都有这个疑问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高,我以2的4次方举例,来解释一下为什么数组大小为2的幂时hashmap访问的性能最高。
看下图,左边两组是数组长度为16(2的4次方),右边两组是数组长度为15。两组的hashcode均为8和9,但是很明显,当它们和1110“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8和9会被放到同一个链表上,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hashcode的值会与14(1110)进行“与”,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!
所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。
说到这里,我们再回头看一下hashmap中默认的数组大小是多少,查看源代码可以得知是16,为什么是16,而不是15,也不是20呢,看到上面annegu的解释之后我们就清楚了吧,显然是因为16是2的整数次幂的原因,在小数据量的情况下16比15和20更能减少key之间的碰撞,而加快查询的效率。
所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方。就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的,代码如下(HashMap的构造方法中):
Java代码
1.// Find a power of 2 >= initialCapacity
2. int capacity = 1;
3. while (capacity < initialCapacity)
4. capacity <<= 1;
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
3、hashmap的resize
当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的“均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能。比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题。
4、key的hashcode与equals方法改写
在第一部分hashmap的数据结构中,annegu就写了get方法的过程:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。所以,hashcode与equals方法对于找到对应元素是两个关键方法。
Hashmap的key可以是任何类型的对象,例如User这种对象,为了保证两个具有相同属性的user的hashcode相同,我们就需要改写hashcode方法,比方把hashcode值的计算与User对象的id关联起来,那么只要user对象拥有相同id,那么他们的hashcode也能保持一致了,这样就可以找到在hashmap数组中的位置了。如果这个位置上有多个元素,还需要用key的equals方法在对应位置的链表中找到需要的元素,所以只改写了hashcode方法是不够的,equals方法也是需要改写滴~当然啦,按正常思维逻辑,equals方法一般都会根据实际的业务内容来定义,例如根据user对象的id来判断两个user是否相等。
在改写equals方法的时候,需要满足以下三点:
(1) 自反性:就是说a.equals(a)必须为true。
(2) 对称性:就是说a.equals(b)=true的话,b.equals(a)也必须为true。
(3) 传递性:就是说a.equals(b)=true,并且b.equals(c)=true的话,a.equals(c)也必须为true。
通过改写key对象的equals和hashcode方法,我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要)。
总结:
本文主要描述了HashMap的结构,和hashmap中hash函数的实现,以及该实现的特性,同时描述了hashmap中resize带来性能消耗的根本原因,以及将普通的域模型对象作为key的基本要求。尤其是hash函数的实现,可以说是整个HashMap的精髓所在,只有真正理解了这个hash函数,才可以说对HashMap有了一定的理解。
java.util.HashMap是很常见的类,前段时间公司系统由于对HashMap使用不当,导致cpu百分之百,在并发环境下使用HashMap 而没有做同步,可能会引起死循环,关于这一点,sun的官方网站上已有阐述,这并非是bug。
HashMap的数据结构
HashMap主要是用数组来存储数据的,我们都知道它会对key进行哈希运算,哈系运算会有重复的哈希值,对于哈希值的冲突,HashMap采用链表来解决的。在HashMap里有这样的一句属性声明:
transient Entry[] table;
Entry就是HashMap存储数据所用的类,它拥有的属性如下
final K key;
V value;
final int hash;
Entry<K,V> next;
看到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
Java代码
1.public HashMap(int initialCapacity, float loadFactor) {
2. if (initialCapacity < 0)
3. throw new IllegalArgumentException("Illegal initial capacity: " +
4. initialCapacity);
5. if (initialCapacity > MAXIMUM_CAPACITY)
6. initialCapacity = MAXIMUM_CAPACITY;
7. if (loadFactor <= 0 || Float.isNaN(loadFactor))
8. throw new IllegalArgumentException("Illegal load factor: " +
9. loadFactor);
10.
11. // Find a power of 2 >= initialCapacity
12. int capacity = 1;
13. while (capacity < initialCapacity)
14. capacity <<= 1;
15.
16. this.loadFactor = loadFactor;
17. threshold = (int)(capacity * loadFactor);
18. table = new Entry[capacity];
19. init();
20.}
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();
}
重点注意这里
Java代码
1.while (capacity < initialCapacity)
2. capacity <<= 1;
while (capacity < initialCapacity)
capacity <<= 1;
capacity才是初始容量,而不是initialCapacity,这个要特别注意,如果执行new HashMap(9,0.75);那么HashMap的初始容量是16,而不是9,想想为什么吧。
构造函数2
Java代码
1.public HashMap(int initialCapacity) {
2. this(initialCapacity, DEFAULT_LOAD_FACTOR);
3. }
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
构造函数3,全部都是默认值
Java代码
1.public HashMap() {
2. this.loadFactor = DEFAULT_LOAD_FACTOR;
3. threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
4. table = new Entry[DEFAULT_INITIAL_CAPACITY];
5. init();
6. }
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
构造函数4
Java代码
1.public HashMap(Map<? extends K, ? extends V> m) {
2. this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
3. DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
4. putAllForCreate(m);
5. }
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函数如下:
Java代码
1.static int hash(int h) {
2. return useNewHash ? newHash(h) : oldHash(h);
3. }
static int hash(int h) {
return useNewHash ? newHash(h) : oldHash(h);
}
useNewHash声明如下:
Java代码
1.private static final boolean useNewHash;
2. static { useNewHash = false; }
private static final boolean useNewHash;
static { useNewHash = false; }
这说明useNewHash其实一直为false且不可改变的,hash函数里对 useNewHash的判断真是多余的。
Java代码
1.private static int oldHash(int h) {
2. h += ~(h << 9);
3. h ^= (h >>> 14);
4. h += (h << 4);
5. h ^= (h >>> 10);
6. return h;
7.}
8.
9.private static int newHash(int h) {
10. // This function ensures that hashCodes that differ only by
11. // constant multiples at each bit position have a bounded
12. // number of collisions (approximately 8 at default load factor).
13. h ^= (h >>> 20) ^ (h >>> 12);
14. return h ^ (h >>> 7) ^ (h >>> 4);
15.}
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。
如果确定数据的位置
看下面两行
Java代码
1.int hash = hash(k.hashCode());
2. int i = indexFor(hash, table.length);
int hash = hash(k.hashCode());
int i = indexFor(hash, table.length);
第一行,上面讲过了,是得到哈希值,第二行,则是根据哈希指计算元素在数组中的位置了,位置的计算是将哈希值和数组长度按位与运算。
Java代码
1.static int indexFor(int h, int length) {
2. return h & (length-1);
3. }
static int indexFor(int h, int length) {
return h & (length-1);
}
“h & (length-1)”其实这里是很有讲究的,为什么是和(length-1)进行按位与运算呢?这样做是为了提高HashMap的效率。什么?这样能提高效率?且听我细细道来。
首先我们要确定一下,HashMap的数组长度永远都是偶数,即使你在初始化的时候是这样的new HashMap(15,0.75);因为在构造函数内部,上面也讲过,有这样的一段代码:
Java代码
1.while (capacity < initialCapacity)
2. capacity <<= 1;
while (capacity < initialCapacity)
capacity <<= 1;
所以length-1一定是个奇数,假设现在长度为16,减去1后就是15,对应的二进制是:1111。
假设有两个元素,一个哈希值是8,二进制是1000,一个哈希值是9,二进制是1001。和1111与运算后,分别还是1000和1001,它们被分配在了数组的不同位置,这样,哈希的分布非常均匀。
那么,如果数组长度是奇数,减去1后就是偶数了,偶数对应的二进制最低位一定是0了,例如14二进制1110。对上面两个数子分别与运算,得到1000和1000。看到了吗?都是一样的值,哈希值8和9的元素多被存储在数组同一个位置的链表中。在操作的时候,链表中的元素越多,效率越低,因为要不停的对链表循环比较。所以,一定要哈希均匀分布,尽量减少哈希冲突,减少了哈希冲突,就减少了链表循环,就提高了效率。
put方法到底作了什么?
Java代码
1.public V put(K key, V value) {
2. if (key == null)
3. return putForNullKey(value);
4. int hash = hash(key.hashCode());
5. int i = indexFor(hash, table.length);
6. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
7. Object k;
8. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
9. V oldValue = e.value;
10. e.value = value;
11. e.recordAccess(this);
12. return oldValue;
13. }
14. }
15.
16. modCount++;
17. addEntry(hash, key, value, i);
18. return null;
19. }
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方法:
Java代码
1.private V putForNullKey(V value) {
2. int hash = hash(NULL_KEY.hashCode());
3. int i = indexFor(hash, table.length);
4.
5. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
6. if (e.key == NULL_KEY) {
7. V oldValue = e.value;
8. e.value = value;
9. e.recordAccess(this);
10. return oldValue;
11. }
12. }
13.
14. modCount++;
15. addEntry(hash, (K) NULL_KEY, value, i);
16. return null;
17. }
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相等的对象,替换它,并且返回旧的值。
Java代码
1.for (Entry<K,V> e = table[i]; e != null; e = e.next) {
2. if (e.key == NULL_KEY) {
3. V oldValue = e.value;
4. e.value = value;
5. e.recordAccess(this);
6. return oldValue;
7. }
8. }
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相等的,那么将当前对象增加到链表里面去
Java代码
1.modCount++;
2.addEntry(hash, (K) NULL_KEY, value, i);
3.return null;
modCount++;
addEntry(hash, (K) NULL_KEY, value, i);
return null;
且看看addEntry方法
Java代码
1.void addEntry(int hash, K key, V value, int bucketIndex) {
2.Entry<K,V> e = table[bucketIndex];
3. table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
4. if (size++ >= threshold)
5. resize(2 * table.length);
6.}
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构造函数就知道了,注意红色部分。
Java代码
1.Entry(int h, K k, V v, Entry<K,V> n) {
2. value = v;
3. next = n;
4. key = k;
5. hash = h;
6. }
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
如何扩容?
当put一个元素时,如果达到了容量限制,HashMap就会扩容,新的容量永远是原来的2倍。
上面的put方法里有这样的一段:
Java代码
1.if (size++ >= threshold)
2. resize(2 * table.length);
if (size++ >= threshold)
resize(2 * table.length);
这是扩容判断,要注意,并不是数据尺寸达到HashMap的最大容量时才扩容,而是达到 threshold指定的值时就开始扩容, threshold=最大容量*加载因子。 看看resize方法
Java代码
1.void resize(int newCapacity) {
2. Entry[] oldTable = table;
3. int oldCapacity = oldTable.length;
4. if (oldCapacity == MAXIMUM_CAPACITY) {
5. threshold = Integer.MAX_VALUE;
6. return;
7. }
8.
9. Entry[] newTable = new Entry[newCapacity];
10. transfer(newTable);
11. table = newTable;
12. threshold = (int)(newCapacity * loadFactor);
13. }
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方法
Java代码
1.void transfer(Entry[] newTable) {
2. Entry[] src = table;
3. int newCapacity = newTable.length;
4. for (int j = 0; j < src.length; j++) {
5. Entry<K,V> e = src[j];
6. if (e != null) {
7. src[j] = null;
8. do {
9. Entry<K,V> next = e.next;
10. int i = indexFor(e.hash, newCapacity);
11. e.next = newTable[i];
12. newTable[i] = e;
13. e = next;
14. } while (e != null);
15. }
16. }
17. }
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的元素查找大致分为三步:
根据key的hasocde()得到哈希值
根据哈希值确定元素在数组中的位置
找到指定位置的链表,循环比较,先“==”比较,如果不等,再“equals”比较,如果有一个比较相等,就说明找到元素了。
所以说到这里,我想大家也明白了,为什么要把一个对象放进HashMap的时候,最好是重写hashcode()方法和equals 方法呢?根据前面的分析,hashcode()可以确定元素在数组中的位置,而equals方法在链表的比较时要用到。
正确的使用HashMap
1:不要在并发场景中使用HashMap
HashMap是线程不安全的,如果被多个线程共享的操作,将会引发不可预知的问题,据sun的说法,在扩容时,会引起链表的闭环,在get元素时,就会无限循环,后果是cpu100%。
看看get方法的红色部分
Java代码
1.public V get(Object key) {
2. if (key == null)
3. return getForNullKey();
4. int hash = hash(key.hashCode());
5. for (Entry<K,V> e = table[indexFor(hash, table.length)];
6. e != null;
7. e = e.next) {
8. Object k;
9. if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
10. return e.value;
11. }
12. return null;
13. }
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开销在某些情况下可能是致命的。
相关推荐
《深入浅出Java》这本书以其独特的讲解方式,旨在让学习者轻松掌握复杂的Java编程语言。"深入浅出"这一理念,意味着作者通过直观、生动的示例和丰富的图解,帮助读者逐步理解Java的核心概念和技术。 Java是一种广泛...
07丨深入浅出HashMap的设计与优化.html
《深入浅出Java语言程序设计》是一本专为Java初学者和进阶者精心编写的教程,旨在帮助读者全面理解并掌握Java编程的核心概念和技术。本书涵盖了从基础语法到高级特性的广泛内容,旨在使读者能够熟练运用Java进行软件...
【标题】"Java深入浅出哥哥复合管"可能是指一个关于Java编程的教程或课程,其中"哥哥复合管"可能是作者或讲师的别称,或者是某种特定编程概念的比喻。这个标题暗示了内容将深入讲解Java语言,并可能涵盖一些高级或...
《深入浅出Java 2面向对象程序设计》是一本针对Java编程初学者和进阶者的重要教程,旨在帮助读者深入理解和掌握面向对象编程的核心概念和技术。面向对象编程(Object-Oriented Programming,简称OOP)是Java语言的...
《深入浅出Java2面向对象程序设计》是一本旨在帮助读者深入理解Java编程语言和面向对象编程概念的书籍。随书附带的光盘包含了源代码、习题解答以及实验工具,为学习者提供了丰富的实践资源,使得理论与实践相结合,...
《深入浅出Java语言程序设计》是一本专为初学者和有一定基础的程序员设计的教程,旨在通过由浅入深的方式,系统性地讲解Java编程的核心概念和技术。这本书的特色在于其详细的解释和通俗易懂的语言,使得学习者能够...
在深入浅出的讲解中,本书涵盖了Java编程的基础知识,包括: 1. **Java简介**:首先介绍Java的历史背景、特点以及为什么选择Java作为学习的编程语言。书中可能以生动的故事或比喻解释,帮助读者理解Java在软件开发...
《深入浅出Java语言程序设计》是一本旨在帮助初学者和有一定经验的开发者更深入理解Java编程的教材。这本书不仅覆盖了Java的基础知识,还深入探讨了许多高级特性,帮助读者构建坚实的Java编程基础。 首先,Java的...
《Java2深入浅出》是一本旨在帮助读者全面掌握Java编程技术的教材,结合源码进行讲解,适合从初学者到有一定经验的开发者阅读。这本书分为入门、进阶和应用实例三个部分,由人民邮电出版社出版,为学习Java语言提供...
《深入浅出Java2源代码》是一本专为Java初学者和进阶者设计的教材,旨在通过深入解析Java2的源代码,帮助读者更好地理解并掌握这门强大的编程语言。光盘中包含的源代码是书中实例和讲解的重要组成部分,它们提供了...
本精讲将深入浅出地探讨Java的基础知识,旨在为初学者提供一个全面且易理解的学习路径。 1. **Java简介**:Java是由Sun Microsystems(现为Oracle Corporation)于1995年发布的,它的设计目标是“一次编写,到处...
《深入浅出Java语言程序设计》是一本专为学习和理解Java编程语言而编写的教材。这本书的内容丰富,涵盖了从基础语法到高级特性的全面解析,旨在帮助读者深入理解Java编程的核心概念和技术。 首先,Java作为一门面向...
《深入浅出Java语言程序设计》是一本专为学习和理解Java编程语言而设计的教材。这本书涵盖了从基础到高级的Java编程概念,旨在帮助读者深入理解Java的各个方面,从而能够熟练地进行软件开发。 首先,Java语言是面向...