LinkedHashMultimap slow on removeAll(key) when only one key in map

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Run the following code:

Multimap<Integer, Integer> map = LinkedHashMultimap.create();
Random random = new Random();
Integer key = 10;
for (int i = 0; i < 20000; i++)
   map.put(key, random.nextInt());

//map.put(2, 2);
long start = System.currentTimeMillis();
map.removeAll(key);
System.out.println("Time is " + (System.currentTimeMillis() - start));

2. Uncomment line //map.put(2,2) and run again

What is the expected output? What do you see instead?

removeAll(key) is slower when the map contains only 1 key than when the map 
contains more keys.

What version of the product are you using? On what operating system?
google collection 1.0, ubuntu 10.04

Please provide any additional information below.
LinkedHashMultimap$SetDecorator.clear calls 
LinkedHashSet.removeAll(Collection<?> c) with an ArrayList as argument.

When the map has only one key, removeAll will perform a contains(Object o) on 
the ArrayList for all the values corresponding to the key.

Original issue reported on code.google.com by gabi.kaltman@gmail.com on 15 Jun 2010 at 1:24

[GoogleCodeExporter]

Original comment by kevinb@google.com on 30 Jul 2010 at 3:56

• Removed labels: Priority-Medium

[GoogleCodeExporter]

Thanks for pointing out this problem.

I fixed it in the Google code base. The fix will be migrated to Guava soon.

Original comment by jared.l....@gmail.com on 24 Aug 2010 at 7:31

• Changed state: Fixed

[GoogleCodeExporter]

Original comment by kevinb@google.com on 18 Jul 2011 at 3:33

• Added labels: Milestone-Release07

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:15

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:10

• Added labels: Restrict-AddIssueComment-Commit