Докладний аналіз структур даних. Частина 2: Черга




Ця стаття – друга частина серії з 6 статей про
структурах даних в. NET Framework – присвячена трьом найбільш часто
аналізованим структурам даних: черги, стеку і хеш-таблиці. Як ми побачимо,
чергу і стек робляться за допомогою ArrayList-а, забезпечуючи місце для зберігання
змінного числа об'єктів, накладаючи, однак, при цьому обмеження на порядок
доступу до елементів. Хеш-таблиця – це структура даних, схожа на масив, але з
більшою гнучкістю індексування елементів.


Частина 2: Черга, стек і хеш-таблиця


Огляд: Ця стаття – друга частина серії з 6 статей про структури даних
в. NET Framework – присвячена трьом найбільш часто розглядаються структурам
даних: черги, стеку і хеш-таблиці. Як ми побачимо, черга і стек робляться з
допомогою ArrayList-а, забезпечуючи місце для зберігання змінного числа об'єктів,
накладаючи, однак, при цьому обмеження на порядок доступу до елементів.
Хеш-таблиця – це структура даних, схожа на масив, але з більшою гнучкістю
індексування елементів. У той час як в масиві елементи індексуються з
допомогою порядкової величини, елементи хеш-таблиці можуть бути індексовані
за допомогою будь-якого об'єкта.

Введення


У Частині 1: Докладний аналіз структур даних, ми зупинилися на визначенні
поняття структур даних, методах оцінки їх ефективності, а також на тому, як
ці міркування впливають на вибір тієї чи іншої структури даних для конкретного
алгоритму. Крім вивчення базових речей про структури даних та аналізі їх
ефективності, ми також розглянули найбільш часто використовувану структуру даних
– Масив.

Масив містить сукупність однорідних елементів (елементів одного типу),
кожному з яких відповідає порядковий індекс. Фізично, вміст
масиву розташовується в пам'яті у вигляді безперервної області. Завдяки цьому
читання або запис елемента масиву здійснюється дуже швидко.

Два нестачі масивів – це їхня однорідність і те, що розмір масиву повинен
бути явно заданий. Для усунення цього недоліку бібліотека класів. NET
Framework містить у собі таку структуру даних як ArrayList, яка
являє собою сукупність елементів різного типу. Причому його розмір
збільшується автоматично при необхідності. Як ми вже обговорили в попередній
статті, реалізація ArrayList ст. NET Framework використовує масив типу
object. Кожен виклик методу Add() ArrayList-а перевіряє,
чи достатній розмір внутрішнього масиву object-ів для зберігання
додаткових елементів і якщо ні, то розмір цього внутрішнього масиву
автоматично подвоюється.

У другій частині серії ми продовжимо наше знайомство з массівоподобнимі
структурами даних і, перш за все, розглянемо чергу (queue) і стек (stack).
Подібно ArrayList-у, ці дві структури даних містять сукупність елементів
різного типу (heterogeneous data) в безперервній області пам'яті (contiguous
block). Однак, як черга, так і стек, накладають обмеження на порядок доступу
до даних.

Після розгляду черги і стека, ми присвятимо інший час, розбираючись в
механізмах роботи хеш-таблиці. Хеш-таблиця, іноді звана також
асоціативним масивом (associative array), зберігає сукупність елементів
різного типу. Однак, елементи хеш-таблиці можуть бути проіндексовані з
допомогою об'єктів довільного типу (наприклад, рядками), а не тільки порядковим
індексом.

Обробка за принципом "Першим прийшов, першим обслужений"


Уявіть собі, що ви пишете комп'ютерну програму, яка може
отримувати множинні запити на виконання деякого завдання з декількох
джерел. Одне із завдань, яку вам доведеться вирішити при написанні такої
програми – це встановити порядок, в якому будуть оброблятися входять
запити. Два типових підходу, які вживаються у цьому випадку такі:


З обробкою запитів за принципом FCFS ми стикаємося в магазині, банку і
т.п. Люди, які очікують моменту, коли їх обслужать, стають у чергу. Ті, хто
стоять перед вами, обслуговуються раніше вас, а ті, хто стоять після, будуть
обслужені пізніше вас. При пріоритезувати обробці ті, у кого пріоритет
більше будуть обслужені перед тими, у кого пріоритет менше. Наприклад, служба
швидкої допомоги в лікарні обслужить спочатку пацієнтів з потенційно смертельним
пораненням, а не тих пацієнтів, стан яких менш критично, незалежно від
того, хто прибув першим.

Уявімо, що нам потрібно створити комп'ютерну службу, і що ми хочемо
обробляти запити до неї в порядку їх отримання. Оскільки запити можуть
з'являтися швидше, ніж ми будемо здатні їх обробити, нам буде потрібно
поміщати запити в деякий буфер, який буде зберігати ці запити в порядку
їх приходу.

Можливе рішення – використовувати ArrayList і цілочисельну змінну
nextJobPos, в якій буде зберігатися індекс наступного завдання, яка
повинна бути відправлена на обробку. З приходом нового завдання ми просто будемо
використовувати метод Add() для додавання задачі в кінець ArrayList-а. Як
тільки ми готові обробити чергове завдання, що знаходиться в буфері, ми беремо це
завдання з nextJobPos-ого елемента ArrayList-а і збільшуємо
nextJobPos на 1. Наступна програма описує цей алгоритм:

using System;
using System.Collections;

public class JobProcessing
{
private static ArrayList jobs = new ArrayList();
private static int nextJobPos = 0;
public static void AddJob(string jobName)
{
jobs.Add(jobName);
}
public static string GetNextJob()
{
if (nextJobPos > jobs.Count – 1)
return "NO JOBS IN BUFFER";
else
{
string jobName = (string) jobs[nextJobPos];
nextJobPos++;
return jobName;
}
}

public static void Main()
{
AddJob("1");
AddJob("2");
Console.WriteLine(GetNextJob());
AddJob("3");
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
Console.WriteLine(GetNextJob());
AddJob("4");
AddJob("5");
Console.WriteLine(GetNextJob());
}
}


Висновок програми такий:

1
2
3
NO JOBS IN BUFFER
NO JOBS IN BUFFER
4

Притому, що такий підхід виключно простий і прямолінійний, він страшенно
неефективний. Для новачків пояснюємо: ArrayList буде необмежено зростати з
кожним додаванням нового завдання в буфер. Це буде відбуватися навіть у тому
випадку, коли запити обробляються негайно після поміщення їх у буфер.
Розглянемо приклад, коли кожну секунду в буфер додається завдання і з буфера
видаляється завдання. Це означає, що раз на секунду викликається метод
AddJob(), Який в свою чергу викликає метод Add() ArrayList-а.
При безперервному виклику методу Add(), Розмір внутрішнього масиву
ArrayList-а постійно подвоюється в міру необхідності. Після 5 хвилин (300
секунд) розмір внутрішнього масиву ArrayList-а досягне 512 елементів, незважаючи
на те, що в буфері ніколи не знаходилося більше 1 завдання одночасно! Розмір
масиву буде, звичайно ж, продовжувати рости в процесі роботи програми і з
приходом нових завдань.

Причина того, що ArrayList розростається до таких неймовірних розмірів у тому,
що пам'ять буфера, що використовувалась для старих запитів, не використовується
повторно. Адже коли ми додаємо перше завдання в буфер, а потім видаляємо його з
буфера після відправки на обробку, перша позиція ArrayList-а може бути
використана повторно для розміщення в ній нового запиту. Розглянемо процес
диспетчеризації задач, представлений у програмі, написаної вище. Після
виконання перших двох рядків-AddJob ("1") і AddJob ("2")-вміст ArrayList-а
буде виглядати так (рис. 1):


Малюнок 1. ArrayList після виконання перших двох рядків коду

Зауважте, що ArrayList на цей момент містить 16 елементів тому, що при
створення ArrayList-а за умовчанням створюється внутрішній масив з 16 елементів
типу object. Після цього викликається метод GetNextJob(), Який
видаляє перше завдання з буфера. У результаті ми отримуємо ситуацію, показану
на рис. 2.


Малюнок 2. Програма після виклику методу GetNextJob ()

Коли виконується AddJob ("3"), нам потрібно додати чергову задачу в буфер.
Очевидно, що перший елемент ArrayList-а (з індексом 0) можна використовувати
повторно. Спочатку, можливо, і є якийсь сенс помістити третій завдання в
нульовий елемент. Однак, ми змушені відкинути такий підхід, розглянувши, що
ж вийде якщо після виконання AddJob ("3") ми викличемо AddJob ("4"), а потім
два виклики методу GetNextJob (). Якщо б ми помістили третє завдання по нульовому
індексом, а четверту – в елемент з індексом 2, ми б отримали наступну
неприємну ситуацію, показану на малюнку 3.


Малюнок 3. Що вийде при приміщенні третього завдання по нульовому
індексом

Тепер якщо ми викличемо GetNextJob () з буфера буде видалена друге завдання,
значення nextJobPos буде збільшено на 1 і стане рівним 2. Таким чином, при
повторному виклику GetNextJob (), з буфера буде видалена четверте завдання, яка
в результаті буде оброблена раніше третьої. Ми отримуємо, що порушується
порядок "Першим прийшов, першим обслужений", який ми домовилися підтримувати.

Суть наших проблем полягає в тому, що ArrayList являє собою список
завдань в лінійному порядку. Це означає, що ми завжди повинні додавати нові
завдання в буфер правіше старих завдань, щоб гарантувати коректний порядок
обробки запитів. Кожен раз, коли ми натикаємося на кінець ArrayList-а, його
розмір подвоюється навіть у тому випадку, якщо існують порожні елементи,
утворилися через викликів GetNextJob().

Щоб виправити це, нам доведеться зробити ArrayList циклічним (сircular).
Циклічний масив не має певного початку або кінця. Точніше, кінець і
початок масиву зберігаються в певних змінних. Графічне представлення
циклічного масиву показано на Малюнку 4.


Малюнок 4. Приклад циклічного масиву

При роботі з циклічним масивом, метод AddJob() поміщає нову
завдання в елемент з індексом endPos, А потім "инкрементируются"
endPos. Метод GetNextJob() забирає завдання з елемента з індексом
startPos, Присвоює елементу з індексом startPos значення null,
а потім "инкрементируются" startPos. Слово "інкрементіровать" (increment)
значить збільшувати на одиницю. Воно було поміщено в лапки, тому що в даному
випадку під "інкрементаціей" маються на увазі трохи більш складні дії, ніж
просте додаток одиниці до целочисленному значенням змінної. Щоб зрозуміти,
чому ми не можемо просто взяти і додати 1, розглянемо випадок, коли
endPos дорівнює 15. Якщо ми додамо до endPos одиницю, значення
endPos стане рівним 16. При наступному виклику AddJob() ми
спробуємо отримати доступ до елемента з номером 16, що призведе до виключення
IndexOutOfRangeException.

Замість цього, коли endPos дорівнює 15, нам хотілося б
"Інкрементіровать" endPos так, щоб його значення стало рівним 0. Ми
можемо зробити це, написавши функцію increment(variable), Яка б
перевіряла, що значення фактичного вхідного параметра дорівнює розміру масиву, і
в цьому випадку скидала це значення в 0. Альтернативний варіант – це
додавати одиницю, проте складання виконувати за модулем розміру масиву. У цьому
випадку, код функції increment() буде таким:

int increment(int variable)
{
return (variable + 1) % theArray.Length;
}

Примітка Бінарний оператор% у натуральному вираженні x% y обчислює залишок від
ділення x на y. Залишок завжди буде в межах між 0 і y – 1.

Цей підхід відмінно працює, якщо наш буфер ніколи не буде містити більше
16 елементів. А що буде, якщо ми захочемо додати нове завдання в буфер, в
якому вже є 16 завдань? Like Подібно методом Add() ArrayList-a, нам
доведеться відповідним чином змінити розмір циклічного масиву, наприклад,
подвоївши розмір масиву.

Клас System.Collections.Queue


Функціональність, яку ми тільки що описали – додавання та видалення
елементів з буфера в порядку FCFS при максимальній оптимізації використовуваного
обсягу пам'яті – надається стандартною структурою даних – Чергою.
Бібліотека класів. NET Framework Base містить вбудований клас
System.Collections.Queue. Аналогічно тому, як ми використовували вище в
написаному нами коді методи AddJob() і GetNextJob(), Клас
Queue cпредоставляет відповідну функціональність у вигляді методів
Enqueue() і Dequeue() відповідно.

За лаштунками, клас Queue використовує внутрішній циклічний масив
елементів типу object і дві змінні, які служать в якості маркерів початку і
кінця циклічного масиву: head (голова) і tail (хвіст). За
замовчуванням початковий розмір черги дорівнює 32 елементів, хоча цю величину можна
налаштувати при виклику конструктора черги. Оскільки чергу для зберігання даних
використовує масив object-ів, у ній можна зберігати змінні будь-яких типів.

Метод Enqueue() визначає, чи достатньо місця для додавання нового
елемента в чергу. Якщо так, то елемент просто записується в комірку масиву з
індексом tail, після чого значення tail "Инкрементируется" (тобто
збільшується на одиницю і від результату береться залишок від ділення його на довжину
масиву). Елсі місця недостатньо, розмір масиву збільшується в n разів. Число n
називається growth factor – фактор росту. За замовчуванням його значення дорівнює 2.0, а
значить, за умовчанням розмір масиву подвоюється. Зазначимо, що фактор зростання ви
також можете задавати в конструкторі класу Queue.

Метод Dequeue() повертає елемент, який знаходиться в комірці масиву
з індексом head. Після цього він привласнює елементу head значення
null і "инкрементируются" head. Для тих випадків, коли ви бажаєте лише
прочитати значення елемента з голови черги, але прицьому не видаляти його звідти,
клас Queue пропонує метод Peek().

Важливо розуміти те, що при роботі з чергою, на відміну від ArrayList-а, ви не
маєте доступу до її безпідставного елементу. Наприклад, ви не можете подивитися
третій елемент черги, не видаливши з неї перші 2 елементи. (Зазначимо, однак,
що клас Queue має метод Contains(), Використовуючи який ви
можете визначити, чи містить чергу той чи інший конкретний елемент). Якщо ви
точно впевнені, що вам необхідний довільний доступ (random access), то
структура даних "черга" не для вас – використовуйте краще ArrayList. Безумовно,
чергу є ідеальним вибором в ситуаціях, коли вам необхідно виконувати
обробку елементів даних точно в порядку їх надходження.

Примітка Черги також часто називають структурами даних типу FIFO –
First In, First Out. Сенс цієї абревіатури аналогічний FCFS і по-російськи звучить
приблизно, як "першим увійшов, першим вийшов".

Структура даних "стік": Першим прийшов, Останнім обслужений (First Come,
Last Served)


Черга дає нам доступ до елементів в порядку "першим прийшов, першим пішов" і
використовує для цих цілей внутрішній циклічний масив object-ів. Така
функціональність надається за допомогою методів Enqueue() і
Dequque(). Порядок обробки "першим прийшов, першим пішов" має багато
застосувань в реальних додатках, таких як веб-сервери, черги друку і
інших програмах, орієнтованих на обробку множинних запитів.

Іншою популярною схемою обробки в комп'ютерних програмах є підхід
"Першим прийшов, останнім пішов". Структура даних, що надає такий доступ
до своїх елементів, називається стек (або магазин – за аналогією з магазином
автоматичної зброї). Бібліотека класів. NET Framework містить клас
System.Collections.Stack, Який, подібно класу Queue, Зберігає
свої елементи в циклічному масиві типу object. Управління даними,
містяться в стеку, відбувається за допомогою методу Push(item)
("Заштовхнути")
, Який поміщає об'єкт, переданий як параметра в
стек, і методу Pop () ("витягти"), Який повертає об'єкт з вершини
стека, видаляючи його зі стека.

Графічно стек можна зобразити у вигляді вертикальної "піраміди" елементів.
При "заталківаніі" елемента в стек він поміщається зверху над всіма іншими
елементами. Витяг елемента зі стека, видаляє його свершіни стека. Наступні
2 малюнки показують стек після "заталківанія" в нього елементів 1, 2, and 3 та
подальшого їх видалення з стека.


Малюнок 10. Хеш-таблиця з 4 співробітниками зі схожими номерами

Номер соціального страхування Аліси хешіруется в значення 1234 і її запис
поміщається в 1234-й елемент масиву. Далі, номер Боба теж хешіруется в 1234,
проте осередок 1234 вже зайнята записом Аліси, таким чином Боб займає
наступну вільну комірку – 1235. Після Боба ми додаємо запис Кела,
хеш-функція видає для його номера соціального страхування значення 1237.
Оскільки у клітинці 1237 нікого немає, запис Кела поміщається в неї. Наступний –
Денні. Його номер відображається хеш-функцією в 1235. Оскільки позиція 1235
зайнята, перевіряється осередок з номером 1236. Оскільки осередок 1236 вакантна, Денні
записується в неї. У кінці додається запис Едварда, його номер соціального
страхування також хешіруется в 1235. Оскільки 1235 зайнята, перевіряється 1236.
Вона також зайнята, перевіряємо 1237. Цей осередок зайнята Келом, і ми перевіряємо 1238,
яка виявляється вільною. Отже, запис Едварда додається в клітинку 1238.

Через колізій виникають проблеми і при пошуку в хеш-таблиці. Наприклад,
уявімо, що нам потрібно знайти в хеш-таблиці з попереднього прикладу інформацію
про Едварда. Ми беремо номер соціального страхування Едварда 111-00-1235, хешіруем
його, отримуємо 1235 і починаємо пошук. У клітинці 1235 ми знаходимо Боба, а не
Едварда. Таким чином, нам потрібно тепер перевірити клітинку 1236, але там Денні.
Наш лінійний пошук триватиме або до тих пір, поки ми не знайдемо
Едварда, або коли ми дійдемо до порожнього вічка. Останнє буде означати, що в
хеш-таблиці не існує співробітника з номером соціального страхування
111-00-1235.

Незважаючи на те, що лінійна послідовність проб – проста процедура, вона
є не найкращим способом вирішення колізій, оскільки веде до утворення
кластерів (clustering). Пояснимо це поняття. Уявімо, що перші 10
співробітників, яких ми додали в хеш-таблицю, всі мають номер соціального
страхування, що закінчується на одні й ті ж 4 цифри, скажімо, 3344. Тоді будуть
зайняті 10 послідовних комірок масиву від 3344 до 3353. При спробі пошуку
даних будь-якого з цих 10 співробітників буде відбуватися процес лінійної
послідовності проб. Більш того, додавання співробітників, для яких
значення хеш-функції лежить в інтервалі від 3345 до 3353 призведе до подальшого
розростанню кластеру. Для швидкого пошуку, звичайно ж, краще мати рівномірний
розподіл даних в хеш-таблиці, а не кластерізованное в околиці
деяких точок.

Складнішою є квадратична послідовність проб (quadratic
probing), яка починає перевіряти осередки на квадратичному відстані один від
одного. Тобто в разі, якщо осередок s зайнята, то замість перевірки осередку s + 1,
а за нею s + 2 і т.д., як в лінійній послідовності проб, спочатку
перевіряється осередок (s + 1) 2, потім (s – 1) 2, потім (s + 2) 2, потім (s – 2) 2,
після цього (s + 3) 2 і так далі. Однак навіть квадратичний варіант може
привести до утворення кластерів.

У наступному розділі ми розглянемо третій метод вирішення колізій,
званий повторним хешування (rehasing). Цей метод використовується класом
Hashtable з. NET Framework.

Клас System.Collections.Hashtable


Базова бібліотека класів. NET Framework iсодержіт реалізацію хеш-таблиці у
класі Hashtable. При додаванні елемента в Hashtable ви повинні передати
не тільки дані, але й унікальний ключ, за яким цей елемент може бути
знайдено. Як ключ так і дані можуть бути будь-якого типу. У нашому прикладі з
сотруднікаміключом був номер соціального страхування. Елементи додаються в
Hashtable за допомогою методу Add().

Щоб витягти елемент з Hashtable ви можете індексувати хеш-таблицю за
ключу, точно так само, як ви б індексували елемент масиву з допомогою
порядкового індексу. Наступна невелика програма на C # демонструє як це
робиться. Програма додає в Hashtable кілька елементів, асоціюючи з
кожним елементом рядковий ключ. Після цього доступ до конкретного елементу можна
отримати за його строковому ключу.

using System;
using System.Collections;

public class HashtableDemo
{
private static Hashtable ages = new Hashtable();
public static void Main()
{
/ / Додамо кілька значень, проіндексованих строковим ключем в хеш-таблицю
ages.Add("Scott", 25);
ages.Add("Sam", 6);
ages.Add("Jisun", 25);
/ / Знайдемо елемент по його ключу
if (ages.ContainsKey("Scott"))
{
int scottsAge = (int) ages["Scott"];
Console.WriteLine ("Scott is" + scottsAge.ToString ());
}
else
Console.WriteLine ("Scott is not in the hash table …");
}
}


У коді також демонструється метод ContainsKey(), Який повертає
булеве значення, що говорить нам чи був знайдений в хеш-таблиці вказаний ключ.
Клас Hashtable має властивість Keys, Повертає всі ключі,
використовувані в хеш-таблиці. Ця властивість може бути використано для
перерахування елементів хеш-таблиці, як показано внизу:

/ / Прохід по всіх елементах хеш-таблиці
foreach(string key in ages.Keys)
Console.WriteLine ("Value at ages [" "+ key +" "] =" + ages [key]. ToString ());

Важливо розуміти, що порядок, в якому елементв додаються в хеш-таблицю і
порядок ключів в колекції, яка повертається властивістю Keys не обов'язково один і
той самий. Порядок у колекції Keys відповідає порядку осередки у внутрішньому
масиві, в якій зберігається об'єкт з даними ключем. Наприклад, результатом
виконання коду, наведеного вище, буде:

Value at ages["Jisun"] = 25
Value at ages["Scott"] = 25
Value at ages["Sam"] = 6

Незважаючи на те, що порядок додавання елементів був "Scott," "Sam," "Jisun."
Хеш-функція класу Hashtable

Хеш-функція класу Hashtable трохи складніше функції для номера
соціального страхування, розглянутої вище. По-перше, пам'ятайте, що хеш-функція
повинна повертати порядкове значення. Цій вимозі було легко задовольнити
у прикладі з номером соціального страхування, тому що це номер вже сам по
собі є числом. Для отримання хешу ми просто викинули всі цифри, крім
останніх чотирьох. Однак, клас Hashtable дозволяє ключу мати
довільний тип. Наприклад, ключ може бути рядком на кшталт "Скотт" або "Сем", як
у попередньому прикладі. Виникає природне запитання, як хеш-функція переводить
рядок на число.

Це магічне перетворення здійснюється методом GetHashCode(),
визначеним у класі System.Object. Реалізація методу
GetHashCode() класу Object за замовчуванням повертає унікальне
ціле число, яке гарантовано не зміниться за час життя об'єкта.
Оскільки всі типи прямо успадковуються від класу Object, Всім об'єктам
доступний цей метод. Тому рядок або будь-який інший тип може бути представлений
унікальним числом.

Визначення хеш-функції класу Hashtable таке:

H (key) = [GetHash (key) + 1 + (((GetHash (key)>> 5) + 1)% (hashsize – 1))]% hashsize

Саме тут GetHash(key) – Це за замовчуванням значення, що повертає при
виклику методу GetHashCode() об'єкта key (ви можете визначити
власну функцію GetHash()). GetHash (key)>> 5 обчислює хеш для
key після чого виконує побітовий зрушення вправо на 5 біт, що рівносильно
поділу результату хешування на 32. Як вже обговорювалося раніше в цій статті,
оператор% служить для знаходження залишку від ділення одного числа на інше.
hashsize – це загальне число всіх осередків в хеш-таблиці. (Згадаймо, що x% y
повертає залишок від ділення x на y і що цей залишок лежить в діапазоні від 0
до y – 1.) Завдяки операціям взяття модуля кінцевий результат функції H (key)
завжди буде від 0 до hashsize – 1. А оскільки hashsize – це число всіх осередків у
хеш-таблиці, то результат, виданий хеш-функцією, буде завжди лежати в
допустимих межах.

Дозвіл колізій у класі Hashtable


Згадаймо, що при вставці або видаленні елементу з хеш-таблиці може
виникнути колізія. При вставці елементу необхідно знайти порожню клітинку; а при
вибірці елемента, його фактичне місце розташування повинно бути знайдено, якщо його
немає в очікуваній позиції. Раніше ми коротко розглянули дваметода дозволу
колізій – лінійну і квадратичну послідовність проб. Клас
Hashtable використовує інший метод, званий повторним хешування
(Rehasing). У деяких джерелах цей метод називають подвійним хешування
(double hashing).

Повторне хешування працює наступним чином. Нехай є набір
хеш-функцій, H1 H2 …. Hn. При вставці або видобування елемента з хеш-таблиці
спочатку використовується хеш-функція H1. Якщо в результаті ми отримуємо колізію,
то далі пробується функція H2 і т.д. до Hn. У попередньому розділі я
продемонстрував лише одну хеш-функцію-нехай вона буде початковій хеш-функцією
(H1). Решта хеш-функції будуть схожі на H1, відрізняючись від неї лише множником
k. Тобто k-я хеш-функція Hk визначена так:

Hk (key) = [GetHash (key) + k * (1 + (((GetHash (key)>> 5) + 1)% (hashsize – 1)))]% hashsize

Математичне примітка У разі повторного хешування важливо, щоб
кожна клітинка хеш-таблиця була відвідана рівно 1 раз після hashsize проб. Те
Тобто, для кожного ключа ми не хочемо, щоб функції Hi і Hj видавали одне і те ж
значення хешу. У разі хеш-функцій класу Hashtable це властивість
виконується, якщо результат обчислення (1 + (((GetHash (key)>> 5) + 1)%
(Hashsize – 1)) і hashsize взаємно прості. (Два числа називаються взаємно
простими, якщо вони не мають спільних дільників крім одиниці). Ці двачісла будуть
гарантовано взаємно прості, якщо hashsize – просте число.

Повторне хешування забезпечує краще уникнення колізій, ніж лінійна і
квадратична послідовності проб.

Рівень заповнення та розширення хеш-таблиці


Клас Hashtable містить закриту (private) змінну
loadFactor (Рівень заповнення), в якій задається максимальне
співвідношення числа елементів, які можуть зберігатися в хеш-таблиці до загального
числу її осередків (slots). Наприклад, якщо loadFactor дорівнює 0,5, то це
означає, що не більше ніж половина осередків хеш-таблиці може бути заповнена
даними. Решта половина осередків при цьому будуть порожніми.

В одній з переобтяжених форм конструктора хеш-таблиці ви можете задавати
значення loadFactor від 0.1 до 1.0. При цьому, однак, незалежно від того,
яке значення цієї змінної ви задасте, воно буде автоматично зменшене до
72 відсотків, так що навіть якщо ви задасте це значення дорівнює 1,0, то на самому
справі рівень заповнення хеш-таблиці все одно буде дорівнює 0,72. У Microsoft
дослідним шляхом встановили, що 0,72 є оптимальним рівнем заповнення
хеш-таблиці, так що рекомендується використовувати значення рівня заповнення по
замовчуванням 1.0 (яке при цьому автоматично встановлюється в 0,72 –
так, це звучить заплутано, але що поробиш).

Примітка Я витратив кілька днів, задаючи питання в різних
форумах і хлопцям з Microsoft чому застосовується таке автоматичне
перетворення рівня заповнення. Мені було цікаво, чому вони вирішили не
робити діапазон допустимих значень рівня заповнення від 0.072 до 0.72. В кінці
решт я добрався до тієї команди в Microsoft, яка працювала над реалізацією
класу Hashtable і вони поділилися зі мною причинами такого рішення. А
саме, в процесі тестування вони виявили, що при рівні заповнення більше
0.72 продуктивність різко падала. Вони вирішили, що розробнику, який
буде використовувати клас Hashtable краще не забивати собі голову таким дивним
числом як 0.72, замість цього йому досить пам'ятати, що рівень заповнення 1.0
дає найкращий результат. Таким чином, таке рішення, трохи жертвує
функціональністю, зате робить структуру даних більш простий у використанні і
принесе менше головного болю спільноті розробників.

Кожного разу при додаванні елемента в хеш-таблицю відбувається перевірка, чи не
перевершує чи рівень заповнення заданого значення. Якщо цей факт має
місце, то хеш-таблиця розширюється (is expanded). Розширення відбувається в два
етапи:


  1. Число осередків хеш-таблиці приблизно подвоюється. Більш точно, кількість осередків
    збільшується з поточного простого числа до наступного простого числа,
    що зберігається у внутрішній таблиці is (згадаємо, що для належної роботи
    процесу повторного хешування необхідно, щоб розмір хеш-табліцибил простим
    числом)
  2. Оскільки у випадку повторного хешування значення хеш-функцій залежить від
    розміру хеш-таблиці, всі значення хеш-функцій для елементів даних хеш-таблиці
    обчислюються заново (оскільки розмір хеш-таблиці був змінений на першому етапі).

На щастя, клас Hashtable приховує від розробника всю складність
методу Add(), Так що в реальності вам не доведеться турбуватися про всі
цих деталях.

Від рівня заповнення залежить розмір хеш-таблиці і число проб при
виникненні колізій. Великий рівень заповнення, при якому елементи
розташовані в хеш-таблиці досить щільно, використовує менше пам'яті, але
вимагає більшого числа проб, ніж розріджена хеш-таблиця. Не вдаючись у
математичні деталі, відзначимо лише, що очікувана кількість проб, яка
необхідно буде здійснити при виникненні колізії, не перевищує 1 / (1 –
lf), де lf – рівень заповнення.

Як вже говорилося, в Microsoft налаштували хеш-таблицю на використання по
замовчуванням рівня заповнення 0,72. Отже, в середньому при виникненні
колізії буде здійснюватися 3.5 проби. Оскільки ця оцінка не залежить від
числа осередків хеш-таблиці, то асимптотичну час доступу хеш-таблиці одно
O (1), що звичайно ж краще, ніж O (n) – час пошуку в відсортованого масиву.

Нарешті, важливо розуміти, що розширення хеш-таблиці далеко не дешева
операція. Поетом перед створенням хеш-таблиці краще за все оцінити число
елементів, які будуть у ній зберігатися і вибрати відповідним чином
розмір хеш-таблиці, щоб уникнути зайвих розширень.

Висновок


У цій статті ми розглянули три структури даних, підтримуваних бібліотекою
класів. NET Framework:


Черга і стек за своїми можливостями подібні ArrayList-у, оскільки вони можуть
зберігати проізольное число об'єктів будь-якого типу. Відмінність черги і стека від
ArrayList-а полягає у тому, що ArrayList дозволяє доступаться до її елементів у
довільному порядку, в той час як і черга, і стек накладають обмеження
на порядок доступу до своїх елементах.

Черга – це структура даних типу FIFO = First In, First Out. Тобто порядок
вилучення елементів з черги буде таким же як і порядок їх додати до
чергу. To Для цих цілей чергу надає два методи: Enqueue () і
Dequeue (). Черги корисні для обробки завдань або інших ситуацій, коли
елементи повинні оброблятися в порядку їхнього приходу.

Модель доступу до даних стека називається LIFO = Last In, First Out. Така схема
доступу реалізована в стеку за допомогою методів Push () і Pop (). Стеки часто
використовуються в різних областях computer scienceот виконання коду до
синтаксичного розбору.

І, нарешті, ми розглянули структуру даних під назвою хеш-таблиця.
Хеш-таблиця розширює поняття масиву, дозволяючи індексувати свої елементи
за допомогою ключа довільного типу, а не тільки порядковим значенням. Якщо ви
плануєте здійснювати пошук в масиві по деякому унікальному ключу, то
замість масиву набагато більш ефективно буде використовувати хеш-таблицю,
оскільки пошук у цьому випадку здійснюється за константне, а не за лінійне
час.

На цьому ми закінчуємо другу статтю нашої серії. У третій частині ми
розглянемо двійкові дерева пошуку-структуру даних, яка дає
логарифмічне час пошуку – O (log n). Подібно хеш-таблицях, двійкові дерева
пошуку ідеально підходять, якщо ви знаєте, що вам доведеться часто здійснювати
пошук даних.

До наступного разу, Щасливого Програмування!

Література



Скотт Мітчелл, Автор п'яти книг і засновник 4GuysFromRolla.com, на
Протягом останніх п'яти років працював з веб-технологіями Microsoft. Скотт
працює незалежним консультантом, викладачем і письменником. Нещодавно він
отримав ступінь магістра Computer Science в Каліфорнійському університеті
(University of California), Сан-Дієго. Зв'язатися з ним можна за адресою mitchell@4guysfromrolla.com.

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*