Організація хеш-таблиці №2 ⇐ ПредыдущаяСтр 6 из 6
Побудувати хеш-таблицю. Розмірність таблиці (m), вигляд хеш-функції h(key) та вигляд функції повторного хешування hi(key) вибрати самостійно, керуючись умовами покращення ефективності методу побудови хеш-таблиці. а) Вибір варіанту індивідуального завдання: № варіанта = ( MN + RN + А1 ) % 11+ 1
б) Варіанти завдань: Розв'язання колізій при хешуванні здійснити: 1. методом роздільних ланцюжків; 2. методом відкритого хешування; 3. методом відкритої адресації; 4. методом закритого хешування; 5. методом лінійного зондування; 6. методом лінійної послідовності спроб; 7. методом рехешування; 8. методом квадратичного зондування; 9. методом квадратичної послідовності спроб; 10. методом відкритої адресації з функцією подвійного хешування; 11. методом закритого хешування з функцією подвійного хешування.
ЗМІСТ ЗВІТУ I. Оформити титульну сторінку звіту стандартного зразка, на якій вказати назву лабораторної роботи, її номер та 3 номера варіантів (1 – номер варіанта вибіру хеш-функції №1, 2 – номер варіанта розв'язання колізій при хешуванні, 3 – номер варіанта організації хеш-таблиці №2).
II. В звіті мають бути відображені наступні пункти: Мета роботи. 1. Постановка задачі. а) Анкетні дані (вміст файлу data.txt). б) Індивідуальне завдання. в) Обрана самостійно хеш-функція та метод розв'язання колізій.
2. Завдання 1. Організація хеш-таблиці №1. 2.1. Обчислення хеш-значень (написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файла data.txt). 2.2. Побудова хеш-таблиці (для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити; визначити кількість кластерів в побудованій таблиці та довжину найбільшого кластера). 2.3. Пошук ключа (словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку). 2.4. Результати роботи програми з першою хеш-таблицею (вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента).
3. Завдання 2. Організація хеш-таблиці №2. 3.1. Обчислення хеш-значень (написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файла data.txt). 3.2. Побудова хеш-таблиці (для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити; визначити кількість кластерів в побудованій таблиці та довжину найбільшого кластера). 3.3. Пошук ключа (словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку). 3.4. Результати роботи програми з першою хеш-таблицею (вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента, послідовність пошуку ключа key в хеш-таблиці, значення С n i С m ).
4. Аналіз ефективності побудованих методів організації хеш-таблиць. 4.1. Графіки С=f(α) (графік С=f1(α) для хеш-таблиці №1 і графік С=f2(α) для хеш-таблиці №2). 4.2. Графіки С=f(m) (графік С=f1(m) для хеш-таблиці №1 і графік С=f2(m) для хеш-таблиці №2) 4.3. Висновки про ефективність (порівняти ефективності побудованих методів організації хеш-таблиць).
Висновки. Додатки (тексти програм з коментарями).
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|