Предисловие:

Отвечая на запросы большинства читателей, Brother Pei представляет вам новый выпуск галантерейных товаров!

Часто задаваемые вопросы на собеседовании: BTree, красно-черное дерево, анализ хеш-алгоритма, анализ исходного кода хэш-таблицы.

Если это было полезно вам и вашим друзьям, обратите внимание на IT Pei Ge. Любимое! Поделитесь им с другими друзьями, чтобы учиться и общаться вместе, а непрерывные самородки неотделимы от ваших лайков и поддержки каждый день!

Глава 1 BTree, красно-черное дерево

1.1 BTree

• бинарное дерево:binary tree, представляет собой упорядоченный порядок с не более чем 2 узлами на узелдерево.

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

Двоичное дерево — это древовидная структура с не более чем двумя поддеревьями на узел. Верхний узел называется корневым узлом, а две стороны называются «левым поддеревом» и «правым поддеревом».

Как показано на рисунке:

1.2 Красно-черное дерево

Мы говорим о более интересной форме бинарного дерева, называемойкрасно-черное дерево, красно-черное дерево само по себе является бинарным деревом поиска, после вставки узла дерево остается бинарным деревом поиска.

Как показано на рисунке:

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

Ограничения красно-черного дерева:

1. Узлы могут быть красными или черными.
2. Корневой узел черный.
3. Листовые узлы (в частности, пустые узлы) черные.
4. Дети каждого красного узла черные.
5. Количество черных узлов на всех путях от любого узла к каждому из его листовых узлов одинаково.

Особенности красно-черных деревьев:

Скорость особенно высока, приближаясь к сбалансированному дереву.

Глава 2. Анализ алгоритма хеширования, анализ исходного кода хеш-таблицы

2.1 Хэш-значение объекта

java.lang.ObjectМетоды определены в классе:public int hashCode()Возвращает значение хэш-кода объекта. Любой класс, наследующий Object, также будет иметь этот метод.

Определите класс Person, не добавляя никаких членов, напрямую вызовите метод hashCode() объекта Person и выполните hashCode() класса Object:

public class Person{}

тестовый класс

public static void main(String[] args){
	Person person = new Person();
	int code = person.hashCode();
}

Когда вы видите результат операции, это целое число типа int. Если вы преобразуете это целое число в шестнадцатеричное, вы увидите так называемое адресное значение объекта, но это не адресное значение. Мы называем его хеш-значение объекта.

Класс Person переопределяет метод hashCode(): возвращает 0 напрямую.

public int hashCode(){
	return 0;
}

После запуска метод выполнит переопределенный метод класса Person, и результатом будет 0, который принадлежит хэш-значению пользовательского объекта класса Person, без использования метода hashCode() класса Object родительского класса.

2.2 Хэш-значение объекта String

public static void main(String[] args){
    String s1 = new String("abc");
    String s2 = new String("abc");
    System.out.println(s1.hashCode());
    System.out.println(s2.hashCode());
}

Анализ программы: Оба строковых объекта создаются с использованием нового ключевого слова.Результат s1==s2 равен false, но хеш-значения двух объектов s1 и s2 одинаковы, оба 96354. Причина в том, что класс String наследует Object , переопределяя метод родительского класса hashCode() для создания собственного хеш-значения.

Анализ исходного кода метода hashCode класса String

Базовая реализация строк представляет собой массив символов, который является окончательным и не может быть изменен после создания.

private final char value[];

Определенная строка «abc» или новая строка («abc») будет преобразована в массив char value[] и сохранена с длиной 3.

/*
 *  String类重写方法hashCode()
 *  返回自定义的哈希值
 */
public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    	char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
    	hash = h;
    }
    return h;
}

Анализ алгоритма хеширования строк

• int h = хэш, хеш — это переменная-член, значение по умолчанию — 0, int h = 0.
• Судя по тому, что h==0 истинно && value.length>0, длина значения массива равна 3, сохраняются три символа abc, и общий результат оценки верен.
• char val[] = value, присвойте массив значений массиву val.
• Цикл for выполняется 3 раза, массив значений просматривается и три символа abc вынимаются.

• Первый цикл: h = 31 * h + val[0], h = 31 * 0 + 97 Результат: h = 97.
• Второй цикл: h = 31 * 97 + val[1], h = 31 * 97 + 98 Результат: h = 3105.
• Третий цикл: h = 31 * 3105 + val[2], h = 31 * 3105 + 99 Результат: h = 96354.
• вернуть 96354.

• Алгоритм: 31 * последнее хэш-значение + значение ASCII-кода символа, 31 — простое число, и каждое умножение на 31 уменьшает вероятность того, что строки разные, но вычисляется одно и то же значение хеш-функции.

2.3 Хэш-таблица

Что такое хеш-таблица?

существуетJDK1.8Раньше нижний слой хеш-таблицы был реализован с помощью массива + связанный список, то есть массив использовался для обработки конфликтов, и все связанные списки с одним и тем же значением хеш-функции хранились в массиве. Однако когда в корзине много элементов, то есть когда много элементов с одинаковыми хеш-значениями, эффективность последовательного поиска по значению ключа низка. В JDK1.8 хранение хеш-таблицы реализовано в виде массива + связанного списка + красно-черного дерева, при превышении длины связанного списка порога (8) связанный список преобразуется в красно-черное дерево, что значительно сокращает время поиска.

• Начальная емкость хеш-таблицы, длина массива 16
  • Когда емкости массива недостаточно, увеличьте емкость до удвоенной длины исходного массива.
• Коэффициент загрузки 0,75
  • Указывает, что при использовании емкости массива на 75% от длины будет выполнено расширение.

Проще говоря, хеш-таблица реализована в виде массива + связанного списка + красно-черного дерева (JDK1.8 добавляет красно-черную часть дерева), как показано на следующем рисунке.

2.4 Схема процесса хранения символьных объектов в хеш-таблице

в общем,JDK1.8Введение красно-черного дерева значительно оптимизирует производительность HashMap, поэтому для обеспечения уникальности элементов коллекции HashSet она фактически определяется по методам hashCode и equals объекта. Если мы сохраняем пользовательский объект в коллекции, для обеспечения его уникальности мы должны переопределить методы hashCode и equals, чтобы установить метод сравнения, принадлежащий текущему объекту.

2.5 Анализ исходного кода хеш-таблицы

Сама коллекция HashSet не предоставляет функций. Базовый слой опирается на коллекцию HashMap. Объект HashMap создается в методе построения HashSet:

map = new HashMap<>();

Таким образом, анализ исходного кода должен анализировать исходный код коллекции HashMap.Метод add в коллекции HashSet исследует метод put в коллекции HashMap.

Анализ безпараметрического метода построения HashMap

//HashMap中的静态成员变量
static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

Анализ: Создайте объект HashMap, используя метод построения без параметров, и установите коэффициент загрузки равным коэффициенту загрузки по умолчанию, loadFactor=0,75F.

HashMap имеет анализ метода построения параметров

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
    	throw new IllegalArgumentException("Illegal initial capacity: " +
    initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
    	initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
    	throw new IllegalArgumentException("Illegal load factor: " +
    loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

РазобратьКонструктор с параметрами, передающими инициализирующую емкость и коэффициент загрузки хеш-таблицы

• Если initialCapacity меньше 0, сразу создается исключение.
• Если InitialCapacity больше, чем самый большой контейнер, InitialCapacity напрямую равна самому большому контейнеру.
  • MAXIMUM_CAPACITY = 1
• Если loadFactor (коэффициент загрузки) меньше или равен 0, выдать исключение напрямую
• Метод tableSizeFor(initialCapacity) вычисляет начальную емкость хеш-таблицы.
  • Примечание: хеш-таблица — это расчетная емкость, а емкость инициализации не равна напрямую параметрам, которые мы передаем.

tableSizeFor метод анализа

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

РазобратьЭтот метод выполняет операцию сдвига передаваемой нами емкости инициализации, и результатом сдвига является код 8 4 2 1.

• Например, если передано 2, результатом будет по-прежнему 2, а если передано 4, результатом будет по-прежнему 4.
• Например, проход 3, результат 4, проход 5, результат 8, проход 20, результат 32.

Анализ внутреннего класса узла

Хеш-таблица — это метод реализации с использованием массива + связанный список, внутренний класс Node в HashMap очень важен

 static class Node<K,V> implements Map.Entry<K,V> {
     final int hash;
     final K key;
     V value;
     Node<K,V> next;
 Node(int hash, K key, V value, Node<K,V> next) {
     this.hash = hash;
     this.key = key;
     this.value = value;
     this.next = next;
}

РазобратьПеременные узел внутренних классов, имеющих четыре члена

• hash, хеш-значение объекта
• ключ, объект, который является ключом
• значение как достойный объект (объясняющий коллекцию Set, не связанный с достойной проблемой)
• следующий, следующий узел объекта

Исходный код метода put элемента хранилища

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

РазобратьВ методе put исследуется метод putVal, а в методе putVal вызывается метод hash.

• метод hash(key): передать элемент для сохранения и получить хэш-значение объекта
• метод putVal, передавая хеш-значение объекта и ключ объекта, который нужно сохранить.

Исходный код метода putVal

Node<K,V>[] tab; Node<K,V> p; int n, i;
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;

РазобратьВ методе оценивается массив объектов Node.Если массив нулевой или длина равна 0, то метод resize() будет исследоваться для расширения массива.

Расчет расширения метода изменения размера

 if (oldCap > 0) {
     if (oldCap >= MAXIMUM_CAPACITY) {
         threshold = Integer.MAX_VALUE;
         return oldTab;
     }
     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold
}

РазобратьВ результате расчета емкость нового массива = емкость исходного массива

Определить индекс, по которому хранится элемент

if ((p = tab[i = (n - 1) & hash]) == null)
	 tab[i] = newNode(hash, key, value, null);

Разбор: i = (длина массива - 1) & хеш-значение объекта, будет получен индекс, а затем tab[i] под этим индексом создаст объект связанного списка.

Также возможно, что объекты с разными хэш-значениями будут храниться под одним и тем же индексом массива.

Обнаружены объекты с повторяющимися хэш-значениями

 Node<K,V> e; K k;
 if (p.hash == hash &&
 	((k = p.key) == key || (key != null && key.equals(k))))
		 e = p;

РазобратьЕсли хеш-значения объектов совпадают, метод equals объекта возвращает true, и он оценивается как объект, и выполняется операция перезаписи.

 else {
     for (int binCount = 0; ; ++binCount) {
     	if ((e = p.next) == null) {
     		p.next = newNode(hash, key, value, null);
     	if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
     		treeifyBin(tab, hash);
     	break;
 }

РазобратьЕсли хэш-значения объектов одинаковы, но метод equals объекта возвращает false, будет пройден связанный список.Когда связанный список не имеет следующего узла, следующий узел будет создан для хранения объекта.

Для последующих статей, пожалуйста, смотрите:

• Позвольте вам решить поток Stream, который должен использоваться крупными производителями, ссылка на метод🔥
• Позвольте вам решить лямбда-выражения и функциональные интерфейсы, которые должны использоваться крупными производителями🔥

Чтобы посмотреть больше качественных статей, перейдите наКраткое изложение технологий, которые должны использовать основные производители! 🔥

---

Если это было полезно вам и вашим друзьям, обратите внимание на IT Pei Ge. Коллекция!Поделитесь ею с большим количеством друзей, чтобы учиться и общаться вместе, а постоянные обновления каждый день неотделимы от вашей поддержки!

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