HashMap是java中相当重要的数据结构,使用HashMap的场景非常之多,因此,了解HashMap实现的过程和原理,是非常有必要的,在一些面试中也会经常被问到。好了,我们赶紧来研究java内部是怎么实现HashMap的吧!

首先,我们都知道,数组的元素查找的效率是不错的,但是涉及到插入操作和删除操作,效率低下,因为可能会涉及到后续元素位置的迁移。而另外一个数据结构链表则很好的解决了这个问题,插入和删除操作都只需要改变节点的指针就行,但是链表的检索的效率就很低了,试想一下,要检索的元素在链表的末尾,而我们只能从链表头开始走完整个链表,才能检索到这个元素。而Hash表能给我们带来高效查询,插入和删除。它是怎么做到的呢?

Hash表的实质是构造记录的存储位置和其对应的关键字之间的映射函数f,关于Hash函数的构造方法,主要有如下几种:

(1)直接定址法,取关键字的某个线性函数作为Hash函数即Hash(key) = a*key+b。这种方法很少使用,虽然不会发生冲突,但是当key非常多的时候,整张Hash表也会非常大,毕竟是一一映射的。

(2)平方取中法,将key的平方的中间几位数作为得到的Hash地址。

(3)除留余数法,将key除以某个数,得到的余数作为Hash地址。

还有一些方法我们在此就不说了。当多个关键字经过这个Hash函数的映射而得到同一个值的时候,就发生了Hash冲突。解决Hash冲突主要有两种方法:

(1)开放定址法:

HashMap的存储原理-LMLPHP

其中i=1,2,3。。。。,k(k<=m-1),H(key)为哈希函数,m为哈希表表长,di为增量序列,可能有下列2种情况:

当 di=1,2,3....,m-1时,称线性探测在散列;

当    HashMap的存储原理-LMLPHP时,称为二次探测再散列。

(2)链地址法:

即将所有关键字为同义词的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间[0,m-1]上,则设立一个指针型向量 ChainHash[m];

其每个分量的初始状态都是空指针。凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在列表中的插入位置可以在表头或表尾;也可以在中间,以保持同义词在同一线性表中按关键字有序。

例如:已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),则按哈希函数H(key)=key MOD 13 和链地址法处理冲突构造所得的哈希表,如下图所示:

HashMap的存储原理-LMLPHP

Java中的HashMap的基本结构就如上图所示,竖着看是一个数组,横着看就是多个链表。当新建一个HashMap的时候,就初始化了一个数组:

 /**
* The table, resized as necessary. Length MUST Always be a power of two.
*/ transient Entry[] table;

关于transient关键字,是为了使其修饰的对象不参与序列化,也就是说,这个对象无法被持久化,这里用这个关键字是有原因的,由于HashCode()方法是一个本地方法(由java调用本地的外部函数执行),所以不同的虚拟机,对于相同的hashCode 产生的 Code 值可能是不一样的,如果你使用默认的序列化,那么反序列化后,元素的位置和之前的是保持一致的,可是由于 hashCode 的值不一样了,那么定位函数 indexOf()返回的元素下标就会不同,这样不是我们所想要的结果.举个网上大神的例子:

向HashMap存一个entry, key为 字符串"STRING", 在第一个java程序里, "STRING"的hashcode()为1, 存入第1号bucket; 在第二个java程序里, "STRING"的hashcode()有可能就是2, 存入第2号bucket. 如果用默认的串行化(Entry[] table不用transient), 那么这个HashMap从第一个java程序里通过串行化导入第二个java程序后, 其内存分布是一样的,那么我取1号bucket能拿到“STRING”这个key,取2号bucket也能拿到相同的key,这是不合理的。

因此,HashMap这个entry数组是不可以串行化的。因此,HashMap自己实现了readObject和writeObject,在其中它只保存了bucket size,entry count(这两个其实不是必需的,但有助于提高效率)和所有的key/value(这个才是必须的)。

这就是数组内的链表:

 static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //持有的一个指向下一个元素的引用,构成链表。
....
}

下面让我们来看看Hash在put新元素时所做的操作:

 public V put(K key, V value) {   // HashMap允许存放null键和null值, 当key为null时,调用putForNullKey方法,将value放置在数组第一个位置。
if (key == null)
return putForNullKey(value); //null key 存放的总是数组的第一个元素中
int hash = hash(key.hashCode()); // 根据key的HashCode重新计算hash值
int i = indexFor(hash, table.length); //通过hash值算出在对应table中的索引(下标)。
for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 如果 i 索引处的 Entry 不为 null,通过循环不断遍历 e 元素的下一个元素
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果存在key相等的情形时,则用新的value值覆盖老的value的值
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++; // 如果i索引处的Entry为null,表明此处还没有Entry。
addEntry(hash, key, value, i); // 将key、value添加到i索引处。
return null;
}

怎么新加传进来的entry呢:

 void addEntry(int hash, K key, V value, int bucketIndex) {   // 获取指定 bucketIndex 索引处的 Entry,bucketIndex可以理解为存放的table中的index,当这个bucketIndex相同时,就是发生了Hash冲突,
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entry
4 if (size++ >= threshold) // 如果新加入后的大小超过了当前最大容量,则把 table 对象的长度扩充到原来的2倍。
resize(2 * table.length);
}

原来新加的entry都是加在了链表的头端。

在取Entry的时候就非常简单了,如果key等于null,直接取数组的第一个元素,如果不是,先计算出key的hashcode找到下标,再用key的equals方法判断是否相等,如果相等,则返回对应的entry,如果不相等,则返回null:

 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;
}

关于HashMap的存储原理就说到这里啦,有什么错误,请欢迎指正。

参考资料:http://zhangshixi.iteye.com/blog/672697

04-23 12:46