在java中高效的计数器

时间:2022-10-03 16:19:16

在编程中,经常会用到HashMap作为计数器,本文简单介绍三种实现方式

第一种,最直观的计数器。

 

public void naiveCounter(String sArr[]) {
        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);
            }
        }
    }

在这种方式中,每次循环都去检查Map中是否包含Key,如果包含则将原值+1再保存,如果不存在,则直接保存1.这种方式是最简单直接的一种方式,但是并不是最有效的方式,其低效的原因:

 

1、如果已经存在某个key(a),containsKey()和get()方法会扫描Map两次

2、由于Integer是不可变对象,因此每次循环,都会创建一个新的对象放到Map中。

第二种,比较好的计数器

由于上述原因,自然可以想到创建一个可变的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;
        }

        public String toString() {
            return Integer.toString(val);
        }
    }

然后将上面的计数器优化一下,改成下面这张格式

 

 

public void betterCounter(String[] sArr) {
        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对象的问题,但是扫描两次Map,

其实在HashMap中,存在一个能够返回当前值的方法(HashMap.put(key,value)),

在上面的基础上,我们可以通过对原来的引用进行更新,而不必扫描两次Map

 

public void efficientCounter(String[] sArr) {
        HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
        for (String a : sArr) {
            MutableInteger initValue = new MutableInteger(1);
            MutableInteger oldValue = efficientCounter.put(a, initValue);
             //MutableInteger是可变的,此处只需判断之前是否为空,
             // 如果非空,则更新MutableInteger的引用即可
            if (oldValue != null) {
                initValue.set(oldValue.get() + 1);
            }
        }
    }


下面是经过500W次操作后,三者方法所消耗的时间

 

start test naiveCounter
end test naiveCounter,time is:5629


start test betterCounter
end test betterCounter,time is:5030


start test efficientCounter
end test efficientCounter,time is:4418

可以看出,最后一种确实是三种里面最高效的方式