Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java	(revision 13120)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionItem.java	(revision 13121)
@@ -22,5 +22,5 @@
     private AutoCompletionPriority priority;
     /** the value of this item */
-    private String value;
+    private final String value;
 
     /**
@@ -79,8 +79,10 @@
      * @param value the value; must not be null
      * @throws IllegalArgumentException if value if null
+     * @deprecated value is now final, set it when constructing the object
      */
+    @Deprecated
     public void setValue(String value) {
         CheckParameterUtil.ensureParameterNotNull(value, "value");
-        this.value = value;
+        throw new UnsupportedOperationException("setValue() is no longer supported");
     }
 
Index: trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java	(revision 13120)
+++ trunk/src/org/openstreetmap/josm/data/tagging/ac/AutoCompletionSet.java	(revision 13121)
@@ -5,4 +5,5 @@
 import java.util.Objects;
 import java.util.Optional;
+import java.util.Set;
 import java.util.TreeSet;
 import java.util.stream.Collectors;
@@ -18,23 +19,47 @@
 public class AutoCompletionSet extends TreeSet<AutoCompletionItem> {
 
+    // Keep a separate tree set of values for determining fast if a value is present
+    private final Set<String> values = new TreeSet<>();
+
     @Override
     public boolean add(AutoCompletionItem e) {
         // Is there already an item for the value?
-        Optional<AutoCompletionItem> result = stream().filter(i -> i.getValue().equals(e.getValue())).findFirst();
-        if (result.isPresent()) {
-            AutoCompletionItem item = result.get();
-            // yes: merge priorities
-            AutoCompletionPriority newPriority = item.getPriority().mergeWith(e.getPriority());
-            // if needed, remove/re-add the updated item to maintain set ordering
-            if (!item.getPriority().equals(newPriority)) {
-                remove(item);
-                item.setPriority(newPriority);
-                return add(item);
+        String value = e.getValue();
+        if (contains(value)) { // Fast
+            Optional<AutoCompletionItem> result = stream().filter(i -> i.getValue().equals(e.getValue())).findFirst(); // Slow
+            if (result.isPresent()) {
+                AutoCompletionItem item = result.get();
+                // yes: merge priorities
+                AutoCompletionPriority newPriority = item.getPriority().mergeWith(e.getPriority());
+                // if needed, remove/re-add the updated item to maintain set ordering
+                if (!item.getPriority().equals(newPriority)) {
+                    super.remove(item);
+                    item.setPriority(newPriority);
+                    return super.add(item);
+                } else {
+                    return false;
+                }
             } else {
-                return false;
+                // Should never happen if values is correctly synchronized with this set
+                throw new IllegalStateException(value);
             }
         } else {
+            values.add(value);
             return super.add(e);
         }
+    }
+
+    @Override
+    public boolean remove(Object o) {
+        if (o instanceof AutoCompletionItem) {
+            values.remove(((AutoCompletionItem) o).getValue());
+        }
+        return super.remove(o);
+    }
+
+    @Override
+    public void clear() {
+        values.clear();
+        super.clear();
     }
 
@@ -74,5 +99,5 @@
      */
     public boolean contains(String value) {
-        return stream().anyMatch(i -> i.getValue().equals(value));
+        return values.contains(value);
     }
 
@@ -83,5 +108,5 @@
      */
     public boolean remove(String key) {
-        return removeIf(i -> i.getValue().equals(key));
+        return values.remove(key) && removeIf(i -> i.getValue().equals(key));
     }
 }
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java	(revision 13120)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionListItem.java	(revision 13121)
@@ -86,5 +86,5 @@
      */
     public void setValue(String value) {
-        item.setValue(value);
+        throw new UnsupportedOperationException("setValue() is no longer supported");
     }
 
Index: trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java	(revision 13120)
+++ trunk/src/org/openstreetmap/josm/gui/tagging/ac/AutoCompletionManager.java	(revision 13121)
@@ -332,5 +332,5 @@
 
     /**
-     * Populates the an {@link AutoCompletionList} with the currently cached values for some given tags
+     * Populates the {@link AutoCompletionList} with the currently cached values for some given tags
      *
      * @param list the list to populate