Хеш-таблицы. Закрытое и открытое хеширование. Алгоритмы и алгоритмические языки. 1 курс, 23 лекция

• Лекция посвящена структурам данных, называемым хэш-таблицами.  

• Задача: организовать хранение данных таким образом, чтобы поиск, добавление и удаление объектов выполнялось эффективно.  

• Ключ может быть числовым или строковым значением.  

• Пример: поиск студентов какой-то группы на факультете.  

• Вместо просмотра всех аудиторий, можно использовать расписание, которое дает адрес аудитории.  

• Функция расстановки: вычисление адреса объекта по ключу.  

• Если ключи - целые числа, то размер массива равен количеству ключей.  

• Если ключи - символьные строки, то упорядочиваем их по алфавиту и нумеруем от 0 до количества строк.  

• Вставка записи с заданным ключом: вычисляем значение функции расстановки, добавляем запись в соответствующую позицию массива.  

• Проверка на занятость позиции: если ячейка занята, используем вторичную функцию расстановки.  

• Закрытое каширование: если при вставке записи с ключом k, значение функции расстановки k равно i, и ячейка с номером i занята, используем вторичную функцию расстановки.  

• Открытое каширование: если при вставке записи с ключом k, значение функции расстановки k равно i, и ячейка с номером i занята, используем вторичную функцию расстановки, которая сдвигает позицию на расстояние c по модулю размера таблицы.  

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

• Пример: число 95 претендует на ячейку 5, но она уже занята, поэтому применяется вторичная функция.  

• 95 по модулю 10 - 5, и число 95 попадает в ячейку 5.  

• Поиск элемента в таблице осуществляется с помощью первичной и вторичной функций.  

• Если элемент не найден за один шаг, поиск продолжается до тех пор, пока не будет найдена пустая ячейка или элемент.  

• Количество сравнений при поиске элемента зависит от степени заполненности таблицы (плотность заполнения).  

• При плотности заполнения 0.25, количество сравнений составляет 1.7.  

• При плотности заполнения 0.5, количество сравнений составляет 1.5.  

• При плотности заполнения 0.7, количество сравнений составляет 2.  

• При открытом хэшировании, если ключ претендует на несколько ячеек, создается список элементов с соответствующим ключом.  

• Поиск элемента осуществляется с помощью алгоритма бинарного поиска.  

• Оценка сложности поиска: 1 + α/2, где α - плотность заполнения таблицы.  

• Второй колориум планируется на 6 января, продолжительность - час.  

• Способ организации колориума - тест с проходом по вопросам только вперед.  

• Результаты работы в семестре будут подведены после экзамена.  

• Оценка за экзамен может быть получена автоматом, если оценка за колориум соответствует.  

• Если оценка за колориум отличается от желаемой, экзамен можно сдать с нуля.  

• Консультация перед экзаменом будет дистанционной.  

• Дерево Фибоначчи имеет минимальное количество вершин на каждом уровне.  

• Количество вершин в дереве Фибоначчи высоты аш равно аш плюс второе число Фибоначчи плюс один.  

• Балансировка дерева позволяет сократить поиск и построить дерево для любого количества вершин.  

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

• Метод цепочек используется в телефонной книжке, где количество букв известно заранее.  

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

• При закрытом хэшировании, элементы добавляются в массив, который не может быть расширен.  

• Это может привести к увеличению времени поиска элементов, если массив заполнен.  

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

• Это достигается путем окрашивания вершин определенным образом, чтобы высоты поддеревьев не различались более чем в два раза.  

• Бинарные деревья используются для организации быстрого доступа к данным.  

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

• Бинарные деревья позволяют организовать поиск данных в поддеревьях, используя несколько ключей.  

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

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

• В качестве примера приводится библиотека, где ключи (шифры) используются для организации книг в каталоге.  

• В чате задается вопрос о том, как использовать деревья для организации данных в компьютере.  

• Ответом является использование деревьев для организации блоков памяти, которые нужно делить между программами.  

• Преподаватель благодарит студентов за активное участие в курсе и желает им успехов на экзаменах.  

• Он также упоминает о возможности слушать живые лекции в будущем, но отмечает, что онлайн-курсы также имеют свои преимущества.