HashMap计数方法优化

冷不防 2024-02-26 05:42 91阅读 0赞

大家可能经常会用HashMap来计算数据库或文本中某些特定内容出现的频率，这篇文章比较了三种HashMap计数器的实现方法，大家可做个参考。

1、首先介绍最基础的一种实现方式，代码如下

String s = "one two three two three three";
    String[] sArr = s.split(" ");
     
    //naive approach	 
    HashMap<String, Integer> counter = new HashMap<String, Integer>();
     
    for (String a : sArr) {
    	if (counter.containsKey(a)) {
    		int oldValue = counter.get(a);
    		counter.put(a, oldValue + 1);
    	} else {
    		counter.put(a, 1);
    	}
    }

这种实现方法中，每次循环遍历都要检查key存在与否，不存在表明第一次出现，设置对应的value值为1，如果存在，则给value值加1。这种方法简单而直观，但它并不是一个很好的实现方式，因为它没有考虑到以下两种情况所造成的效率不高的问题：

> 1、1 当Key存在的时候，方法containsKey()和方法get()会对map循环两次
> 
> 1、2 因为Integer类型是不可变的，所以每次给value值加1操作的时候都会创建一个新的Integer对象
> 
>   
>

2、较好一点的一个实现方式，解决了上述Integer类型是不可变的问题

很显然，为了不去创建很多很多的Integer对象，我们需要一个可变的Integer，实现类代码如下：

class MutableInteger {
     
    	private int val;
     
    	public MutableInteger(int val) {
    		this.val = val;
    	}
     
    	public int get() {
    		return val;
    	}
     
    	public void set(int val) {
    		this.val = val;
    	}
     
    	//used to print value convinently
    	public String toString(){
    		return Integer.toString(val);
    	}
    }

这样我们的代码就可以优化为：

HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();	
     
    for (String a : sArr) {
    	if (newCounter.containsKey(a)) {
    		MutableInteger oldValue = newCounter.get(a);
    		oldValue.set(oldValue.get() + 1);
    	} else {
    		newCounter.put(a, new MutableInteger(1));
    	}
    }

因为不需要额外的再去创建很多的Integer对象，所以较第一种方法要好一些，但是key存在时依然循环遍历两次。所以我们需要进一步的进行优化。

3、最有效的实现方式

HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
     
    for (String a : sArr) {
    	MutableInteger initValue = new MutableInteger(1);
    	MutableInteger oldValue = efficientCounter.put(a, initValue);
     
    	if(oldValue != null){
    		initValue.set(oldValue.get() + 1);
    	}
    }

因为HashMap.put(key, value)这个方法返回的是key的当前值，即当前key对应的value，所以我们可以利用value的索引来对其进行加1操作，一次搞定，不必在去查找浪费性能！

原文链接:[http://iyuze.cn/blog/56.html][http_iyuze.cn_blog_56.html]

[http_iyuze.cn_blog_56.html]: http://iyuze.cn/blog/56.html