TreeMap настолько прост [анализ исходного кода]

Java задняя часть исходный код Java EE

предисловие

Утверждение, в этой статье используется jdk1.8

Обзор предыдущих глав:

эта статьяВ основном объяснить TreeMap~

Прежде чем читать эту статью, лучше немного ознакомиться с основами структуры данных:

Конечно, если что-то не так, пожалуйста, потерпите и поправьте меня в комментариях~

1. Анализ TreeMap

Как обычно, я просто перевела комментарии вверху (мой уровень английского - шлак, пожалуйста, потерпите меня, если есть какие-либо ошибки ~ Добро пожаловать, чтобы исправить меня в области комментариев)

Давайте посмотрим на схему наследования классов:

Подытожу пункты, упомянутые в комментариях:

  • TreeMap реализует интерфейс NavigableMap, а интерфейс NavigableMap наследует интерфейс SortedMap, в результате чего нашTreeMap заказан!
  • Нижний слой TreeMap представляет собой красно-черное дерево, и временная сложность его методов не слишком высока: log(n)~
  • асинхронный
  • Используйте Comparator или Comparable для сравнения ключей на равенство и сортировку ~

Что касается меня, я почти забыл Comparator и Comparable~~~ Давайте начнем с исходного кода TreeMap, чтобы увидеть, как он реализован, и рассмотрим использование Comparator и Comparable!

1.1 Домен TreeMap

1.2Метод построения TreeMap

Существует 4 метода построения TreeMap:

Можно обнаружить, что большинство методов построения TreeMap связаны с компараторами:

То есть в верхнем комментарии говорилось: порядок TreeMap сравнивается через Comparator,Если компаратор равен нулю, используется естественный порядок.~

Например:

  • Если value является целым числом, естественный порядок относится к порядку, в котором мы обычно сортируем (1,2,3,4,5..)~

    TreeMap<Integer, Integer> treeMap = new TreeMap<>();

    treeMap.put(1, 5);
    treeMap.put(2, 4);
    treeMap.put(3, 3);
    treeMap.put(4, 2);
    treeMap.put(5, 1);

    for (Entry<Integer, Integer> entry : treeMap.entrySet()) {

        String s = entry.getKey() +"关注公众号：Java3y---->" + entry.getValue();

        System.out.println(s);
    }

1.3PUT метод

Давайте посмотрим на ядро ​​метода PUT TREEWAP, вы можете получить много вещей, чтобы прочитать о характеристиках TREEWAP ~

Нижеcompare(Object k1, Object k2)метод


    /**
     * Compares two keys using the correct comparison method for this TreeMap.
     */
    @SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }

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

1.4 получить метод

Далее давайте взглянем на реализацию метода get:

нажмите вgetEntry()Посмотрите на реализацию:

Если Comparator не нулевой, давайте зайдем и посмотримgetEntryUsingComparator(Object key), как это достигается

1.5метод удаления

При удалении узла он вызываетсяdeleteEntry(Entry<K,V> p)метод, этот метод в основномУдалить узлы и сбалансированное красно-черное дерево

Код сбалансированного красно-черного дерева сложнее, я не скажу, вы видите это (не могу читать все равно) ....

1.6 Метод обхода

Глядя на исходный код, вы можете не знать, какой метод обхода является основным, потому что существует так много итераторов~

На данный момент нам просто нужно отладить, чтобы увидеть, просто следуйте!

Таким образом, мы можем найти:Обход TreeMap использует внутренний класс EntryIterator

Во-первых, давайте взглянем на диаграмму структуры классов EntryIterator:

Можно обнаружить, что большинство реализаций EntryIterator находятся в родительском классе:

Затем давайте взглянем на более важные методы PrivateEntryIterator:

мы входимsuccessor(e)Способ увидеть реализацию:

преемник на самом деле является следующим узлом узла, так называемый следующий, это следующий узел, отсортированный по порядку. Как видно из кода, если правое поддерево не пусто, возвращается наименьший узел в правом поддереве. Если правое поддерево пусто, требуется возврат. В этом случае t является последним узлом дерева с корнем в нем. Если это левый дочерний элемент своего родительского узла, то родительский узел является его следующим узлом, в противном случае t является последним узлом дерева с корнем в его родительском узле, который необходимо снова отследить. пока ch не будет левым потомком p.

источник:blog.CSDN.net/on_1 has/art IC…

2. Резюме

Нижний слой TreeMap представляет собой красно-черное дерево, которое может реализовать порядок коллекции Map~

Если в конструктор передается объект Comparator, сравнение будет выполняться так же, как и объект Comparator. В противном случае используйте ComparablecompareTo(T o)метод сравнения.

  • Стоит отметить, что если вы используетеcompareTo(T o)метод сравнения,ключ не должен быть нулевыми должен реализовать интерфейс Comparable.
  • Даже если вы проходите в объекте компаратора, вам не нужноcompareTo(T o)метод сравнения, ключСлишкомне обнуляемый

    public static void main(String[] args) {
        TreeMap<Student, String> map = new TreeMap<Student, String>((o1, o2) -> {
            //主要条件
            int num = o1.getAge() - o2.getAge();

            //次要条件
            int num2 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;

            return num2;
        });

        //创建学生对象
        Student s1 = new Student("潘安", 30);
        Student s2 = new Student("柳下惠", 35);

        //添加元素进集合
        map.put(s1, "宋朝");
        map.put(s2, "元朝");
        map.put(null, "汉朝");

        //获取key集合
        Set<Student> set = map.keySet();

        //遍历key集合
        for (Student student : set) {
            String value = map.get(student);
            System.out.println(student + "---------" + value);
        }
    }

Мы нашли из многих мест в исходном коде: Comparator и Comparable появляются очень часто, потому что реализация TreeMap упорядочена либо путем передачи объекта Comparator из внешнего мира, либо с использованием интерфейса Comparable ключа по умолчанию (для достижения естественной сортировки)

Наконец, позвольте мне резюмировать основные моменты TreeMap:

  1. Поскольку нижний слой представляет собой красно-черное дерево, можно гарантировать, что временная сложность будет равна log(n)
  2. Ключ не может быть NULL, чтобы сгенерировать NullPointexception для NULL
  3. Если вы хотите настроить сравнение, пройдите в объект компаратора в конструкторе, в противном случае используйте естественные заказа ключей для сравнения
  4. TreeMap не синхронизируется. Если вы хотите синхронизировать, вы можете использовать Collections для его инкапсуляции.

Использованная литература:

Если завтра ничего не случится, я могу написать коллекцию ConcurrentHashMap, так что следите за обновлениями~~~~

Оглавление Навигация по статьям:Город Чжунфу.bit cron.com/post/hand-just…

Если в статье есть какие-либо ошибки, пожалуйста, поправьте меня, и мы сможем общаться друг с другом. Учащиеся, привыкшие читать технические статьи в WeChat и желающие получить больше ресурсов по Java, могутОбратите внимание на публичный аккаунт WeChat: Java3y. Спасибо за Вашу поддержку! Надеюсь представить больше другим нуждающимся друзьям

Категории