Коллекция с доступом как по порядку, так и по ключевому поиску

Лучше всего подойдет LinkedHashMap.

Он работает как HashMap, у которого есть двусвязный список, проходящий через его элементы Map.Entry. Вы можете использовать список для итерации, и, будучи HashMap, он даст вам поиск O (1).

Вы можете выбрать порядок вставки или порядок доступа.

LinkedHashMap даст вам близко к O (1) с порядком размещения

Если вам нужен индексированный поиск O (1), а также поиск O (1) по ключу, вы можете сделать это, если вам не нужно помещать новые записи в карту, только создавая карту один раз (хотя, возможно, изменяя записи в карту) с Гуава ImmutableMap, который также сохраняет порядок вставки. Как и обычный Map, вы можете выполнять поиск по ключу, а также можете выполнять map.values().asList().get(i), который извлекает элемент за постоянное время. Однако я не верю, что в JDK есть что-то, что делает и то, и другое.

Основываясь на комментарии @aa333, я сделал свою собственную реализацию, возможно, она неполная, поэтому предложения приветствуются.

https://gist.github.com/anonymous/7a93535a3cfb63623a54

Он проходит эти тестовые случаи Q & D:

public static void main(String[] args) {
    Map<String, String> preMap = new HashMap<String, String>();
    preMap.put("subZero", "-1");
    preMap.put("zero", "0");
    IterableLinkedMap<String, String> map = new IterableLinkedMap<String, String>();
    map.putAll(preMap);
    map.put("one", "1");
    map.put("two", "2");
    map.put("three", "3");
    map.put("four", "4");
    map.put("five", "5");
    map.put("six", "6");
    map.remove("three");
    map.put("eight", "8");
    map.put("seven", "7");
    map.remove("one");
    map.put("three", "33");
    map.put("five", "actually five");
    for (int i = 0; i < map.size(); i++){
        System.out.println(map.getPosition(i));
    }
    map.clear();
    System.out.println(map.getPosition(0));
}

Полученные результаты:

0
-1
2
4
actually five
6
8
7
33
null