在 Java 中增加 Map 值的最有效方法
https://stackoverflow.com/questions/81346
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我希望这个问题对于这个论坛来说不会被认为太基本，但我们拭目以待。我想知道如何重构一些多次运行的代码以获得更好的性能。
假设我正在使用 Map（可能是 HashMap）创建一个词频列表，其中每个键都是一个字符串，其中包含正在计数的单词，值是一个整数，每次找到单词的标记时都会递增。
在 Perl 中，增加这样的值非常简单：
$map{$word}++;
但在 Java 中，情况要复杂得多。这是我目前正在做的方式：
int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);
这当然依赖于较新 Java 版本中的自动装箱功能。我想知道您是否可以建议一种更有效的方法来增加这样的值。是否有更好的性能理由来避免使用集合框架并使用其他框架？
更新：我已经对几个答案进行了测试。见下文。
解决方案
一些测试结果
我已经得到了这个问题的很多好的答案——谢谢大家——所以我决定进行一些测试并找出哪种方法实际上是最快的。我测试的五种方法是：
- 我在中介绍的“ContainsKey”方法 问题
- Aleksandar Dimitrov 建议的“TestForNull”方法
- Hank Gay 建议的“AtomicLong”方法
- jrudolph建议的“Trove”方法
- phax.myopenid.com 建议的“MutableInt”方法
方法
这就是我所做的......
- 创建了五个相同的类，除了下面所示的差异之外。每个类都必须执行我所呈现的场景的典型操作：打开一个 10MB 的文件并读入，然后对文件中的所有单词标记执行频率计数。由于这平均只花费 3 秒，因此我让它执行频率计数（而不是 I/O）10 次。
- 对 10 次迭代的循环进行计时，但是 不是I/O操作 并记录了所花费的总时间（以时钟秒为单位），主要使用 Java Cookbook 中 Ian Darwin 的方法.
- 连续进行所有五次测试，然后再进行三次。
- 对每种方法的四个结果进行平均。
结果
我将首先向感兴趣的人展示结果和下面的代码。
这 包含键 正如预期的那样，该方法是最慢的，因此我将给出每种方法的速度与该方法的速度的比较。
- 包含密钥： 30.654 秒（基线）
- 原子长： 29.780 秒（快 1.03 倍）
- 测试为空： 28.804 秒（快 1.06 倍）
- 宝藏： 26.313 秒（快 1.16 倍）
- 可变整数： 25.747 秒（快 1.19 倍）
结论
看来只有 MutableInt 方法和 Trove 方法明显更快，因为只有它们的性能提升超过 10%。然而，如果线程是一个问题，AtomicLong 可能比其他的更有吸引力（我不太确定）。我还运行了 TestForNull final 变量，但差异可以忽略不计。
请注意，我没有分析不同场景下的内存使用情况。我很高兴听到任何人对 MutableInt 和 Trove 方法如何影响内存使用有深入的见解。
就我个人而言，我发现 MutableInt 方法最有吸引力，因为它不需要加载任何第三方类。因此，除非我发现它存在问题，否则我最有可能采用这种方式。
代码
这是每个方法的关键代码。
包含键
import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);
空值测试
import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
freq.put(word, 1);
}
else {
freq.put(word, count + 1);
}
原子长
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map =
new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();
宝藏
import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);
可变整数
import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
int value = 1; // note that we start at 1 since we're counting
public void increment () { ++value; }
public int get () { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
freq.put(word, new MutableInt());
}
else {
count.increment();
}
其他提示
好吧，可能是一个老问题了，但是 Java 8 有一个更短的方法：
Map.merge(key, 1, Integer::sum)
它能做什么 ：如果 钥匙 不存在，放入 1 作为值，否则 总和 1 到链接到的值 钥匙。更多信息 这里
2016年的一点研究： https://github.com/leventov/java-word-count, 基准源代码
每种方法的最佳结果（越小越好）：
time, ms
kolobokeCompile 18.8
koloboke 19.8
trove 20.8
fastutil 22.7
mutableInt 24.3
atomicInteger 25.3
eclipse 26.9
hashMap 28.0
hppc 33.6
hppcRt 36.5
时间\空间结果：
@汉克·盖伊
作为我自己的（相当无用的）评论的后续：Trove 看起来是个不错的选择。如果出于某种原因您想坚持使用标准 JDK， 并发映射 和 原子长 可以使代码成为 微小的 好一点，不过YMMV。
final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>();
map.putIfAbsent("foo", new AtomicLong(0));
map.get("foo").incrementAndGet();
会离开 1 作为地图中的值 foo. 。实际上，这种方法所推荐的只是增加了对线程的友好性。
您应该意识到您最初的尝试
int count = map.containsKey(word) ? map.get(word) : 0;
包含地图上两个潜在昂贵的操作，即 containsKey 和 get. 。前者执行的操作可能与后者非常相似，因此您正在做相同的工作 两次!
如果你查看 Map 的 API， get 操作通常会返回 null 当地图不包含请求的元素时。
请注意，这将产生类似的解决方案
map.put( key, map.get(key) + 1 );
危险，因为它可能会产生 NullPointerExceptions。您应该检查 null 第一的。
另请注意, ，这非常重要，即 HashMaps 能 包含 nulls 根据定义。所以不是每个都返回 null 说“不存在这样的元素”。在这方面， containsKey 表现 不同地 从 get 实际上告诉你 无论 有这样一个元素。详情请参阅API。
但是，对于您的情况，您可能不想区分存储的 null 和“noSuchElement”。如果你不想允许 null你可能更喜欢 Hashtable. 。使用其他答案中已经提出的包装器库可能是手动处理的更好解决方案，具体取决于应用程序的复杂性。
要完成答案（由于编辑功能，我一开始忘记了输入！），最好的本地完成方法是 get 变成一个 final 变量，检查 null 和 put 它回来了 1. 。该变量应该是 final 因为无论如何它都是不可变的。编译器可能不需要这个提示，但这样更清晰。
final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
map.put(i + 1);
} else {
// do something
}
如果你不想依赖自动装箱，你应该这样说 map.put(new Integer(1 + i.getValue())); 反而。
Map<String, Integer> map = new HashMap<>();
String key = "a random key";
int count = map.getOrDefault(key, 0);
map.put(key, count + 1);
这就是使用简单代码增加值的方法。
益处：
- 不为 mutable int 创建另一个类
- 短代码
- 容易明白
- 无空指针异常
另一种方法是使用合并方法，但这对于仅仅增加一个值来说太多了。
map.merge(key, 1, (a,b) -> a+b);
建议：在大多数情况下，您应该更关心代码的可读性，而不是很少的性能提升。
另一种方法是创建一个可变整数：
class MutableInt {
int value = 0;
public void inc () { ++value; }
public int get () { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt> ();
MutableInt value = map.get (key);
if (value == null) {
value = new MutableInt ();
map.put (key, value);
} else {
value.inc ();
}
当然，这意味着创建一个额外的对象，但与创建 Integer （即使使用 Integer.valueOf ）相比，开销不应该那么多。
您可以利用 计算如果不存在 中的方法 Map 中提供的接口 爪哇8.
final Map<String,AtomicLong> map = new ConcurrentHashMap<>();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet();
map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1]
方法 computeIfAbsent 检查指定的键是否已与值关联？如果没有关联值，则它尝试使用给定的映射函数计算其值。在任何情况下，它都会返回与指定键关联的当前（现有的或计算的）值，如果计算的值为 null，则返回 null。
附带说明一下，如果您遇到多个线程更新共同总和的情况，您可以看看 长加法器 在高竞争情况下，该类的预期吞吐量明显高于 AtomicLong, ，以更高的空间消耗为代价。
内存循环在这里可能是一个问题，因为大于或等于 128 的 int 的每次装箱都会导致对象分配（请参阅 Integer.valueOf(int)）。尽管垃圾收集器非常有效地处理短期对象，但性能会受到一定程度的影响。
如果您知道增量的数量将大大超过键的数量（在本例中=单词），请考虑使用 int 持有者。Phax 已经为此提供了代码。又是这样，有两个更改（持有者类设为静态且初始值设置为 1）：
static class MutableInt {
int value = 1;
void inc() { ++value; }
int get() { return value; }
}
...
Map<String,MutableInt> map = new HashMap<String,MutableInt>();
MutableInt value = map.get(key);
if (value == null) {
value = new MutableInt();
map.put(key, value);
} else {
value.inc();
}
如果您需要极致的性能，请寻找直接针对原始值类型定制的 Map 实现。尤鲁道夫提到 GNU 宝库.
顺便说一下，这个主题的一个很好的搜索词是“直方图”。
与调用 containsKey() 相比，调用 map.get 并检查返回值是否为 null 会更快。
Integer count = map.get(word);
if(count == null){
count = 0;
}
map.put(word, count + 1);
你确定这是一个瓶颈吗？你做过性能分析吗？
尝试使用 NetBeans 分析器（它是免费的，内置于 NB 6.1 中）来查看热点。
最后，JVM 升级（例如从 1.5 到 1.6）通常是一种廉价的性能提升器。即使内部版本号的升级也可以提供良好的性能提升。如果您在 Windows 上运行并且这是服务器类应用程序，请在命令行上使用 -server 来使用服务器热点 JVM。在 Linux 和 Solaris 机器上，这是自动检测到的。
有几种方法：
使用 Bag 算法，例如 Google Collections 中包含的集合。
创建可以在 Map 中使用的可变容器：
class My{
String word;
int count;
}
并使用 put("word", new My("Word") );然后你可以检查它是否存在并在添加时递增。
避免使用列表滚动您自己的解决方案，因为如果您进行内循环搜索和排序，您的性能将会很差。第一个 HashMap 解决方案实际上相当快，但像 Google Collections 中找到的那样的解决方案可能更好。
使用 Google Collections 计算单词数，如下所示：
HashMultiset s = new HashMultiset();
s.add("word");
s.add("word");
System.out.println(""+s.count("word") );
使用 HashMultiset 非常优雅，因为 bag-algorithm 正是您在计算单词时所需要的。
我认为您的解决方案将是标准方法，但是 - 正如您自己所指出的 - 这可能不是最快的方法。
你可以看看 GNU 宝库. 。这是一个包含各种快速原始集合的库。你的例子将使用 TObjectIntHashMap 它有一个方法 adjustmentOrPutValue ，它完全可以满足您的需求。
MutableInt 方法的一个变体是使用单元素 int 数组，如果有点 hack，可能会更快：
Map<String,int[]> map = new HashMap<String,int[]>();
...
int[] value = map.get(key);
if (value == null)
map.put(key, new int[]{1} );
else
++value[0];
如果您可以使用此变体重新运行性能测试，那将会很有趣。这可能是最快的。
编辑：上面的模式对我来说效果很好，但最终我改为使用 Trove 的集合来减少我正在创建的一些非常大的地图中的内存大小 - 而且作为奖励，它也更快。
一个非常好的功能是 TObjectIntHashMap 类有一个 adjustOrPutValue 调用它，根据该键是否已经有一个值，将放置一个初始值或增加现有值。这非常适合增量：
TObjectIntHashMap<String> map = new TObjectIntHashMap<String>();
...
map.adjustOrPutValue(key, 1, 1);
谷歌集合 HashMultiset ：
- 使用起来非常优雅
- 但消耗CPU和内存
最好是有这样的方法： Entry<K,V> getOrPut(K); （优雅，成本低）
这样的方法只能计算一次哈希和索引，然后我们可以通过条目（替换或更新值）来完成我们想要的工作。
更优雅：
- 采取一个 HashSet<Entry>
- 扩展它，以便 get(K) 如果需要，添加一个新条目
- 条目可以是您自己的对象。
--> (new MyHashSet()).get(k).increment();
“put”需要“get”（以确保没有重复的键）。
所以直接做一个“put”，
如果有先前的值，则进行加法：
Map map = new HashMap ();
MutableInt newValue = new MutableInt (1); // default = inc
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.add(oldValue); // old + inc
}
如果计数从 0 开始，则加 1：（或任何其他值......）
Map map = new HashMap ();
MutableInt newValue = new MutableInt (0); // default
MutableInt oldValue = map.put (key, newValue);
if (oldValue != null) {
newValue.setValue(oldValue + 1); // old + inc
}
注意 ： 这段代码不是线程安全的。使用它来构建然后使用地图，而不是同时更新它。
优化 ： 在一个循环中，保留旧值成为下一个循环的新值。
Map map = new HashMap ();
final int defaut = 0;
final int inc = 1;
MutableInt oldValue = new MutableInt (default);
while(true) {
MutableInt newValue = oldValue;
oldValue = map.put (key, newValue); // insert or...
if (oldValue != null) {
newValue.setValue(oldValue + inc); // ...update
oldValue.setValue(default); // reuse
} else
oldValue = new MutableInt (default); // renew
}
}
我将使用 Apache Collections Lazy Map（将值初始化为 0）并使用 Apache Lang 中的 MutableIntegers 作为该映射中的值。
最大的成本是必须用您的方法搜索地图两次。在我这里你只需要做一次。只需获取该值（如果不存在，它将被初始化）并递增它。
这 函数式Java 图书馆的 TreeMap 数据结构有一个 update 最新trunk头中的方法：
public TreeMap<K, V> update(final K k, final F<V, V> f)
用法示例：
import static fj.data.TreeMap.empty;
import static fj.function.Integers.add;
import static fj.pre.Ord.stringOrd;
import fj.data.TreeMap;
public class TreeMap_Update
{public static void main(String[] a)
{TreeMap<String, Integer> map = empty(stringOrd);
map = map.set("foo", 1);
map = map.update("foo", add.f(1));
System.out.println(map.get("foo").some());}}
该程序打印“2”。
@Vilmantas Baranauskas：关于这个答案，如果我有代表点，我会发表评论，但我没有。我想指出的是，那里定义的 Counter 类不是线程安全的，因为仅同步 inc() 而不同步 value() 是不够的。除非与更新建立了发生之前关系，否则调用 value() 的其他线程不能保证看到该值。
我不知道它的效率如何，但下面的代码也可以工作。您需要定义一个 BiFunction 一开始。另外，使用此方法您可以实现的不仅仅是增量。
public static Map<String, Integer> strInt = new HashMap<String, Integer>();
public static void main(String[] args) {
BiFunction<Integer, Integer, Integer> bi = (x,y) -> {
if(x == null)
return y;
return x+y;
};
strInt.put("abc", 0);
strInt.merge("abc", 1, bi);
strInt.merge("abc", 1, bi);
strInt.merge("abc", 1, bi);
strInt.merge("abcd", 1, bi);
System.out.println(strInt.get("abc"));
System.out.println(strInt.get("abcd"));
}
输出是
3
1
如果您正在使用 日食系列, ，你可以使用 HashBag. 。就内存使用而言，这将是最有效的方法，并且在执行速度方面也将表现良好。
HashBag 由一个支持 MutableObjectIntMap 它存储原始整数而不是 Counter 对象。这减少了内存开销并提高了执行速度。
HashBag 提供您需要的 API，因为它是 Collection 它还允许您查询某个项目出现的次数。
这是一个来自 Eclipse Collection 卡塔.
MutableBag<String> bag =
HashBag.newBagWith("one", "two", "two", "three", "three", "three");
Assert.assertEquals(3, bag.occurrencesOf("three"));
bag.add("one");
Assert.assertEquals(2, bag.occurrencesOf("one"));
bag.addOccurrences("one", 4);
Assert.assertEquals(6, bag.occurrencesOf("one"));
笔记： 我是 Eclipse Collections 的提交者。
很简单，使用内置函数即可 Map.java 如下
map.put(key, map.getOrDefault(key, 0) + 1);
由于很多人在 Java 主题中搜索 Groovy 答案，因此您可以在 Groovy 中执行以下操作：
dev map = new HashMap<String, Integer>()
map.put("key1", 3)
map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}
希望我能正确理解你的问题，我是从 Python 转向 Java 的，所以我可以理解你的挣扎。
如果你有
map.put(key, 1)
你会做
map.put(key, map.get(key) + 1)
希望这可以帮助！
