HashMap中的几个重要变量
默认初始容量,必须是2的n次方
1
|
static final int DEFAULT_INITIAL_CAPACITY = 16 ;
|
最大容量,当通过构造方法传入的容量比它还大时,就用这个最大容量,必须是2的n次方
1
|
static final int MAXIMUM_CAPACITY = 1 << 30 ;
|
默认负载因子
1
|
static final float DEFAULT_LOAD_FACTOR = 0 .75f;
|
用来存储键值对,可以看到键值对都是存储在Entry中的
1
2
3
4
|
transient Entry<K,V>[] table;
//capacity * load factor,超过这个数就会进行再哈希
int threshold;
|
HashMap中的元素是用名为table的Entry数组来保存的,默认大小是16
- capacity:数组的容量
- load_factor:负载因子
- threshold:实际能承载的容量,等于上面两个相乘,当size大于threshold时,就会进行rehash
jdk7中在面对key为String的时候采用了区别对待,会有alternative hashing,但是这个在jdk8中已经被删除了
存储结构
Entry是一个链表结构,不仅包含key和value,还有可以指向下一个的next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry( int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
...
|
put方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public V put(K key, V value) {
if (key == null )
return putForNullKey(value);
int hash = hash(key);
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 ;
}
|
首先通过hash方法对hashcode进行处理:
1
2
3
4
5
6
7
|
final int hash(Object k) {
int h = 0 ;
h ^= k.hashCode();
h ^= (h >>> 20 ) ^ (h >>> 12 );
return h ^ (h >>> 7 ) ^ (h >>> 4 );
}
|
可以看到只是在key的hashcode值上做了一些处理,通过hash计算出来的值将会使用indexFor方法找到它应该所在的table下标:
1
2
3
|
static int indexFor( int h, int length) {
return h & (length- 1 );
}
|
这个方法其实相当于对table.length
取模。
当需要插入的key为null时,调用putForNullKey方法处理:
1
2
3
4
5
6
7
8
9
10
11
12
13
|
private V putForNullKey(V value) {
for (Entry<K,V> e = table[ 0 ]; e != null ; e = e.next) {
if (e.key == null ) {
V oldValue = e.value;
e.value = value;
e.recordAccess( this );
return oldValue;
}
}
modCount++;
addEntry( 0 , null , value, 0 );
return null ;
}
|
putForNullKey方法只从table[0]
这个位置开始遍历,因为key为null只放在table中的第一个位置,下标为0,在遍历中如果发现已经有key为null了,则替换新value,返回旧value,结束;如果还没有key为null,调用addEntry方法增加一个Entry:
1
2
3
4
5
6
7
8
9
|
void addEntry( int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && ( null != table[bucketIndex])) {
resize( 2 * table.length);
hash = ( null != key) ? hash(key) : 0 ;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
|
可以看到jdk7中resize的条件已经发生改变了,只有当 size>=threshold
并且 table中的那个槽中已经有Entry时,才会发生resize。即有可能虽然size>=threshold
,但是必须等到每个槽都至少有一个Entry时,才会扩容。还有注意每次resize都会扩大一倍容量
1
2
3
4
5
|
void createEntry( int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
|
最后看createEntry,它先保存这个桶中的第一个Entry,创建新的Entry放入第一个位置,将原来的Entry接在后面。这里采用的是头插法插入元素。
get方法
其实get方法和put方法如出一辙,怎么放的怎么拿
1
2
3
4
5
6
7
|
public V get(Object key) {
if (key == null )
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
|
key为null时,还是去table[0]
去取:
1
2
3
4
5
6
7
|
private V getForNullKey() {
for (Entry<K,V> e = table[ 0 ]; e != null ; e = e.next) {
if (e.key == null )
return e.value;
}
return null ;
}
|
否则调用getEntry方法:
1
2
3
4
5
6
7
8
9
10
11
12
|
final Entry<K,V> getEntry(Object key) {
int hash = (key == null ) ? 0 : hash(key);
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 != null && key.equals(k))))
return e;
}
return null ;
}
|
这个方法也是通过key的hashcode计算出它应该所在的下标,再遍历这个下标的Entry链,如果key的内存地址相等(即同一个引用)或者equals相等,则说明找到了
hash的原则
A、等幂性。不管执行多少次获取Hash值的操作,只要对象不变,那么Hash值是固定的。如果第一次取跟第N次取不一样,那就用起来很麻烦.
B、对等性。若两个对象equal方法返回为true,则其hash值也应该是一样的。举例说明:若你将objA作为key存入HashMap中,然后new了一个objB。在你看来objB和objA是一个东西(因为他们equal),但是使用objB到hashMap中却取不出来东西。
C、互异性。若两个对象equal方法返回为false,hash值有可能相同,但最好是不同的,这个不是必须的,只是这样做会提高hash类操作的性能(碰撞几率低)。
解决hash碰撞的方法:
- 开放地址法
- 链地址法
hashmap采用的就是链地址法,这种方法好处是无堆积现象,但是next指针会占用额外空间
和jdk8中的HashMap区别
在jdk8中,仍然会根据key.hashCode()
计算出hash值,再通过这个hash值去定位这个key,但是不同的是,当发生冲突时,会采用链表和红黑树两种方法去处理,当结点个数较少时用链表(用Node存储),个数较多时用红黑树(用TreeNode存储),同时结点也不叫Entry了,而是分成了Node和TreeNode。再最坏的情况下,链表查找的时间复杂度为O(n),而红黑树一直是O(logn),这样会提高HashMap的效率。jdk8中的HashMap中定义了一个变量TREEIFY_THRESHOLD,当节点个数>= TREEIFY_THRESHOLD - 1时,HashMap将采用红黑树存储
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作能带来一定的帮助,如果有疑问大家可以留言交流。