How to add faster object to an array

Question

I have a list with contentlets and want all languages from every contentlet (I get these with the method languageAPI.getAllValuesByKey(key , contentList). I get a Hashmap and iterate over it. There are 1000 keys available. In the beginning it only takes 2 ms per key. But after a while it increases. And the last one takes 35ms. How can I decrease these times? How can I make it faster/more efficient?

    JSONArray arrAll = new JSONArray();
    JSONObject jsonObject = new JSONObject();
    JSONArray arr = new JSONArray();
    JSONObject values = new JSONObject();

    List<Contentlet> contentlets = languageFactory.getAllContentlets(null);
    List<Contentlet> keys = languageAPI.getLanguageKeys(null, contentlets);

    for(Contentlet key : keys) {
        Long startTime = System.currentTimeMillis();
        jsonObject = new JSONObject();

        HashMap<Long, String> allValues = languageAPI.getAllValuesByKey(key.getStringProperty("key"), contentlets);
        Iterator<java.util.Map.Entry<Long, String>> it = allValues.entrySet().iterator();
        arr = new JSONArray();
        while (it.hasNext()) {
            values = new JSONObject();
            java.util.Map.Entry<Long, String> pairs = it.next();
            values.put("l", pairs.getKey());
            values.put("v", pairs.getValue());
            arr.add(values);
            it.remove(); // avoids a ConcurrentModificationException
        }

        try {
            jsonObject.put("k", key.getStringProperty("key"));
            jsonObject.put("t", (Object)arr);
            jsonObject.put("p", key.isLive());
            jsonObject.put("l", key.isLocked());
            jsonObject.put("a", key.isArchived());
        } catch (DotStateException e) {
            throw new RuntimeException(e.toString(),e);
        } catch (DotDataException e) {
            throw new RuntimeException(e.toString(),e);
        } catch (DotSecurityException e) {
            throw new RuntimeException(e.toString(),e);
        }

        arrAll.add(jsonObject);
        Long end = System.currentTimeMillis() - startTime;
        Logger.info(this, "For key: " + key.getStringProperty("key") + " " + end  + "ms");
    }

edit:

One of the problems is that the for loop in the getStringKey method take some time. Ofcourse in the beginning the value is at the beginning, but after a while, it is at the end of the list. So I think one of the problems might be here (this takes 8ms, in the last records)

public HashMap<Long, String> getAllValuesByKey(String key, List<Contentlet> contentlets) {
    HashMap<Long, String> keys = new HashMap<Long, String>();
    for(Language language : APILocator.getLanguageAPI().getLanguages()) {
        keys.put(language.getId(), getStringKey(language.getId(), key, contentlets));
    }
    return keys;
}

public String getStringKey(Long languageId, String key, List<Contentlet> contentlets){
    String value=null;

    for(Contentlet keyEntry : contentlets) {
        if(keyEntry.getStringProperty("key").equals(key) && languageId == keyEntry.getLanguageId()) {
            return keyEntry.getStringProperty("value");
        }
    }

    if(value==null)
    {
        value = "";
    }
    return value;
}   

Edit 2, found the problem, but How to solve it?

Hmm.. the code after this phrase takes 20ms in the last records. The only thing what happens here is adding some things to a JSONObject. Why is this taking so long? I even don't know, how to make this faster, because this is the only way to handle it?

        end = System.currentTimeMillis() - startTime;
        Logger.info(this, "Before add: " + key.getStringProperty("key") + " " + end  + "ms");
        try {
            jsonObject.put("k", key.getStringProperty("key"));
            jsonObject.put("t", (Object)arr);
            jsonObject.put("p", key.isLive());
            jsonObject.put("l", key.isLocked());
            jsonObject.put("a", key.isArchived());
        } catch (DotStateException e) {
            throw new RuntimeException(e.toString(),e);
        } catch (DotDataException e) {
            throw new RuntimeException(e.toString(),e);
        } catch (DotSecurityException e) {
            throw new RuntimeException(e.toString(),e);
        }
        end = System.currentTimeMillis() - startTime;
        Logger.info(this, "After add: " + key.getStringProperty("key") + " " + end  + "ms");