powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Java [игнор отключен] [закрыт для гостей] / компаратор HashMap
25 сообщений из 28, страница 1 из 2
компаратор HashMap
    #38631781
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Вопрос возник по прочтении этого ответа
http://stackoverflow.com/a/1283722/2740224

код:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
public class HashMapComparatorTest {

    public static void main(String[] args) {

        HashMap<String, Double> map = new HashMap<String, Double>();
        ValueComparator bvc = new ValueComparator(map);
        TreeMap<String, Double> sorted_map = new TreeMap<String, Double>(bvc);

        map.put("A", 99.5);
        map.put("B", 67.4);
        map.put("C", 67.4);
        map.put("D", 67.3);
        map.put("E", 100.);

        System.out.println("unsorted map: " + map);

        sorted_map.putAll(map);

        System.out.println("results: " + sorted_map);
    }

}

class ValueComparator implements Comparator<String> {

    Map<String, Double> base;

    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}



output:
авторunsorted map: {D=67.3, E=100.0, A=99.5, B=67.4, C=67.4}
results: {E=100.0, A=99.5, C=67.4, B=67.4, D=67.3}

1.Не могу понять как работает это компаратор. Не понимаю логики его работы. Но он реально работает судя по output.
2.Как это вообще так может быть ? ведь хеш таблица заполняется по определенным правилам и элементы потом в ней ищутся по определенным правилам. Останется ли у новой хеш таблицы доступ O(1) ?
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631908
rema174
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
по-моему, ключевое во всем этом:
Код: java
1.
2.
new TreeMap<String, Double>(bvc);
// Constructs a new, empty tree map, ordered according to the given comparator. 
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631925
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
rema174,

сволочи))) обманули они меня.

спасибо
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631927
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
хотя реализацию компаратора я всё равно не понимаю
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631948
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90, тебя на собеседовании завалят по любому. Кури самые основы хеш-таблиц
и бинарных (red/black) деревьев. Иначе будешь вечно плавать.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631953
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
mayton,

Просто для меня логичнее видеть такие компараторы

Код: java
1.
2.
3.
4.
5.
6.
7.
new Comparator<Map.Entry<String, Double>>() {
                @Override
                public int compare(Map.Entry<String, Double> e1,
                        Map.Entry<String, Double> e2) {
                    return e1.getValue().compareTo(e2.getValue());
                }
            }
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631968
no56892
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90,
Да добавьте себе в IDE наконец исходники jre runtime, и покопайтесь во всех этих мэпах, сэтах и т.д.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38631988
rema174
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
redwhite90хотя реализацию компаратора я всё равно не понимаю
скорее всего, тут большинство не понимают как в деталях телевизор работает, но это не мешает пользоваться телевизором.

с другой стороны, там же показана реализация, и если надо наоборот, поменять минус на плюс и делов.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632016
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90хотя реализацию компаратора я всё равно не понимаю http://ru.wikipedia.org/wiki/Стратегия_(шаблон_проектирования)
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632069
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Usman,

не в принципе компаратора, а конкретно приведенного мной компаратора)))
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632072
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90,

Смысл? Вам нужно отсортировать по значению?
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632080
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Usman,
да, надо отсортировать.

компаратор внутри себя сохраняет HashMap иии....как это помогает отсортировать...непонятно
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
class ValueComparator implements Comparator<String> {

    Map<String, Double> base;

    public ValueComparator(Map<String, Double> base) {
        this.base = base;
    }

    // Note: this comparator imposes orderings that are inconsistent with equals.
    public int compare(String a, String b) {
        if (base.get(a) >= base.get(b)) {
            return -1;
        } else {
            return 1;
        } // returning 0 would merge keys
    }
}
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632081
Фотография Usman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90,

Для сортировки TreeMap'у нужен компаратор (интерфейс), т.е. внешняя реализации метода compare(a,b) .

В качестве аргументов метода compare будут подсовываться значения ключей (а нужны значения. Как быть?)

Выход: Делается "финт" в виде класса, реализующего Comparator. НО! Чтобы была возможность отсортировать
по значениям, приходится добавлять ссылку на исходный мэп:
Код: java
1.
2.
if (base.get(a) >= base.get(b)) { } // здесь и происходит сортировка по значению ключей a и b
// first argument is less than (-1), equal to (0), or greater than the second (1).
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632103
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Usman,

ааааааааааа у двух коллекций значения(всмысле не ключи) одинаковые же.

спасибо
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632104
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
P.S. ключи тоже одинаковые, но я про Value имел ввиду
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632113
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
хотя я бы сделал компаратор по Map.Entry

Тут как-то ненаглядно вышло ИМХО.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632122
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
всё, пазл сложился)

public TreeMap(Comparator<? super K> comparator)

конструктор принимает только компаратор по ключу)
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632270
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
только где-то определенно нарушен контракт.

Код: java
1.
System.out.println(sorted_map.get("A"));




выводит null.


только где.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632311
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
так надо
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
public int compare(String a, String b) {
        if (base.get(a) > base.get(b)) {
            return -1;
        } else if (base.get(a) == base.get(b)){
            return 0;
        } else{
            return 1;
        }
    }
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632451
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90так надо
Вы читали, что там делается и зачем?
Ваш компаратор выкинет два одинаковых значения при разных ключах. :)
Тут в качестве из пушки по воробьям TreeMap используется только для одноразовой сортировки.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632613
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Сергей Арсеньев Вы читали, что там делается и зачем?
Задача отсортировать value у map
Сергей АрсеньевВаш компаратор выкинет два одинаковых значения при разных ключах. :)
Сортируем по value же. Это нарушает контракт Map разве? В общем я не понял, что конкретно тут плохо.
Сергей Арсеньев Тут в качестве из пушки по воробьям TreeMap используется только для одноразовой сортировки.
совсем же печально, что мы потом не можем из этой отсортированной мапы ничего взять, а только вывести.
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632614
redwhite90
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
....а только вывести эту мапу целиком
...
Рейтинг: 0 / 0
компаратор HashMap
    #38632944
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
redwhite90что мы потом не можем из этой отсортированной мапы ничего взять
Так первоначальная мапа есть.
Здесь шутка в том, что алгоритм построения дерева - у TreeMap уже есть им и пользуются.
Своего рода антиООП.
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
компаратор HashMap
    #39815000
arrt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Когда то передо мной постал вопрос - что если в тримапе есть ентри c одинаковыми ключами.
Ответ дает этот пример:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Map;
public class CreateTreeMapExample {
    public static void main(String[] args) {
        SortedMap<String, String> languages  = new TreeMap<>();
        languages.put("J", "Java");
        languages.put("J", "Jscript");
        languages.put("C", "C++");
        languages.put("N", ".NET");
        languages.put("P", "Pascal");
        System.out.println(languages);
    }
}


-- {C=C++, J=Jscript, N=.NET, P=Pascal}
Выходит что такого не может быть ибо следуещее значение с тем самым ключем заменяет уже существующее в тримапе, по аналогии из сетом, не выкидывая никаких эсепшенов -
public V put(K key,
V value)
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.
...
Рейтинг: 0 / 0
компаратор HashMap
    #39815004
arrt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Но в этом видоизменным примере, когда в конструктор тримапа передается хешмап,
возвращается пустой "список", даже если и нет ключей-дуюликатов.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;
public class CreateTreeMapExample {
    public static void main(String[] args) {
        Map<String, String> languages  = new HashMap<>();
        Map<String, String> languages1  = new TreeMap<>(languages);
        languages.put("J", "Java");
        languages.put("S", "Jscript");
        languages.put("C", "C++");
        languages.put("N", ".NET");
        languages.put("P", "Pascal");
        System.out.println(languages1);
    }
  }
-- {}


В чем дело?
...
Рейтинг: 0 / 0
25 сообщений из 28, страница 1 из 2
Форумы / Java [игнор отключен] [закрыт для гостей] / компаратор HashMap
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]