面试-计数器相关

面试官问：

文件里有m个身份证号，统计每个身份证号出现的次数

回答：

使用hashMap实现，key作为身份证号
ContainsKey

Map<String, Integer> freq = new HashMap<String, Integer>();
public void incr (String word){
    int count = freq.containsKey(word) ? freq.get(word) : 0;
    freq.put(word, count + 1);
}

面试官问：

还能优化吗

回答：

TestForNull

Map<String, Integer> freq = new HashMap<String, Integer>();
public void incr (String word){
  Integer count = freq.get(word);
  if (count == null) {
      freq.put(word, 1);
  }
  else {
    freq.put(word, count + 1);
  }
}

减少调用containsKey方法的开销

面试官问：

如果是高并发情况呢

回答：

采用ConcurrentHashMap去做，线程安全的

面试官问：

高并发下HashMap有什么问题吗

回答：

并发情况下使用HashMap造成Race Condition，从而导致死循环，CPU占用率会达到100%
博文链接hashMap死循环

面试官问：

ok 用ConcurrentHashMap 实现下

回答：

ConcurrentMap <String, Integer> freq = new ConcurrentHashMap <String, Integer>();
public void incr (String word){
  Integer count = freq.get(word);
  if (count == null) {
      freq.put(word, 1);
  }
  else {
      freq.put(word, count + 1);
  }
}

面试官问：

确定能实现？

回答：

实现不了 put操作会覆盖，比如两个线程同时进来读到了都是4，那么都会put 5进去，
可以给方法加上synchronized锁

ConcurrentMap <String, Integer> freq = new ConcurrentHashMap <String, Integer>();
public synchronized void incr (String word){
  Integer count = freq.get(word);
  if (count == null) {
      freq.put(word, 1);
  }
  else {
      freq.put(word, count + 1);
  }
}

面试官问：

嗯嗯 加锁确实能实现，但是性能差点，能优化下吗

回答(当时回答的不好)：

能,采用cas方式

ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
public void incr (String word){
  map.putIfAbsent(word, new AtomicLong(0));
  map.get(word).incrementAndGet();
}

也可以采用 AtomicLongMap，AtomicLongMap是Google Guava项目的一个类，它是线程安全、支持并发访问的，通过CAS方式实现

AtomicLongMap<String> map = AtomicLongMap.create();
public void incr (String word){
   map.getAndIncrement(word);
}

延伸：

AtomicLong – 这组类使用CAS（比较并交换）处理器指令来更新计数器的值。听起来不错，真的是这样吗？是也不是。好的一面是它通过一个直接机器码指令设置值时，能够最小程度地影响其他线程的执行。坏的一面是如果它在与其他线程竞争设置值时失败了，它不得不再次尝试。在高竞争下，这将转化为一个自旋锁，线程不得不持续尝试设置值，无限循环直到成功。这可不是我们想要的方法。让我们进入Java 8的LongAdders