0 Предисловие
(1) Краткое введение в HashMap
Здравствуйте, эта статья является первой из "HashMap самостоятельно". До java7 HashMap реализовывался в виде массива(hashbucket)+связный список.Общий принцип вычислять hashCode для ключа,а hashCode по модулю размера текущего массива-это индекс массива соответствующий ключу , То же самое значение hashCode помещается в тот же индекс хранится в виде связанного списка,Вероятно, как следующее
Да, это так просто. Конечно, в java7 и раньше люди всегда скептически относились к производительности HashMap, потому что при большом количестве коллизий hashCode неизбежно потребуется O(N) времени поиска, что ничем не отличается от обычных линейных таблиц. Поэтому структура HashMap была пересмотрена в java 8. Базовая структура по-прежнему в виде массива (хэш-база) + связанный список, но при поиске hashCode была добавлена функция возмущения для уменьшения коллизий, а предыдущий обычный связанный список также был изменен на красный.Черное дерево (это все еще обычный связанный список, когда количество элементов очень мало),Вероятно, как следующее*
На этот раз я в основном говорю о красно-черных деревьях, так что давайте перейдем к делу.
1. Краткий обзор основного определения красно-черного дерева
Красно-черное дерево — это бинарное дерево поиска (Что такое бинарное дерево поиска?), которое отличается от обычного бинарного дерева тем, что добавляет к каждому узлу атрибут цвета, то есть красный или черный, а затем равномерно распределяет данные по узлам посредством цветовых ограничений. сбалансированное дерево, и почему бы напрямую не использовать сбалансированное двоичное дерево, конечно же, чтобы сбалансировать производительность различных операций. пространство ограничено,Чтобы узнать о конкретных свойствах красно-черного дерева, нажмите здесь., но это не имеет значения, если вы его не читали, потому что это будет подробно объяснено, когда код будет опубликован позже
2. Почему стоит выбрать красно-черное дерево (производительность красно-черного дерева)
Здесь прямо сформулирован вывод: высота красно-черного дерева с n внутренними узлами не превосходит 2lg(n+1).Основные операции сложения, удаления и проверки на красно-черном дереве, в том числе нахождение максимума и минимума значения, имеют наихудшую временную сложность, составляет O(lgn).
3. Базовые операции над красно-черными деревьями (добавление, обход, удаление)
Далее идет кодовая часть
(1) Организационная структура класса объектов
1. Прежде всего, должен быть объект для хранения информации о текущем узле, включая следующие атрибуты
- цвет красный или черный,
- ключ и значение текущего узла
- Родительский узел (родительский узел корневого узла равен нулю)
- левый ребенок
- правильный ребенок
следующим образом
import java.io.Serializable;
import java.util.Objects;
public class Node<K, V> implements Serializable , Comparable<Node<K, V>>{
private int color;
private K key;
private V value;
private Node<K, V> pro;
private Node<K, V> left;
private Node<K, V> right;
public Node(int color, K key, V value, Node<K, V> pro, Node<K, V> left, Node<K, V> right) {
this.color = color;
this.key = key;
this.value = value;
this.pro = pro;
this.left = left;
this.right = right;
}
public Node() {
}
public int getColor() {
return color;
}
public void setColor(int color) {
this.color = color;
}
public K getKey() {
return key;
}
public void setKey(K key) {
this.key = key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public Node<K, V> getPro() {
return pro;
}
public void setPro(Node pro) {
this.pro = pro;
}
public Node<K, V> getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node<K, V> getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node<?, ?> node = (Node<?, ?>) o;
return Objects.equals(key, node.key);
}
@Override
public int hashCode() {
return Objects.hash(key);
}
@Override
public int compareTo(Node<K, V> o) {
return this.hashCode() - o.hashCode();
}
}
Методы equals, hashCode и compareTo здесь переписаны, в основном, для удобства написания последующих кодов, т.к. часто используются операции сравнения, и здесь добавлены дженерики
2. Второй объект — красно-черное дерево.
- Должен быть атрибут для хранения корневого узла
Основная структура такая
public class Tree<K, V> implements Serializable, Iterable<Node<K, V>> {
private Node<K, V> root;
private int size;
private int BLACK = 0;
private int RED = 1;
public Tree() {
this.size = 0;
}
public int size() {
return this.size;
}
}
Наследуйте Iterable, потому что вы хотите реализовать итераторы. Мы определяем две константы, BLACK и RED, чтобы отметить цвет узла.
Пока что для реализации красно-черного дерева используется очень мало классов сущностей.
(2) поставить операцию
Вставка данных несложная.Трудность в том, что текущее дерево должно по-прежнему соответствовать свойствам красно-черного дерева после вставки данных, поэтому давайте сначала посмотрим на ограничения красно-черного дерева.
- Каждый узел либо красный, либо черный
- Корневой узел черный
- Два потомка красного узла должны быть черными.
- Для каждого узла простой путь от узла ко всем его дочерним листовым узлам (последний дочерний узел без ветвей) содержит одинаковое количество черных узлов.
На первый взгляд, правил довольно много.На самом деле конечная погоня за красно-черным деревом состоит в том, чтобы надеяться, что узлы могут быть распределены равномерно, а высота каждой ветви не должна быть слишком разной.Причина добавления цветовые ограничения для каждого узла предназначены для достижения этой цели. Для достижения этой цели нам нужно настроить красно-черное дерево, чтобы оно соответствовало характеру после вставки данных.
Шаг за шагом напишите метод для вставки узла в текущее дерево
public void put(K key, V value) {
Node<K, V> z = new Node<>();
z.setKey(key);
z.setValue(value);
z.setColor(RED);
this.size++;
Node<K, V> y = null;
Node<K, V> x = root;
while (x != null) {
y = x;
int sp = z.compareTo(x);
if (sp < 0) {
x = x.getLeft();
} else if (sp > 0) {
x = x.getRight();
} else {
x.setValue(value);
this.size--;
return;
}
}
z.setPro(y);
if (y == null) {
root = z;
} else if (z.compareTo(y) < 0) {
y.setLeft(z);
} else if (z.compareTo(y) > 0) {
y.setRight(z);
}
//调整红黑树
this.fixup(z);
}
Выше мы создали новый красный узел в начале, установили в него значение значения ключа и увеличили размер дерева на 1. Причина, по которой мы установили новый узел красным, заключается в том, что вставка красного узла лучше, чем вставка черного узла.Узлы намного проще и будут подробно рассмотрены ниже. Затем сравните размер нового узла с текущим узлом через цикл, чтобы определить позицию вставки нового узла.Маленький вставляется в левый дочерний узел, а большой — в правый дочерний узел. конечно, если узлы равны, хорошо покрыть их напрямую. Это не конец. После нахождения позиции вставки установите родительский узел нового узла и укажите дочерний узел родительского узла на новый узел. Если текущий корневой узел пуст, установите новый узел напрямую. хорошо быть корневым узлом.Наконец, вставка нового узла может нарушить свойства красно-черного дерева, поэтому мы вызываем метод fixup для корректировки красно-черного дерева.
private void fixup(Node<K, V> z) {
while (z.getPro() != null && z.getPro().getColor() == RED) {
if (z.getPro().getPro() != null) {
if (z.getPro().equals(z.getPro().getPro().getLeft())) {
Node<K, V> y = z.getPro().getPro().getRight();
if (y != null && y.getColor() == RED) {
z.getPro().setColor(BLACK);
y.setColor(BLACK);
z.getPro().getPro().setColor(RED);
z = z.getPro().getPro();
} else {
if (z.equals(z.getPro().getRight())) {
z = z.getPro();
this.leftRotate(z);
}
z.getPro().setColor(BLACK);
z.getPro().getPro().setColor(RED);
this.rightRotate(z.getPro().getPro());
}
} else if (z.getPro().equals(z.getPro().getPro().getRight())) {
Node<K, V> y = z.getPro().getPro().getLeft();
if (y != null && y.getColor() == RED) {
z.getPro().setColor(BLACK);
y.setColor(BLACK);
z.getPro().getPro().setColor(RED);
z = z.getPro().getPro();
} else {
if (z.equals(z.getPro().getLeft())) {
z = z.getPro();
this.rightRotate(z);
}
z.getPro().setColor(BLACK);
z.getPro().getPro().setColor(RED);
this.leftRotate(z.getPro().getPro());
}
}
}
}
this.root.setColor(BLACK);
}
Чтобы кратко проанализировать, когда мы вставляем новый узел, свойства которого могут быть уничтожены, свойство 1 должно быть истинным, потому что мы вставляем красный узел, свойство 4 также верно, но свойство 2 может быть уничтожено, если родительский узел также красный, то свойство 3 также будет уничтожено.Таким образом, удовлетворение свойств 2 и 3 — наша цель скорректировать текущее дерево.Думаете ли вы сейчас, что если мы вставим черный узел, свойства 2 и 3 не будут удовлетворены, но в этом случае свойство 4 не будет удовлетворено, и нам может потребоваться настроить множество узлов, чтобы удовлетворить всем свойствам, если красный узел вставлен, нам нужно только поместить цель регулировки слева или справа и продолжать смотреть вниз, Мы знаем, что сейчас нам нужно настроить древовидную структуру так, чтобы она удовлетворяла свойствам 2 и 3. Только подумайте об этом, если свойство 2 уничтожено, то причина должна заключаться в том, что текущий корневой узел пуст и нарушает свойство 3, это должен быть новый узел Родительский узел красный, потому что корневой узел должен быть черным, поэтому родительский узел нового узла не должен быть корневым узлом,Таким образом, свойства 2 и 3 не будут нарушены одновременно, и одна операция вставки нарушит только одно из них., ситуация становится намного проще. Со свойством 2 справиться проще. Просто установите новый узел или корневой узел черным. Нарушение свойства 3 немного сложнее. Всего 6 случаев, но поскольку вставка левого и правого — это симметричная операция. , нам нужно подумать только о трех случаях, а остальные три можно обратить.
Во-первых, нарушение свойства 3 происходит только тогда, когда родительский узел нового узла красный.
- Дядя нового узла красный
- Дядя нового узла черный, а новый узел является правым дочерним элементом.
- Дядя узла — черный, а новый узел — левый дочерний элемент.
Дядя-узел — это другой узел, который находится на уровне родительского узла текущего узла.
Первый случай состоит в том, что новый узел, родительский узел и узел-дядя все красные.Представьте, что если родительский узел красный, то родительский узел родительского узла должен быть черным, поэтому родительский узел и родительский узел узел должен быть черным.Все узлы-дяди окрашены в черный цвет, чтобы удовлетворить свойству 3, но поскольку увеличение количества черных узлов нарушит свойство 4, родительский узел родительского узла окрашен в красный цвет (строки 8-11 кода выше), и ситуация разрешится.
Как показано ниже
Левша
private void leftRotate(Node<K, V> x) {
Node<K, V> y = x.getRight();
x.setRight(y.getLeft());
if (y.getLeft() != null) {
y.getLeft().setPro(x);
}
y.setPro(x.getPro());
if (x.getPro() == null) {
this.root = y;
} else if (x.equals(x.getPro().getLeft())) {
x.getPro().setLeft(y);
} else {
x.getPro().setRight(y);
}
y.setLeft(x);
x.setPro(y);
}
После перемещения таким образом, я думаю, всех больше всего беспокоит порядок размера.Давайте переместим правый дочерний узел (S) вверх, чтобы он стал родительским узлом, потому что правый дочерний узел определенно больше, чем текущий узел (E), другими словами, E определенно меньше, чем S, поэтому нет проблем с тем, чтобы сделать E левым дочерним элементом S. Точно так же левый дочерний элемент S также больше, чем E, потому что узлы, меньшие, чем E, не будут вставлены в S на дочерний узел . Если левое вращение понятно, то правое вращение простое, если мы обратим операцию прямо сейчас, это будет правое вращение.
правша
private void rightRotate(Node<K, V> x) {
Node<K, V> y = x.getLeft();
x.setLeft(y.getRight());
if (y.getRight() != null) {
y.getRight().setPro(x);
}
y.setPro(x.getPro());
if (x.getPro() == null) {
this.root = y;
} else if (x.equals(x.getPro().getLeft())) {
x.getPro().setLeft(y);
} else {
x.getPro().setRight(y);
}
y.setRight(x);
x.setPro(y);
}
(картинка взята из интернета)
Мы можем преобразовать случай 2 в случай 3 (13-16) простым поворотом влево, поскольку новый узел и родительский узел оба красные, это не повлияет на другие свойства, кроме свойства 3, и тогда мы имеем дело со случаем 3, наиболее интуитивно понятный способ сделать родительский узел черным, чтобы свойство 3 не конфликтовало, а свойство 4 не соответствовало, так что же нам делать?Чтобы сбалансировать свойство 4, мы поместим родительский узел родительского узла.Одетый в красный цвет, таким образом выполняются свойства 3 и 4. Но подумайте об этом внимательно, что, если родительский узел родительского узла является корневым узлом, не соответствует ли он снова свойству 2, поэтому в настоящее время, пока решена последняя проблема, настройка может быть завершена немедленно, а как решить последнюю задачу Один вопрос,По сути, в этот раз нам нужно только преобразовать структуру дерева, не нарушая других свойств — праворуких следующим образом
Суммировать
На этом операция вставки фрагмента данных закончена.Подведем краткий итог.Сначала вставляем фрагмент данных в подходящую позицию по способу обычного бинарного дерева поиска, а затем, если свойства красно-черного дерево нарушается, мы передаем Изменить цвет и поворот, локально корректируем структуру дерева, чтобы оно соответствовало ограничениям красно-черного дерева в целом, и операция вставки завершается.
(3) Обход и поиск
Обход красно-черного дерева такой же, как и у обычного бинарного дерева поиска.Методы обхода можно разделить на обход по порядку, по порядку и по порядку.Конечно, существуют и иерархические обходы. Обход - это текущий объект выходного узла, выводимый в середине его левого дочернего узла и правого дочернего узла, следующее достигается за счет рекурсии.
public void inorder(Node<K, V> x){
if(x!=null){
inorder(x.getLeft());
System.out.println(x.getKey() + ":" + x.getValue());
inorder(x.getRight());
}
}
затем проверить
public static void main(String[] args) {
Tree<String, Integer> tree = new Tree<>();
tree.put("1", 333);
tree.put("12", 3331);
tree.put("41", 3313);
tree.put("21", 3133);
tree.put("4", 33343);
tree.put("33", 3353);
tree.inorder(tree.getRoot());
}
Для обхода предварительного и обратного порядка нужно только переместить позицию вывода текущего узла.
Реализация рекурсии очень проста, но для большинства случаев рекурсия требует частого стекирования, мы можем улучшить эту ситуацию итерационным методом, Поскольку мы хотим выполнить итерацию, давайте реализуем итератор, поставляемый с jdk, потому что тогда мы сможем использовать итераторы или улучшенные циклы for для обхода в будущем.
@Override
public Iterator<Node<K, V>> iterator() {
return new Iter();
}
private class Iter implements Iterator<Node<K, V>> {
List<Node<K, V>> array;
int cur;
public Iter() {
cur = 0;
array = new ArrayList<>();
Stack<Node<K, V>> stack = new Stack<>();
Node<K, V> next = root;
while (true) {
while (next != null) {
stack.push(next);
next = next.getLeft();
}
if (stack.isEmpty()) break;
next = stack.pop();
array.add(next);
next = next.getRight();
}
}
@Override
public boolean hasNext() {
return cur < array.size();
}
@Override
public Node<K, V> next() {
Node<K, V> node = array.get(cur);
cur++;
return node;
}
}
Сначала реализуем итератор, а затем расширяем рекурсию через цикл while.Сначала аналогично сканированию цикл помещает все оставшиеся дочерние узлы во временную очередь, а в завершение достает узлы очереди и находит его правый дочерний узел, войдите в следующий цикл.
пройти тест
public static void main(String[] args) {
Tree<String, Integer> tree = new Tree<>();
tree.put("1", 333);
tree.put("12", 3331);
tree.put("41", 3313);
tree.put("21", 3133);
tree.put("4", 33343);
tree.put("33", 3353);
for(Node node : tree){
System.out.println(node.getKey() + ":" + node.getValue());
}
}
По сравнению с пересечением,найтиГораздо проще.
public V get(K key) {
Node<K, V> node = getNode(key);
return node != null ? node.getValue() : null;
}
private Node<K, V> getNode(K key) {
if (this.root == null)
return null;
Node<K, V> x = this.root;
while (x != null && !x.getKey().equals(key)) {
if (key.hashCode() - x.getKey().hashCode() < 0) {
x = x.getLeft();
} else if (key.hashCode() - x.getKey().hashCode() > 0) {
x = x.getRight();
}
}
return x;
}
*расширятьнайти максимум и минимум
public Node<K, V> getMaximum(Node<K, V> node) {
while (node.getLeft() != null) {
node = node.getRight();
}
return node;
}
public Node<K, V> getMinimum(Node<K, V> node) {
while (node.getLeft() != null) {
node = node.getLeft();
}
return node;
}
(4) удалить
По сравнению с операцией вставки операция удаления должна учитывать больше ситуаций, поэтому обычно считается, что удаление более сложное, но несложное. Мы можем проанализировать операцию удаления в соответствии с тем, как раньше думали об операции вставки.
Для начала рассмотрим, как удаляется обычное бинарное дерево.
Подумайте о том, как мы можем удалить случайные узлы в двоичном дереве, Это примерно разделено на три случая, мы устанавливаем удаляемый узел как z
- у з нет детей
- z имеет только один дочерний узел
- z имеет два узла слова слева и справа одновременно
Первые два относительно просты: в случае 1 удалить x напрямую, в случае 2 удалить z и заменить позицию z дочерними узлами, Немного сложнее случай 3. Невозможно найти дочерний узел z для замены текущей позиции z, потому что мы должны обеспечить структуру порядка размеров, а заменяемый узел должен быть больше всех левых дочерних элементов z и больше чем все z. Правый дочерний узел маленький, сделайте паузу на две минуты, чтобы подумать об этой проблеме. Помните обход по порядку, о котором мы говорили ранее? Да, мы можем следовать идее обхода по порядку и начать поиск вниз с правого дочернего узла z (как показано c и d на рисунке выше), чтобы найти правое поддерево Наименьший узел y в правом поддереве также должен быть больше, чем все узлы в левом поддереве Лучше всего заменить x на этот узел.
Вышеупомянутая операция удаления обычного бинарного дерева.Это не так уж сложно после тщательного рассмотрения.Мы пытаемся добавить ограничение на цвет к обычному бинарному дереву,а затем мы можем проанализировать операцию удаления красно-черного дерева . Это отличается от обычного бинарного дерева.Есть два случая, то есть является ли удаленный узел z красным узлом или черным узлом. Удаление красного узла не повлияет на свойства 1, 2, 3, но если дочерний узел y перемещается вверх, чтобы заменить z, а y черный, это может повлиять на свойство 4, но мы можем решить эту проблему, просто изменив вопрос цвета. Удаление черного узла может повлиять на свойство 4, а также может повлиять на свойства 2 и 3. Повлияет это или нет, зависит от того, является ли замененный узел черным или нет.В настоящее время удаление черного узла является наиболее важным.
Тот же принцип, что и операция вставки, мы сначала удаляем узел в соответствии с логикой удаления обычного бинарного дерева, и, наконец, корректируем красно-черное дерево с помощью метода исправления.
public void remove(K key) {
Node<K, V> z = getNode(key);
Node<K, V> y = z;
Node<K, V> x;
int oColor = y.getColor();
if (z.getLeft() == null) {
x = z.getRight();
this.RBTransplant(z, z.getRight());
} else if (z.getRight() == null) {
x = z.getLeft();
this.RBTransplant(z, z.getLeft());
} else {
y = this.getMinimum(z.getRight());
oColor = y.getColor();
x = y.getLeft();
if (y.getPro().equals(z)) {
x.setPro(y);
} else {
this.RBTransplant(y, y.getRight());
y.setRight(z.getRight());
y.getRight().setPro(y);
}
this.RBTransplant(z, y);
y.setLeft(z.getLeft());
y.getLeft().setPro(y);
y.setColor(z.getColor());
}
if (oColor == this.BLACK) {
this.RBRemoveFixup(x);
}
this.size--;
}
private void RBTransplant(Node<K, V> u, Node<K, V> v) {
if (u.getPro() == null) {
this.root = v;
} else if (u.equals(u.getPro().getLeft())) {
u.getPro().setLeft(v);
} else {
u.getPro().setRight(v);
}
if (v != null)
v.setPro(u.getPro());
}
Логика удаления обычных бинарных деревьев была разобрана выше, и код здесь не будет приводиться по одному, он в основном написан по нашим предыдущим идеям. Операция RBTransplant используется для замены узлов.Ключевым моментом здесь является то, что если мы удаляем черный узел или когда в x есть два левых и правых дочерних узла, если замененный узел y не красный, то Оставьте это RBRemoveFixup для скорректировать структуру.Давайте посмотрим, как работает RBRemoveFixup.
private void RBRemoveFixup(Node<K, V> x) {
while (x != null && !x.equals(this.root) && x.getColor() == this.BLACK) {
if (x.equals(x.getPro().getLeft())) {
Node<K, V> w = x.getPro().getRight();
if (w.getColor() == this.RED) {
w.setColor(this.BLACK);
x.getPro().setColor(this.RED);
this.leftRotate(x.getPro());
w = x.getPro().getRight();
}
if (w.getLeft().getColor() == this.BLACK && w.getRight().getColor() == this.BLACK) {
w.setColor(RED);
x = x.getPro();
} else if (w.getRight().getColor() == BLACK) {
w.getLeft().setColor(BLACK);
w.setColor(RED);
this.rightRotate(w);
w = x.getPro().getRight();
}
w.setColor(x.getPro().getColor());
x.getPro().setColor(BLACK);
w.getRight().setColor(BLACK);
this.leftRotate(x.getPro());
x = root;
} else {
Node<K, V> w = x.getPro().getLeft();
if (w.getColor() == this.RED) {
w.setColor(this.BLACK);
x.getPro().setColor(this.RED);
this.rightRotate(x.getPro());
w = x.getPro().getLeft();
}
if (w.getRight().getColor() == this.BLACK && w.getLeft().getColor() == this.BLACK) {
w.setColor(RED);
x = x.getPro();
} else if (w.getLeft().getColor() == BLACK) {
w.getRight().setColor(BLACK);
w.setColor(RED);
this.leftRotate(x);
w = x.getPro().getLeft();
}
w.setColor(x.getPro().getColor());
x.getPro().setColor(BLACK);
w.getLeft().setColor(BLACK);
this.rightRotate(x.getPro());
x = root;
}
}
if (x != null)
x.setColor(BLACK);
}
Когда я вижу этот обширный код, я, возможно, сначала растерялся.Честно говоря, хотя он был написан мной, я был немного сбит с толку с первого взгляда. Но если мы извлечем уроки из нашего предыдущего опыта и проведем простой анализ, мы сразу же станем просветленными, верно? Мы устанавливаем замененный узел на x.Если x черный, нам нужно настроить его, чтобы сбалансировать красно-черное дерево, то есть переместить дополнительный черный узел вверх через операции изменения цвета и вращения до тех пор, пока
- x - красный узел
- x является корневым узлом
- х не нуль
С этой точки зрения мы разделяем операцию корректировки на 8 случаев, что аналогично операции вставки, которая симметрична попарно, поэтому нам нужно рассмотреть только 4 случая, а остальные 4 случая обратные.
Здесь мы анализируем случай, когда x — левый дочерний узел.
- брат x x красный
- брат x w черный, и оба ребенка w черные
- Родной брат w элемента x черный, левый дочерний элемент w красный, а правый дочерний элемент w черный.
- брат x w черный, а правый ребенок w красный
Выше описана операция удаления красно-черного дерева, удалить элемент красно-черного дерева очень хлопотно, но проблема ограничивается людьми, потому что для машины ее временная сложность по-прежнему log(n)
4. Вывод
Ядро HashMap - реализована структура красно-черного дерева и базовые операции Далее в следующей статье мы подробно реализуем алгоритм хеширования HashMap, думая о том, как уменьшить коллизии, а также легендарную динамику расширение. Конечно, есть также основные добавления и удаления. Проверьте, итератор и исследуйте, почему HashMap не является потокобезопасным и почему возникает взаимоблокировка.
Увидимся во втором.
Полный код этой статьи Связь:disk.Baidu.com/Yes/11C область u ZG D…Код извлечения: v1j3