Java源码角度分析HashMap用法

发布于 2020-11-21|标签java
复制链接
摘记: —HashMap—优点:超级快速的查询速度,时间复杂度可以达到O(1)的数据结构非HashMap莫属。动态的可变长存储数据(相对于数组而言)。缺点:需要额外计算一次hash值,如果处理不当会占用额外的空间。—HashMap如何使用—平时我们使用hashmap如下 ```java Map< ..
—HashMap—优点:超级快速的查询速度,时间复杂度可以达到O(1)的数据结构非HashMap莫属。动态的可变长存储数据(相对于数组而言)。缺点:需要额外计算一次hash值,如果处理不当会占用额外的空间。—HashMap如何使用—平时我们使用hashmap如下 ```java Map maps=new HashMap(); maps.put(1, "a"); maps.put(2, "b"); ``` 上面代码新建了一个HashMap并且插入了两个数据,这里不接受基本数据类型来做K,V 如果这么写的话,就会出问题了: ```java Map maps=new HashMap(); ``` 我们为什么要这样使用呢?请看源码: ```java public class HashMap extends AbstractMap implements Map, Cloneable, Serializable ``` 这是HashMap实现类的定义。—HashMap是一个动态变长的数据结构—在使用HashMap的时候,为了提高执行效率,我们往往会设置HashMap初始化容量: ```java Map rm=new HashMap(2) ``` 或者使用guava的工具类Maps,可以很方便的创建一个集合,并且,带上合适的大小初始化值。 ```java Map map = Maps.newHashMapWithExpectedSize(7); ``` 那么为什么要这样使用呢?我们来看他们的源码构造函数。未带参的构造函数: ```java 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(); } ```java /** * Constructs an empty HashMap 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); } ``` 名词解释: ```java DEFAULT_LOAD_FACTOR //默认加载因子,如果不制定的话是0.75 DEFAULT_INITIAL_CAPACITY //默认初始化容量,默认是16 threshold //阈(yu)值 根据加载因子和初始化容量计算得出 ,threshold表示当HashMap的size大于threshold时会执行resize操作。 ``` 因此我们知道了,如果我们调用无参数的构造方法的话,我们将得到一个16容量的数组。所以问题就来了:如果初始容量不够怎么办?数组是定长的,如何用一个定长的数据来表示一个不定长的数据呢,答案就是找一个更长的,但是在resize的时候是很降低效率的。所以我们建议HashMap的初始化的时候要给一个靠谱的容量大小。—HashMap的Put方法— ```java 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 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; } ``` 如果插入的数据超过现有容量就会执行 ```java addEntry(hash, key, value, i); ``` ```java void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } ``` 这里显示了如果当前 size++ >threshold 的话那么就会扩展当前的size的两倍,执行resize(2*table.length),那么他们是如何扩展的呢? ```java 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]; new 一个新的数组, transfer(newTable); //将就数组转移到新的数组中 table = newTable; threshold = (int)(newCapacity * loadFactor); //重新计算容量 } ``` 对于转移数组transfer是如何转移的呢? ```java void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j e = src[j]; if (e != null) { src[j] = null; do { Entry next = e.next; int i = indexFor(e.hash, newCapacity); //根据hash值个容量重新计算下标 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次因此强力建议我们在项目中如果知道范围的情况下,我们应该手动指定初始大小像这样: ```java Map maps=new HashMap(1000); ``` 总结:这就是为什么当hashmap使用过程中如果超出 初始容量后他的执行效率严重下降的原因。 原文地址: http://blog.csdn.net/lee_sire/article/details/53424735
冀ICP备17029012号-4 | 版权所有©鲍亚龙 |免责声明  | GIF图库  | NUXT版