—HashMap—
优点：超级快速的查询速度，时间复杂度可以达到O（1）的数据结构非HashMap莫属。动态的可变长存储数据（相对于数组而言）。
缺点：需要额外计算一次hash值，如果处理不当会占用额外的空间。
—HashMap如何使用—
平时我们使用hashmap如下
|
1
2
3
|
Map<Integer,String> maps=new HashMap<Integer,String>();
maps.put(1, "a");
maps.put(2, "b");
|
上面代码新建了一个HashMap并且插入了两个数据，这里不接受基本数据类型来做K,V
如果这么写的话，就会出问题了：
|
1
|
Map<int,double> maps=new HashMap<int,double>();
|
我们为什么要这样使用呢？请看源码：
|
1
2
3
|
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
|
这是HashMap实现类的定义。
—HashMap是一个动态变长的数据结构—
在使用HashMap的时候，为了提高执行效率，我们往往会设置HashMap初始化容量：
|
1
|
Map<String,String> rm=new HashMap<String,String>(2)
|
或者使用guava的工具类Maps，可以很方便的创建一个集合，并且，带上合适的大小初始化值。
|
1
|
Map<String, Object> map = Maps.newHashMapWithExpectedSize(7);
|
那么为什么要这样使用呢？我们来看他们的源码构造函数。
未带参的构造函数：
|
1
2
3
4
5
6
|
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
|
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
|
1
2
3
4
5
6
7
8
9
10
|
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
|
名词解释：
|
1
2
3
|
DEFAULT_LOAD_FACTOR //默认加载因子，如果不制定的话是0.75
DEFAULT_INITIAL_CAPACITY //默认初始化容量，默认是16
threshold //阈（yu）值 根据加载因子和初始化容量计算得出 ，<span style="color: rgb(54, 46, 43); font-family: "microsoft yahei";">threshold表示当HashMap的size大于threshold时会执行resize操作。
|
因此我们知道了，如果我们调用无参数的构造方法的话，我们将得到一个16容量的数组。
所以问题就来了：如果初始容量不够怎么办？
数组是定长的，如何用一个定长的数据来表示一个不定长的数据呢，答案就是找一个更长的，但是在resize的时候是很降低效率的。所以我们建议HashMap的初始化的时候要给一个靠谱的容量大小。
—HashMap的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) //键为空的情况，HashMap和HashTable的一个区别
return putForNullKey(value);
int hash = hash(key.hashCode()); //根据键的hashCode算出hash值
int i = indexFor(hash, table.length); //根据hash值算出究竟该放入哪个数组下标中
for (Entry<K,V> e = table[i]; e != null; e = e.next) {//整个for循环实现了如果存在K那么就替换V
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;
}
|
如果插入的数据超过现有容量就会执行
|
1
|
addEntry(hash, key, value, i);
|
|
1
2
3
4
5
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)
<span style="color:#ff0000;"><strong> resize(2 * table.length);
}
|
这里显示了如果当前 size++ >threshold 的话那么就会扩展当前的size的两倍，执行resize（2*table.length）,那么他们是如何扩展的呢？
|
1
2
3
4
5
6
7
8
9
10
11
12
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]; <span style="color: rgb(51, 51, 51); font-family: Arial;">new 一个新的数组，</span>
<strong> <span style="color:#ff0000;">transfer(newTable);</span> </strong> //将就数组转移到新的数组中
table = newTable;
threshold = (int)(newCapacity * loadFactor); //重新计算容量
}
|
对于转移数组transfer是如何转移的呢？
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 = <strong><span style="color:#ff0000;">indexFor(e.hash, newCapacity); //根据hash值个容量重新计算下标</span></strong>
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
|
—hashmap扩容额外执行次数—
因此如果我们要添加一个1000个元素的hashMap，如果我们用默认值那么我么需要额外的计算多少次呢
当大于16*0.75=12的时候，需要从新计算12次
当大于16*2*0.75=24的时候，需要额外计算24次
……
当大于16*n*0.75=768的时候，需要额外计算768次
所以我们总共在扩充过程中额外计算12+24+48+……+768次
因此强力建议我们在项目中如果知道范围的情况下，我们应该手动指定初始大小像这样：
|
1
|
Map<Integer,String> maps=new HashMap<Integer,String>(1000);
|
总结：这就是为什么当hashmap使用过程中如果超出 初始容量后他的执行效率严重下降的原因。
以上就是本文关于Java源码角度分析HashMap用法的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
原文链接：http://blog.csdn.net/lee_sire/article/details/53424735