Index: trunk/src/org/openstreetmap/josm/data/osm/AbstractPrimitive.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/AbstractPrimitive.java	(revision 9648)
+++ trunk/src/org/openstreetmap/josm/data/osm/AbstractPrimitive.java	(revision 9649)
@@ -9,5 +9,4 @@
 import java.util.Collections;
 import java.util.Date;
-import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Map;
@@ -391,14 +390,6 @@
      */
     @Override
-    public Map<String, String> getKeys() {
-        String[] keys = this.keys;
-        final Map<String, String> result = new HashMap<>(
-                Utils.hashMapInitialCapacity(keys == null ? 0 : keys.length / 2));
-        if (keys != null) {
-            for (int i = 0; i < keys.length; i += 2) {
-                result.put(keys[i], keys[i + 1]);
-            }
-        }
-        return result;
+    public TagMap getKeys() {
+        return new TagMap(keys);
     }
 
@@ -444,4 +435,19 @@
         }
         this.keys = newKeys;
+        keysChangedImpl(originalKeys);
+    }
+
+    /**
+     * Copy the keys from a TagMap.
+     * @param keys The new key map.
+     */
+    public void setKeys(TagMap keys) {
+        Map<String, String> originalKeys = getKeys();
+        String[] arr = keys.getTagsArray();
+        if (arr.length == 0) {
+            this.keys = null;
+        } else {
+            this.keys = arr;
+        }
         keysChangedImpl(originalKeys);
     }
Index: trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java	(revision 9648)
+++ trunk/src/org/openstreetmap/josm/data/osm/OsmPrimitive.java	(revision 9649)
@@ -919,4 +919,14 @@
 
     @Override
+    public final void setKeys(TagMap keys) {
+        boolean locked = writeLock();
+        try {
+            super.setKeys(keys);
+        } finally {
+            writeUnlock(locked);
+        }
+    }
+
+    @Override
     public final void setKeys(Map<String, String> keys) {
         boolean locked = writeLock();
Index: trunk/src/org/openstreetmap/josm/data/osm/Tag.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/Tag.java	(revision 9648)
+++ trunk/src/org/openstreetmap/josm/data/osm/Tag.java	(revision 9649)
@@ -5,4 +5,5 @@
 import java.util.Collections;
 import java.util.Map;
+import java.util.Map.Entry;
 import java.util.Objects;
 
@@ -18,5 +19,5 @@
  * the modifying methods throw an {@link UnsupportedOperationException}.
  */
-public class Tag implements Tagged {
+public class Tag implements Tagged, Entry<String, String> {
 
     private final String key;
@@ -66,4 +67,5 @@
      * @return the key of the tag
      */
+    @Override
     public String getKey() {
         return key;
@@ -75,6 +77,18 @@
      * @return the value of the tag
      */
+    @Override
     public String getValue() {
         return value;
+    }
+
+    /**
+     * This is not supported by this implementation.
+     * @param value ignored
+     * @return (Does not return)
+     * @throws UnsupportedOperationException always
+     */
+    @Override
+    public String setValue(String value) {
+        throw new UnsupportedOperationException();
     }
 
Index: trunk/src/org/openstreetmap/josm/data/osm/TagMap.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/TagMap.java	(revision 9649)
+++ trunk/src/org/openstreetmap/josm/data/osm/TagMap.java	(revision 9649)
@@ -0,0 +1,254 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.data.osm;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.Arrays;
+import java.util.ConcurrentModificationException;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.Set;
+
+/**
+ * This class provides a read/write map that uses the same format as {@link AbstractPrimitive#keys}.
+ * It offers good performance for few keys.
+ * It uses copy on write, so there cannot be a {@link ConcurrentModificationException} while iterating through it.
+ *
+ * @author Michael Zangl
+ */
+public class TagMap extends AbstractMap<String, String> {
+    /**
+     * We use this array every time we want to represent an empty map.
+     * This saves us the burden of checking for null every time but saves some object allocations.
+     */
+    private static final String[] EMPTY_TAGS = new String[0];
+
+    /**
+     * An iterator that iterates over the tags in this map. The iterator always represents the state of the map when it was created.
+     * Further changes to the map won't change the tags that we iterate over but they also won't raise any exceptions.
+     * @author Michael Zangl
+     */
+    private static class TagEntryInterator implements Iterator<Entry<String, String>> {
+        /**
+         * The current state of the tags we iterate over.
+         */
+        private final String[] tags;
+        /**
+         * Current tag index. Always a multiple of 2.
+         */
+        private int currentIndex = 0;
+
+        /**
+         * Create a new {@link TagEntryInterator}
+         * @param tags The tags array. It is never changed but should also not be changed by you.
+         */
+        TagEntryInterator(String[] tags) {
+            super();
+            this.tags = tags;
+        }
+
+        @Override
+        public boolean hasNext() {
+            return currentIndex < tags.length;
+        }
+
+        @Override
+        public Entry<String, String> next() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+
+            Tag tag = new Tag(tags[currentIndex], tags[currentIndex + 1]);
+            currentIndex += 2;
+            return tag;
+        }
+
+        @Override
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+
+    }
+
+    /**
+     * This is the entry set of this map. It represents the state when it was created.
+     * @author Michael Zangl
+     */
+    private static class TagEntrySet extends AbstractSet<Entry<String, String>> {
+        private final String[] tags;
+
+        /**
+         * Create a new {@link TagEntrySet}
+         * @param tags The tags array. It is never changed but should also not be changed by you.
+         */
+        TagEntrySet(String[] tags) {
+            super();
+            this.tags = tags;
+        }
+
+        @Override
+        public Iterator<Entry<String, String>> iterator() {
+            return new TagEntryInterator(tags);
+        }
+
+        @Override
+        public int size() {
+            return tags.length / 2;
+        }
+
+    }
+
+    /**
+     * The tags field. This field is guarded using RCU.
+     */
+    private volatile String[] tags;
+
+    /**
+     * Creates a new, empty tag map.
+     */
+    public TagMap() {
+        this(null);
+    }
+
+    /**
+     * Creates a new read only tag map using a key/value/key/value/... array.
+     * <p>
+     * The array that is passed as parameter may not be modified after passing it to this map.
+     * @param tags The tags array. It is not modified by this map.
+     */
+    public TagMap(String[] tags) {
+        if (tags == null || tags.length == 0) {
+            this.tags = EMPTY_TAGS;
+        } else {
+            if (tags.length % 2 != 0) {
+                throw new IllegalArgumentException("tags array length needs to be multiple of two.");
+            }
+            this.tags = tags;
+        }
+    }
+
+    @Override
+    public Set<Entry<String, String>> entrySet() {
+        return new TagEntrySet(tags);
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+        return indexOfKey(tags, key) >= 0;
+    }
+
+    @Override
+    public String get(Object key) {
+        String[] tags = this.tags;
+        int index = indexOfKey(tags, key);
+        return index < 0 ? null : tags[index + 1];
+    }
+
+    @Override
+    public boolean containsValue(Object value) {
+        String[] tags = this.tags;
+        for (int i = 1; i < tags.length; i += 2) {
+            if (value.equals(tags[i])) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public synchronized String put(String key, String value) {
+        if (key == null) {
+            throw new NullPointerException();
+        }
+        if (value == null) {
+            throw new NullPointerException();
+        }
+        int index = indexOfKey(tags, key);
+        int newTagArrayLength = tags.length;
+        if (index < 0) {
+            index = newTagArrayLength;
+            newTagArrayLength += 2;
+        }
+
+        String[] newTags = Arrays.copyOf(tags, newTagArrayLength);
+        String old = newTags[index + 1];
+        newTags[index] = key;
+        newTags[index + 1] = value;
+        tags = newTags;
+        return old;
+    }
+
+    @Override
+    public synchronized String remove(Object key) {
+        int index = indexOfKey(tags, key);
+        if (index < 0) {
+            return null;
+        }
+        String old = tags[index + 1];
+        int newLength = tags.length - 2;
+        if (newLength == 0) {
+            tags = EMPTY_TAGS;
+        } else {
+            String[] newTags = new String[newLength];
+            System.arraycopy(tags, 0, newTags, 0, index);
+            System.arraycopy(tags, index + 2, newTags, index, newLength - index);
+            tags = newTags;
+        }
+
+        return old;
+    }
+
+    @Override
+    public synchronized void clear() {
+        tags = EMPTY_TAGS;
+    }
+
+    @Override
+    public int size() {
+        return tags.length / 2;
+    }
+
+    /**
+     * Finds a key in an array that is structured like the {@link #tags} array and returns the position.
+     * <p>
+     * We allow the parameter to be passed to allow for better synchronization.
+     *
+     * @param tags The tags array to search through.
+     * @param key The key to search.
+     * @return The index of the key (a multiple of two) or -1 if it was not found.
+     */
+    private static int indexOfKey(String[] tags, Object key) {
+        for (int i = 0; i < tags.length; i += 2) {
+            if (tags[i].equals(key)) {
+                return i;
+            }
+        }
+        return -1;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder stringBuilder = new StringBuilder();
+        stringBuilder.append("TagMap[");
+        boolean first = true;
+        for (java.util.Map.Entry<String, String> e : entrySet()) {
+            if (!first) {
+                stringBuilder.append(",");
+            }
+            stringBuilder.append(e.getKey());
+            stringBuilder.append("=");
+            stringBuilder.append(e.getValue());
+            first = false;
+        }
+        stringBuilder.append("]");
+        return stringBuilder.toString();
+    }
+
+    /**
+     * Gets the backing tags array. Do not modify this array.
+     * @return The tags array.
+     */
+    String[] getTagsArray() {
+        return tags;
+    }
+}