Создание хеш таблицы для текстового файла

1.

Технический университет Молдовы
Тема : Создание хеш таблицы для
текстового файла

2.

Что же такое хеширование???

3.

Хеширование есть преобразование некоторого
числа или строки в уникальный ключ.
Данный уникальный ключ и называется хешем.
Процесс хеширования
функция.
осуществляет
хеш

4.

Основные критерии любой хеш функции это :
1.Очень быстрое вычисление
2.Она должна минимизировать кол-во
коллизий

5.

Какими бывают хеш функции и есть ли
универсальная хеш функция , которая была
бы эффективна для
абсолютно
любых
случаев?

6.

Самыми популярными хеш функциями
являются хеш функции с :
1.Методом деления
2.Методом середины квадрата
3.Методом свёртки
4.Мультипликативном методе

7.

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

8.

Что есть коллизия???
Коллизия это ситуация,когда хеш фунция
возвращает одинаковый ключ, для разных
чисел или строк.

9.

Хеш таблица
Хеш таблица — это обычный массив с
необычной адресацией,которую задаёт хеш
функция.

10.

Разрешение коллизий в хеш
таблице
Для разрешения коллизий используются хеш
таблицы с открытым или закрытым
хешированием

11.

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

12.

Методики повторного
хеширования в закрытой хеш
таблице
Существуют 3 методики повторного хеширования
или методов опробывания:
Линейное опробывание
Квадратичное опробывание
Двойное хеширование

13.

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

14.

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