Сортировка HashMap <?,?> По ключу

Question

привет Мне нужно реализовать метод, который получает HashMap и сортирует (mergeSort) его значения по ключу (без использования TreeMap, SortedMap или Collections.Sort или использования каких-либо решений для сортировки из пакетов JAVA) . моя проблема связана с подстановочными типами ... это моя реализация (которая возвращает ошибки компиляции из-за использования групповых символов)

public HashMap<?, ?> mergeSort(HashMap<?, ?> map) {
        if (map.size() < 1) {
            return map;
        }
        // rounds downwards
        int middle = map.size() / 2;
        int location = 0;

        HashMap<?,?> mapLeft = new HashMap<?, ?>();
        HashMap<?,?> mapRight = new HashMap<?, ?>();
        // splitting map
        for (Iterator<?> keyIter = map.keySet().iterator(); keyIter.hasNext();) {
            if (location < middle) {
                mapLeft.put(keyIter, map.get(keyIter));
            } else {
                mapRight.put(keyIter, map.get(keyIter));
            }
            location++;
        }
        // recursive call
        mapLeft = mergeSort(mapLeft);
        mapRight = mergeSort(mapRight);
        return merge(mapLeft, mapRight);
    }

    public HashMap<?, ?> merge(HashMap<?, ?> mapLeft, HashMap<?, ?> mapRight) {
        HashMap<?, ?> result = new HashMap<?, ?>();
        Iterator<?> keyLeftIter = mapLeft.keySet().iterator();
        Iterator<?> keyRightIter = mapRight.keySet().iterator();
        String keyLeft;
        String keyRight;
        while (keyLeftIter.hasNext()) {
            keyLeft = keyLeftIter.next();
            while (keyRightIter.hasNext()) {
                keyRight = keyRightIter.next();

                if (keyLeft.compareTo(keyRight) < 0) {
                    result.put(keyLeft, mapLeft.get(keyLeft));
                    keyLeft = keyLeftIter.next();
                } else {
                    result.put(keyRight, mapRight.get(keyRight));
                    keyRight = keyRightIter.next();
                }
            }
        }
        return result;
    }

Я ценю вашу помощь!

Answer 1

Если все, что вам нужно сделать, это выполнить контракт метода, вы можете сделать это.

public HashMap<?, ?> mergeSort(HashMap<?, ?> map) {
    return new LinkedHashMap(new TreeMap(map));
}

Это позволит отсортировать ключи и вернуть подкласс HashMap.Дизайн этого метода не работает, но иногда вы не можете ничего изменить.

---

Если вы сортируете карту, вы должны использовать SortedMap, такой как TreeMap.hashmap не сохраняет порядок, поэтому использование его для сортировки слиянием невозможно.Использование сортировки слиянием для TreeMap является излишним.

Вы не можете предполагать, что ? является сопоставимым.Вы можете написать что-то вроде.

public static <K extends Comparable<K>, V> SortedMap<K,V> sort(Map<K,V> map) {
    return new TreeMap<K, V>(map);
} 

Как видите, это короче и проще, чем ваш подход.Это домашнее задание?Вам действительно нужно использовать сортировку слиянием?

Проблема, с которой вы столкнулись, заключается в том, что вы не можете вернуть HashMap, поскольку он не выполняет порядок, и вы не можете вернуть TreeMap, поскольку он отсортирует ключи для вас.делая все остальное, что вы излишни.Для этой задачи вы можете вернуть только LinkedHashMap, так как он сохраняет порядок, не выполняя для вас сортировку.

---

здесь приведен пример использования LinkedHashMap.Обратите внимание, что он не создает копии Карт, как он есть, он создает один массив и объединяет его части до тех пор, пока он не будет полностью отсортирован.

Примечание. Я использую TreeMap как SortedMap, чтобы показать его отсортированные правильно.;)

public static void main(String... args) throws IOException {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i=0;i<100;i++)
        map.put((int)(Math.random()*1000), i);
    System.out.println("Unsorted "+map);
    System.out.println("Sorted "+sort(map));
    final String sortedToString = sort(map).toString();
    final String treeMapToString = new TreeMap<Integer, Integer>(map).toString();
    if (!sortedToString.equals(treeMapToString))
        System.out.println(sortedToString+" != \n"+treeMapToString);
}

public static <K extends Comparable<K>, V> Map<K, V> sort(Map<K, V> map) {
    return mergeSort(map);
}

// a very bad design idea, but needed for compatibility.
public static <K extends Comparable<K>, V> HashMap<K, V> mergeSort(Map<K, V> map) {
    Map.Entry<K, V>[] entries = map.entrySet().toArray(new Map.Entry[map.size()]);
    mergeSort0(entries, 0, entries.length);
    HashMap<K, V> ret = new LinkedHashMap<K, V>();
    for (Map.Entry<K, V> entry : entries)
        ret.put(entry.getKey(), entry.getValue());
    return ret;
}

private static <K extends Comparable<K>, V> void mergeSort0(Map.Entry<K, V>[] entries, int start, int end) {
    int len = end - start;
    if (len < 2) return;
    int mid = (end + start) >>> 1;
    mergeSort0(entries, start, mid);
    mergeSort0(entries, mid, end);
    // merge [start, mid) and [mid, end)  to [start, end)
    for(int p = start, l=start, r=mid; p < end && l < r && r < end; p++) {
        int cmp = entries[l].getKey().compareTo(entries[r].getKey());
        if (cmp <=  0) {
            l++;
            // the entry is in the right place already
        } else if (p != r) {
            // we need to insert the entry from the right
            Map.Entry<K,V> e= entries[r];
            // shift up.
            System.arraycopy(entries, p, entries, p+1, r - p);
            l++;
            // move down.
            entries[p] = e;
            r++;
        }
    }
}

отпечатки

Unsorted {687=13, 551=0, 2=15, 984=3, 608=6, 714=16, 744=1, 272=5, 854=9, 96=2, 918=18, 829=8, 109=14, 346=7, 522=4, 626=19, 495=12, 695=17, 247=11, 725=10}
Sorted {2=15, 96=2, 109=14, 247=11, 272=5, 346=7, 495=12, 522=4, 551=0, 608=6, 626=19, 687=13, 695=17, 714=16, 725=10, 744=1, 829=8, 854=9, 918=18, 984=3}

Answer 2

Как и другие комментаторы, я бы предложил почитать тему об обобщениях в Java. То, что вы сделали в слиянии - это использование подстановочных знаков в результате HashMap

HashMap<?, ?> result = new HashMap<?, ?>();

Когда вы надеваете на него символы подстановки, вы в основном говорите: «Я буду только читать из этого». Позже вы пытаетесь что-то толкнуть в

result.put(keyLeft, mapLeft.get(keyLeft));

Компилятор скажет: "Эй, ты только что сказал мне, что будешь только читать, и теперь ты хочешь что-то вставить в ... FAIL

Затем он генерирует ваши ошибки времени компиляции.

Решение

Не помещайте символы подстановки в коллекции, которые вы будете изменять.

Answer 3

Вот метод, который сортирует карту по ключам.Используется метод Collections.sort(List, Comparator).

static Map sortByKey(Map map) {
     List list = new LinkedList(map.entrySet());
     Collections.sort(list, new Comparator() {
          public int compare(Object o1, Object o2) {
               return ((Comparable) ((Map.Entry) (o1)).getKey())
              .compareTo(((Map.Entry) (o2)).getKey());
          }
     });

    Map result = new LinkedHashMap();
    for (Iterator it = list.iterator(); it.hasNext();) {
        Map.Entry entry = (Map.Entry)it.next();
        result.put(entry.getKey(), entry.getValue());
    }
    return result;
} 

Answer 4

Почему вы всегда используете ?.Дайте детям имя, например Key или Value.

Редактировать: Вы должны пройти через этот учебный кулак: Урок: Дженерики