Перебирать только часть карты

Question

У меня есть данные, хранящиеся в HashMap, к которому я хочу получить доступ через несколько потоков одновременно, чтобы разделить работу, проделанную над элементами.

Обычно (например, со списком) я бы просто дал каждому потокуиндекс, с которого можно начать, и который может легко разделить работу следующим образом:

for(int i = startIndex; i < startIndex+batchSize && i < list.size(); i++)
{
    Item a = list.get(i);
    // do stuff with the Item
}

Конечно, это не работает с HashMap, потому что я не могу получить к нему доступ через индекс.

Есть ли простой способ перебора только части карты?Мне лучше использовать другую структуру данных для этого случая?

Я читал о SortedMap, но у него слишком много служебных данных, которые мне не нужны (сортировка элементов).У меня много данных, и производительность очень важна.

Любые советы будут высоко оценены.

Answer 1

Во-первых, вы не должны использовать HashMap, потому что порядок итераций не определен.Либо используйте LinkedHashMap, порядок итераций которого совпадает с порядком вставки (по крайней мере, он определен), либо используйте TreeMap, порядок итераций которого является естественным порядком сортировки.Я бы порекомендовал LinkedHashMap, потому что вставка записи сделает нарезку карты непредсказуемой.

Чтобы разделить карту, используйте этот код:

    LinkedHashMap<Integer, String> map = new LinkedHashMap<Integer, String>();

    for (Map.Entry<Integer, String> entry : new ArrayList<Map.Entry<Integer,String>>(map.entrySet()).subList(start, end)) {
        Integer key = entry.getKey();
        String value = entry.getValue();
        // Do something with the entry
    }

Я встроил код, но в развернутом виде это эквивалентно:

List<Map.Entry<Integer, String>> entryList = new ArrayList<Map.Entry<Integer,String>>();
entryList.addAll(map.entrySet());
entryList = entryList.subList(start, end); // You provide the start and end index
for (Map.Entry<Integer, String> entry : entryList) ...

Answer 2

С помощью HashMap # keySet -> Set # toArray вы получите массив ключей.

С этим массивом вы можете продолжить работу, как и раньше, сохранить массив ключей и передать их своим потокам.Тогда каждый поток получит доступ только к тем ключам, которые ему назначены, и, наконец, вы сможете получить доступ к записям данного раздела HashMap только с этими ключами.

Answer 3

Если вы делаете обход несколько раз, или если карта не меняется, вы можете получить набор ключей, а затем отправить его в массив. Оттуда это в значительной степени ваш обычный метод. Но очевидно, что если HashMap изменился, вам придется снова выполнить эти две операции, которые могут стать очень дорогостоящими.

Answer 4

Если ваша карта не огромна, стоимость итерации по карте мала по сравнению со стоимостью запуска задачи в другом потоке и тривиальна по сравнению с работой, которую вы намереваетесь выполнить.

По этой причине самый простой способ разделить вашу работу - это превратить Карту в Массив и разбить ее на части.

final Map<K, V> map =
final ExecutorServices es = 
final int portions = Runtime.getRuntime().availableProcessors();
final Map.Entry<K,V>[] entries = (Map.Entry<K,V>[]) map.entrySet().toArray(new Map.Entry[map.size()]);
final int portionSize = (map.size() + portions-1)/ portions;

for(int i = 0; i < portions; i++) {
    final int start = i * portionSize;
    final int end = Math.min(map.size(), (i + 1) * portionSize);
    es.submit(new Runnable() {
        public void run() {
            for(int j=start; j<end;j++) {
               Map.Entry<K,V> entry = entries[j];
               // process entry.
            }
        }
    });
}