java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 程序设计语言和 Java 平台(即 JavaEE(j2ee), JavaME(j2me), JavaSE(j2se))的总称。
这篇文章主要介绍了 java HashMap 内部实现原理详解的相关资料, 需要的朋友可以参考下
详解 HashMap 内部实现原理
内部数据结构
- static class Entry<K,V> implements Map.Entry<K,V> {
- final K key;
- V value;
- Entry<K,V> next;
- int hash;
从上面的数据结构定义可以看出,HashMap 存元素的是一组键值对的链表,以什么形式存储呢
- transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
可以看出,是以数组形式储存,好的,现在我们知道,HashMap 是以数组形式存储,每个数组里面是一个键值对,这个键值对还可以链接到下个键值对。如下图所示:
hashmap 的添加
- public V put(K key, V value) {
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
- 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;
- }
这里可以看出,hashmap 的添加,首先根据一个 entry 的 hash 属性去查找相应的 table 元素 i,然后看这个位置是否有元素存在,如果没有,直接放入,如果有,遍历此次链表,加到表尾
删除
- final Entry < K,
- V > removeEntryForKey(Object key) {
- if (size == 0) {
- return null;
- }
- int hash = (key == null) ? 0 : hash(key);
- int i = indexFor(hash, table.length);
- Entry < K,
- V > prev = table[i];
- Entry < K,
- V > e = prev;
- while (e != null) {
- Entry < K,
- V > next = e.next;
- Object k;
- if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
- modCount++;
- size--;
- if (prev == e) table[i] = next;
- else prev.next = next;
- e.recordRemoval(this);
- return e;
- }
- prev = e;
- e = next;
- }
- return e;
- }
删除的话,还是先根据 hash 在 table 数组中查找,然后再根据 equals 在链表中进行查找,这个也是为什么 hashmap 和 hashset 等以 hash 方式进行存储的数据结构要求实现两个方法 hashcode 和 equalsd 的原因
学过 hash 的人都知道,hash 表的性能和 hash 冲突的发生次数有很大关系,但有不能申请过长的 table 表浪费空间,所以这里有了我们的 resize 函数
扩容机制
- 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, initHashSeedAsNeeded(newCapacity));
- table = newTable;
- threshold = (int) Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
- }
这个方法会在 put 的时候调用, 上面 put 的时候先调用 addEntry(hash, key, value, i); 方法,然后看 addEntry 方法
- 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);
- }
上面可以看出那么 HashMap 当 HashMap 中的元素个数超过数组大小 *loadFactor 时,就会进行数组扩容,loadFactor 的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当 HashMap 中元素个数超过 16*0.75=12 的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位 置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能。
来源: http://www.phperz.com/article/17/1221/358630.html