Java源码角度分析HashMap用法

—hashmap—

优点：超级快速的查询速度，时间复杂度可以达到o（1）的数据结构非hashmap莫属。动态的可变长存储数据（相对于数组而言）。

缺点：需要额外计算一次hash值，如果处理不当会占用额外的空间。

—hashmap如何使用—

平时我们使用hashmap如下

map<integer,string> maps=new hashmap<integer,string>();   
maps.put(1, "a");   
maps.put(2, "b");

上面代码新建了一个hashmap并且插入了两个数据，这里不接受基本数据类型来做k,v

如果这么写的话，就会出问题了：

map<int,double> maps=new hashmap<int,double>();

我们为什么要这样使用呢？请看源码：

public class hashmap<k,v>  
  extends abstractmap<k,v>  
  implements map<k,v>, cloneable, serializable 

这是hashmap实现类的定义。

—hashmap是一个动态变长的数据结构—

在使用hashmap的时候，为了提高执行效率，我们往往会设置hashmap初始化容量：

map<string,string> rm=new hashmap<string,string>(2)

或者使用guava的工具类maps，可以很方便的创建一个集合，并且，带上合适的大小初始化值。

map<string, object> map = maps.newhashmapwithexpectedsize(7);

那么为什么要这样使用呢？我们来看他们的源码构造函数。

未带参的构造函数：

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

/** 
   * 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); 
  }

名词解释：

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方法—

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

如果插入的数据超过现有容量就会执行

addentry(hash, key, value, i);

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）,那么他们是如何扩展的呢？

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是如何转移的呢？

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次

因此强力建议我们在项目中如果知道范围的情况下，我们应该手动指定初始大小像这样：

map<integer,string> maps=new hashmap<integer,string>(1000);

总结：这就是为什么当hashmap使用过程中如果超出 初始容量后他的执行效率严重下降的原因。

以上就是本文关于java源码角度分析hashmap用法的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！