HashMap原理
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
...
}
既然是个数组,那么数组是要声明容量的,这个工作在初始化HashMap的时候完成 ,我们看默认的初始化方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
这里的容量定义为DEFAULT_INITAL_CAPACITY ,是个常量,默认值是16。也就是说你声明一个HashMap,默认给你的是16个桶来放Key(注意是key ,不是value,所以并不意味着初始的HashMap只能容纳16组Entry),当key超过16时就得扩容了。具体扩容方法,是超过threshhold后就会触发resize()重新hash。因此初始化HashMap时根据数据情况合理的设置容量是必要得。
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);
}
二、存取算法
具体来说就是常用的put(),get()方法的源码
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;
}
put一个值的时候首先会根据key的hashCode()方法计算hash值,然后会根据这个hash值计算entry数组(桶)的下标(i)在具体判断是否key 命中时,是根据 e.hash==hash&& ((k = e.key) == key || key.equals(k))) 这个表达式。从而我们知道,HashMap判断当前是否已经存储了一个值是根据key的hashCode() 和equal() 来判断的。所以如果要用自定义对象来作key,需要重写这两个方法,保证相同对象的一致性。
那么如果上面执行下来没有发现相同的key,这里有两种情况,一是没有桶,也就是entry数组没有位置。二是有桶(Hash命中)但是链表中找不到,这两种情况都可以通过addEntry(hash, key, value, i)这个方法把新值put进去。
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);
}
这个方法很短,但是完成了很多工作,一是new了一个entry, 二是监视当前的桶大小是否超过阈值,如果超过就进行扩容。这个地方其实容易迷糊,看起来似乎是new了一个Entry对象把老对象替换掉了。此时请记得,entry是一个链表,new的过程可能是新创建一个链表,也可能是在已有链表上添加一个节点。
put搞明白了,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;
}
其实完成的就是put前半段查找的过程。如果找不到,会返回null。
通过上面分析,HashMap是怎么存储与运作的应该知道个大概了。总体来说,我想有两个地方比较关键,一是对与容量(Capacity )的规划,二是hashCode()的实现。应用的得当应该会让HashMap效率提高不少档次。另外有一点,看源码就发现HashMap的方法都没有做synchronize,相比而言Hashtable实现原理基本类似,但是其存取方法都是synchronized, 因此hashMap非线程安全,但是相应的效率会比较高。
推荐阅读
-
PHP Curl多线程原理实例详解_PHP教程
-
Android的线程通信:消息机制原理(Message,Handler,MessageQueue,Looper),异步任务AsyncTask,使用JSON
-
理解Javascript_05_原型继承原理_javascript技巧
-
php图片加水印原理(超简单的实例代码)_php技巧
-
RabbitMQ与PHP(一)—— RabbitMQ的原理与操作示例
-
PHP strtotime函数用法、实现原理和源码分析_php技巧
-
怎么出错了呢?求原理
-
数据库字段复用的基本原理与示例
-
Oracle 并行原理深入解析及案例精粹
-
Base64编码原理分析与PHP实现_PHP教程_编程技术