Struktury danych w C#

Część 2. Kolejka, stos i tablica z haszowaniem

Scott Mitchell
4GuysFromRolla.com

listopad 2003

Streszczenie
Artykuł ten to druga część sześcioczęściowej serii dotyczącej struktur danych na platformie .NET. Przedstawiono w nim trzy najczęściej używane struktury: kolejkę, stos i tablicę z haszowaniem. Z artykułu tego dowiemy się, że kolejka i stos — wyspecjalizowane obiekty ArrayList — pozwalają na przechowywanie zmiennej liczby elementów, lecz do tych elementów można uzyskać dostęp jedynie w z góry określonej kolejności. Tablica z haszowaniem działa podobnie jak zwykła tablica, jednak charakteryzuje się lepszym indeksowaniem. W zwykłych tablicach wymagane jest, aby elementy były indeksowane liczbami porządkowymi, natomiast w tablicach z haszowaniem elementy mogą być indeksowane dowolnymi obiektami.
(19 stron drukowanych)

Spis treści

Wprowadzenie
Szeregowanie zadań zgodnie z algorytmem „pierwszy przyszedł — pierwszy obsłużony”
Struktura stosu, czyli szeregowanie typu „pierwszy przyszedł — ostatni obsłużony”
Ograniczenia indeksowania bezpośredniego
Klasa System.Collections.Hashtable
Podsumowanie

Wprowadzenie

W części 1. pod nazwą Struktury danych — wprowadzenie rozważaliśmy, czym są struktury danych, w jaki sposób można sprawdzić ich wydajność oraz jaką rolę odgrywa wydajność w wyborze odpowiedniego algorytmu. Oprócz poznania podstawowych zagadnień dotyczących struktur danych i ich analizy, przyjrzeliśmy się także najczęściej stosowanej strukturze danych — tablicy.

W tablicy przechowywany jest zbiór jednorodnych elementów, które są indeksowane liczbami porządkowymi. Zawartość tablicy jest zaalokowana jako ciągły blok pamięci, dzięki czemu odczyt i zapis konkretnego elementu wykonywany jest bardzo szybko.

Tablice mają dwie wady — jednorodność elementów oraz konieczność definiowania rozmiaru tablicy przy jej tworzeniu. Ograniczenia te można ominąć, stosując dostępną w bibliotece klas bazowych platformy.NET Framework strukturę danych ArrayList, która umożliwia przechowywanie niejednorodnych obiektów i nie wymaga jawnego definiowania rozmiaru tablicy. Jak opisałem to już w poprzednim artykule, ArrayList wykorzystuje tablicę elementów typu object. W każdym wywołaniu metody Add() klasy ArrayList następuje sprawdzenie, czy w wewnętrznej tablicy typu object jest jeszcze miejsce na nowe elementy. Jeśli nie, rozmiar tablicy jest automatycznie podwajany.

W tym artykule będziemy kontynuować naszą analizę tablicowych struktur danych. Zaczniemy od kolejki i stosu. W strukturach tych także przechowywane są ciągłe bloki niejednorodnych elementów (tak jak w ArrayList). Jednak w przypadku kolejki i stosu dostęp do przechowywanych obiektów jest w pewnym stopniu ograniczony.

Po omówieniu kolejki i stosu przejdziemy do tablicy z haszowaniem. Tablica z haszowaniem (czasami nazywana tablicą asocjacyjną) służy do przechowywania kolekcji niejednorodnych elementów, ale jej elementy — w przeciwieństwie elementów zwykłych tablic, indeksowanych liczbami porządkowymi — indeksowane są obiektami dowolnego typu (np. string).

Szeregowanie zadań zgodnie z algorytmem „pierwszy przyszedł — pierwszy obsłużony”

Przy tworzeniu dowolnej usługi — to jest programu, który otrzymuje z wielu źródeł wiele żądań wykonania jakiegoś zadania — wyzwaniem staje się podjęcie decyzji o sposobie, w jaki żądania te będą obsługiwane. Dwa najczęściej stosowane rozwiązania to:

• pierwszy przyszedł — pierwszy obsłużony,

• przetwarzanie priorytetowe.

Pierwszy przyszedł — pierwszy obsłużony to sposób planowania realizacji zadań stosowany na przykład w sklepie spożywczym, banku czy w fabryce samochodów. Osoby oczekujące na obsługę ustawiają się w kolejkę. Ludzie, którzy znajdują się w kolejce przed tobą, zostaną obsłużeni przed tobą. Ludzie, którzy znajdują się w kolejce za tobą, zostaną obsłużeni po tobie. W przypadku przetwarzania priorytetowego najpierw realizowane są zadania o wysokim priorytecie, a dopiero później zadania o niższym priorytecie. Na przykład w szpitalnej izbie przyjęć pomoc zostanie udzielona najpierw osobom w stanie krytycznym, a dopiero później osobom w mniej poważnym stanie — niezależnie od tego, który pacjent przyjechał pierwszy.

Załóżmy, że chcemy utworzyć usługę komputerową, która będzie obsługiwać żądania w kolejności ich otrzymywania. Kolejne żądania mogą być nadsyłane szybciej, niż jesteśmy w stanie je obsłużyć, dlatego potrzebny jest bufor, w którym moglibyśmy je umieszczać, zapamiętując jednocześnie porządek, w jakim zostały nadesłane.

Jednym z możliwych rozwiązań jest zastosowanie tablicy ArrayList oraz zmiennej całkowitej o nazwie nextJobPos, w której zapisywana będzie pozycja następnego zadania do wykonania. Gdy nadejdzie żądanie wykonania nowego zadania, po prostu wywołujemy metodę Add() tablicy ArrayList, aby ustawić to zadanie na koniec tablicy ArrayList. Gdy jesteśmy gotowi, by przetworzyć kolejne zadanie z bufora, odczytujemy z tablicy ArrayList element o indeksie nextJobPos i zwiększamy wartość nextJobPos. Rozwiązanie to zilustrowane jest przez następujący kod:

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 "BRAK ZADAŃ W BUFORZE ";

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());

}

}

W wyniku wykonania powyższego programu uzyskamy następujący rezultat:

1

2

3

BRAK ZADAŃ W BUFORZE

BRAK ZADAŃ W BUFORZE

4

Jest to nieskomplikowane rozwiązanie — niestety jest także bardzo nieefektywne. Przede wszystkim tablica ArrayList stale rośnie wraz z każdym nowym zadaniem dodanym do bufora — nawet jeśli zadania są wykonywane natychmiast po dodaniu ich do bufora. Zastanówmy się nad sytuacją, gdy co sekundę do bufora jest dodawane nowe zadanie, natychmiast przetwarzane i usuwane z bufora. Oznacza to, że co sekundę wywoływana jest metoda AddJob(), która z kolei wywołuje metodę Add() tablicy ArrayList. Metoda Add() jest regularnie wywoływana i w miarę zapełniania się tablicy ArrayList podwajany jest rozmiar jej wewnętrznej tablicy. Po pięciu minutach (300 sekund) wewnętrzna tablica ma rozmiar 512 elementów — mimo że w buforze nigdy nie znajdował się więcej niż jeden element! Oczywiście ta tendencja ma miejsce przez cały czas działania programu i zgłaszania nowych zadań.

Przyczyną rozrostu tablicy ArrayList do tak absurdalnych rozmiarów jest to, że nie następuje odzyskanie miejsca w buforze, zwolnionego przez zrealizowane zadania. Po tym, jak pierwsze zadanie zostaje dodane do bufora i przetworzone, miejsce po nim w ArrayList jest gotowe do ponownego użycia. Rozważmy rozkład zadań przedstawiony w poprzednim fragmencie kodu. Po pierwszych dwóch liniach kodu — AddJob("1")i AddJob("2") — tablica ArrayList będzie wyglądała tak, jak na rysunku poniżej.

Ilustracja 1. ArrayList po wykonaniu pierwszych dwóch linii kodu

Zauważmy, że w tym momencie tablica ArrayList ma rozmiar 16, ponieważ domyślnie w trakcie inicjalizacji klasa ArrayList tworzy wewnętrzną tablicę 16 elementów typu object. Następnie wywoływana jest metoda GetNextJob(), która realizuje (usuwa) pierwsze zadanie. Po jej wywołaniu tablica ArrayList wygląda tak, jak na ilustracji 2.

Ilustracja 2. Tablica po wywołaniu metody GetNextJob()

Wykonanie kolejnej linii kodu — AddJob("3") — powoduje dodanie do bufora kolejnego zadania. Pierwszy element ArrayList (indeks 0) nie jest zajęty. Z początku może wydawać się, że wstawienie trzeciego zadania na miejsce o indeksie 0 jest dobrym rozwiązaniem. Jednak możemy szybko o tym zapomnieć, jeśli rozważymy przypadek, w którym po wywołaniu AddJob("3") wywołalibyśmy AddJob("4"), a następnie dwa razy wywołalibyśmy funkcję GetNextJob(). Jeśli wstawilibyśmy trzecie zadanie na miejsce o indeksie 0, a czwarte zadanie na miejsce o indeksie 2, sytuacja wyglądałaby tak, jak na ilustracji 3.

Ilustracja 3. Sytuacja po wstawieniu zadania na miejsce o indeksie 0

Wywołanie funkcji GetNextJob() spowoduje usunięcie z bufora drugiego zadania i ustawienie zmiennej nextJobPos tak, by wskazywała indeks 2. Po kolejnym wywołaniu funkcji GetNextJob(),zostanie wykonane czwarte zadanie i usunięte z bufora przed trzecim zadaniem, co narusza szeregowanie pierwszy przyszedł — pierwszy obsłużony, które chcieliśmy zastosować.

Sedno problemu tkwi w tym, że ArrayList reprezentuje listę zadań w porządku liniowym. Dlatego — aby zagwarantować odpowiednią kolejność wykonywania zadań — nowe zadania należy dodawać na prawo od starych zadań. Gdy dojdziemy do końca tablicy ArrayList, jej rozmiar jest podwajany ze względu na kolejne wywołania funkcji GetNextJob(), nawet jeśli w tablicy znajdują się wolne miejsca.

Problem ten można rozwiązać, przekształcając tablicę ArrayList w tablicę cykliczną. Tablica cykliczna charakteryzuje się tym, że nie ma ani określonego początku, ani określonego końca. Początek i koniec tablicy należy zapamiętać w osobnych zmiennych. Graficzną reprezentację tablicy cyklicznej przedstawiono na ilustracji 4.

Ilustracja 4. Przykład tablicy cyklicznej

W przypadku tablicy cyklicznej, metoda AddJob() dodaje nowe zadanie w pozycji wskazywanej przez endPos i następnie „zwiększa” wartość endPos. Metoda GetNextJob() pobiera do realizacji zadanie wskazywane przez startPos, na jego miejsce w tabeli wstawia wartość null , a następnie „zwiększa” wartość startPos. Wyraz zwiększa napisałem w cudzysłowie, ponieważ w tym przypadku operacja jest nieco bardziej skomplikowana niż zwykłe dodawanie jedynki do wartości zmiennej. Aby przekonać się, dlaczego nie możemy po prostu dodać 1, rozważmy przypadek, w którym wartość endPos wynosi 15. Jeśli zwiększlibyśmy endPos o 1, zmienna miałaby wartość 16. Przy następnym wywołaniu metody AddJob() program próbowałby odwołać się do elementu o indeksie 16, co spowodowałoby wyjątek IndexOutOfRangeException.

Dlatego gdy zmienna endPos ma wartość 15, zerujemy ją, zamiast zwiększać jej wartość o jeden. Takie zwiększenie możemy zaimplementować jako funkcję increment(zmienna), która sprawdza, czy przekazana zmienna ma wartość równą rozmiarowi tablicy i jeśli tak jest — ustawia jej wartość na 0. Innym rozwiązaniem jest zwiększanie wartości o jeden, a następnie obliczenie reszty z dzielenia przez rozmiar tablicy. W takim przypadku kod funkcji increment() wyglądałby następująco:

int increment(int variable)

{

return (variable + 1) % theArray.Length;

}

Uwaga   Operator modulo (%), stosowany w wyrażeniu x % y, powoduje obliczenie reszty z dzielenia x przez y. Wynik zawsze ma wartość z przedziału [0; y - 1].

Rozwiązanie to świetnie się sprawdza, jeśli w naszym buforze nigdy nie będzie więcej niż 16 zadań. Jednak co się stanie, jeśli do bufora będziemy chcieli dodać kolejne zadanie w sytuacji, gdy wszystkie 16 miejsc będzie zapełnione? Tak samo jak w przypadku metody Add() obiektu ArrayList, będziemy musieli zwiększyć rozmiar tablicy — na przykład podwajając go.

Klasa System.Collections.Queue

Opisana wyżej funkcjonalność — dodawanie i usuwanie elementów z bufora w porządku „pierwszy przyszedł — pierwszy obsłużony” oraz dużo lepsze wykorzystanie pamięci — zapewniana jest przez standardową strukturę danych nazywaną kolejką. Biblioteka klas bazowych środowiska .NET Framework zawiera klasę kolejki — System.Collections.Queue. W zamieszczonym powyżej kodzie w celu dodania elementu i jego usunięcia wykorzystywane są funkcje AddJob() i GetNextJob(), natomiast w klasie Queue zadania te można wykonać za pomocą metod Enqueue() i Dequeue().

Implementacja klasy Queue wykorzystuje wewnętrzną tablicę cykliczną elementów typu object oraz dwie zmienne, które są wskaźnikami na początek i koniec tablicy — head (głowa kolejki) i tail (ogon kolejki). Domyślny rozmiar kolejki wynosi 32 elementy, jednak można go samodzielnie zdefiniować, podając właściwy rozmiar w wywołaniu konstruktora. Kolejka wykorzystuje tablicę elementów typu object, dlatego można w niej przechowywać zmienne każdego typu.

Metoda Enqueue() sprawdza, czy tablica może pomieścić kolejny element. Jeśli tak — dodaje nowy element na miejsce wskazywane przez indeks tail i „zwiększa” indeks tail metodą wykorzystującą operator modulo (dzięki temu indeks tail nie przekroczy rozmiaru tablicy wewnętrznej). Jeśli w tablicy brakuje miejsca, jej rozmiar jest mnożony przez określony współczynnik wzrostu. Jego standardowa wartość wynosi 2.0, można jednak przy wywoływaniu konstruktora klasy Queue podać inną wartość.

Metoda Dequeue() zwraca element określany jako głowa kolejki (element wskazywany przez indeks head). Następnie na miejsce w tablicy o indeksie head wstawia wartość null i „zwiększa” indeks head. Pierwszy element w kolejce można także tylko sprawdzić, nie usuwając go z kolejki — służy do tego metoda Peek().

Klasa Queue — w przeciwieństwie do klasy ArrayList — nie pozwala na dowolny dostęp do umieszczonych w niej elementów. Oznacza to, że nie można uzyskać dostępu do trzeciego elementu w kolejce bez uprzedniego wyjęcia z kolejki dwóch pierwszych elementów. Klasa Queue zawiera jednak metodę Contains(), która umożliwia sprawdzenie, czy szukany obiekt znajduje się w kolejce, czy nie. Jeśli wiadomo, że będzie potrzebny swobodny dostęp do elementów, kolejka nie jest dobrym rozwiązaniem. W takim przypadku należy zastosować tablicę ArrayList. Kolejka jest idealnym rozwiązaniem w sytuacjach, w których ważne jest zachowanie kolejności otrzymywania elementów.

Uwaga   Kolejki czasem nazywane są także strukturami danych typu FIFO. FIFO to skrót od wyrażenia „First In, First Out” (pierwszy przyszedł — pierwszy wyszedł).

Struktura stosu, czyli szeregowanie typu „pierwszy przyszedł — ostatni obsłużony”

Kolejka to struktura danych umożliwiająca dostęp do elementów w kolejności pierwszy przyszedł — pierwszy obsłużony. W tym celu wykorzystywana jest wewnętrzna tablica cykliczna elementów typu object oraz metody Enqueue() i Dequque(). Szeregowanie typu pierwszy przyszedł — pierwszy obsłużony ma wiele zastosowań, głównie w usługach takich jak serwer WWW, kolejkowanie wydruków oraz w innych programach, obsługujących wiele żądań.

Innym popularnym sposobem szeregowania zadań jest pierwszy przyszedł — ostatni obsłużony. Struktura danych, umożliwiająca taką formę dostępu do elementów, to stos. Biblioteka klas bazowych środowiska .NET Framework zawiera klasę System.Collections.Stack, która — tak jak klasa Queue — przechowuje elementy w cyklicznej tablicy elementów typu object. Stos obsługiwany jest za pomocą dwóch metod — metody Push(item), umożliwiającej wstawienie elementu na stos oraz metody Pop() powodującej usunięcie oraz zwrócenie elementu ze szczytu stosu.

Graficznie stos można przedstawić jako pionowy zbiór elementów. Umieszczany na stosie element kładziony jest na szczycie stosu. Ściągnięcie elementu ze stosu polega na zdjęciu elementu znajdującego się na szczycie stosu. Zamieszczone poniżej dwa rysunki przedstawiają stos po dodaniu do niego elementów o numerach 1,2 i 3 oraz po ściągnięciu ich.

Ilustracja 5. Stos z trzema elementami

Ilustracja 6. Stos po ściągnięciu trzech elementów

Domyślna pojemność stosu (klasa Stack) wynosi 10 elementów, w przeciwieństwie do 32 elementów w przypadku kolejki (klasa Queue). Tak samo, jak w przypadku klas Queue i ArrayList, pojemność stosu można określić przy wywoływaniu konstruktora. Podobnie jak w klasie ArrayList, gdy pojemność wewnętrznej tablicy musi zostać zwiększona, jej rozmiar jest podwajany (jednak w przypadku kolejki w konstruktorze można było również zdefiniować współczynnik wzrostu).

Uwaga   Stosy określa się również strukturami danych typu LIFO (Last In, First Out).

Stos — częsta metafora w języku informatycznym

Mówiąc o kolejkach, można przytoczyć dużo przykładów z rzeczywistego świata — kolejki w urzędzie, szeregowanie zadań wydruku itd. Niestety, trudniej jest wymyślić przykłady z życia odwzorowujące działanie stosu. Jest on jednak bardzo popularną strukturą danych, stosowaną w wielu różnych aplikacjach komputerowych.

Wystarczy przyjrzeć się jakiemuś językowi programowania wyższego poziomu — na przykład językowi C#. Po uruchomieniu programu napisanego w C#, środowisko CLR tworzy stos wywołań (call stack), na którym zapisywane są wszystkie wywołania funkcji. Za każdym razem, gdy wywoływana jest jakaś funkcja, jej dane odkładane są na stos. Po zakończeniu wykonywania funkcji, jej dane ściągane są ze stosu wywołań. Informacje na samym szczycie stosu należą do aktualnie działającej funkcji. Aby zobaczyć wizualną prezentację stosu wywołań, należy utworzyć projekt w Visual Studio® .NET, ustawić w kodzie punkt przerwania (breakpoint) i z menu Debug wybrać polecenie Start. Wykonywanie kodu zatrzyma się na ustawionym punkcie przerwania. Aby wyświetlić okno stosu wywołań, należy wtedy wybrać z menu Debug polecenie Windows, a następnie Call Stack.

Stosy są również powszechnie stosowane przy parsowaniu gramatyk (od prostych wyrażeń algebraicznych po komputerowe języki programowania), jako sposób symulowania rekursji, a nawet w modelach wykonywania instrukcji.

Ograniczenia indeksowania bezpośredniego

W pierwszym artykule tej serii mówiliśmy o tym, że charakterystycznymi cechami zwykłych tablic jest homogeniczność i indeksowanie bezpośrednie. Oznacza to, że do i-tego elementu można uzyskać dostęp (w celu zapisu lub odczytu) w czasie stałym. Czas stały zapisuje się jako O(1).

Rzadko znamy numer pozycji w tablicy, na której znajdują się potrzebne nam dane. Rozważmy na przykład bazę danych pracowników. Pracownika można zidentyfikować na podstawie unikalnego numeru ubezpieczenia, mającego postać DDD-DD-DDDD, gdzie D jest cyfrą (0 - 9). Jeśli dane pracowników zapisano w losowej kolejności w jednej tablicy, to znalezienie danych pracownika o numerze ubezpieczenia 111-22-3333 wymagałoby przeszukania całej tablicy — złożoność obliczeniowa tej operacji wynosi O(n). Lepszym rozwiązaniem byłoby wstępne posortowanie tablicy według numeru ubezpieczenia, co zredukowałoby złożoność obliczeniową operacji wyszukiwania do O(log n).

Najlepiej jednak byłoby dostać się do rekordu pracownika w czasie O(1). Taki czas dostępu można uzyskać tworząc ogromną tablicę z taką liczbą elementów, by zmieściły się w niej wszystkie możliwe numery ubezpieczenia. Tablica taka zaczynałaby się wtedy od elementu o numerze 000-00-0000, a kończyła na elemencie o numerze 999-99-9999, jak pokazano na rysunku poniżej:

Ilustracja 7. Tablica zawierająca wszystkie możliwe elementy dla 9-cyfrowego numeru ubezpieczenia

Jak pokazano na ilustracji, każdy rekord pracownika zawiera informacje takie jak nazwisko, numer telefonu, wysokość wynagrodzenia itp. Tablica jest indeksowana jest liczbami odpowiadającymi numerom ubezpieczenia pracowników. Dzięki takiemu rozwiązaniu do danych konkretnego pracownika można uzyskać dostęp w stałym czasie. Wadą takiego rozwiązania jest ogromne marnotrawstwo pamięci — wszystkich numerów ubezpieczenia jest dokładnie 10⁹, czyli tablica ma jeden miliard (1.000.000.000) elementów. Jeśli firma zatrudnia 1.000 osób, to wykorzystywane będzie tylko 0,0001% miejsc w tablicy. Dla porównania, firma musiałaby zatrudnić około jedną szóstą populacji świata, aby prawie zapełnić tę tablicę.

Kompresja indeksowania bezpośredniego za pomocą funkcji haszującej

Oczywiście niedopuszczalne jest tworzenie tablicy mogącej pomieścić milion elementów tylko po to, by przechowywać w niej informacje o 1.000 pracowników. Jednak możliwość dostępu w stałym czasie do danych konkretnego pracownika jest wysoce pożądana. Jednym z możliwych rozwiązań jest skrócenie numeru ubezpieczenia pracownika do czterech ostatnich cyfr. Dzięki temu indeksy tablicy nie należałyby do zakresu od 000-00-0000 do 999-99-9999, tylko do zakresu 0000 - 9999. Na ilustracji 8. przedstawiono zmniejszoną tablicę pracowników.

Ilustracja 8. Zmniejszona tablica

Takie podejście zapewnia stały czas dostępu do rekordów oraz dużo lepsze wykorzystanie pamięci. Nie ma znaczenia, czy wybierzemy cztery ostatnie cyfry numeru ubezpieczenia, cztery cyfry środkowe, czy cyfrę pierwszą, trzecią ósmą i dziewiątą.

Matematyczne przekształcenie dziewięciocyfrowego numeru ubezpieczenia na liczbę czterocyfrową nazywa się haszowaniem. Tablica, która wykorzystuje haszowanie do zmniejszenia zakresu indeksowania, nazywa się tablicą z haszowaniem.

Funkcja haszująca jest funkcją odpowiedzialną za haszowanie. W przypadku naszego przykładu, funkcję haszującą można przedstawić w następujący sposób:

H(x) = ostatnie cztery cyfry z x

Danymi wejściowymi funkcji H może być dowolna liczba dziewięciocyfrowa, reprezentująca numer ubezpieczenia, a wynikiem jej działania będzie liczba czterocyfrowa, utworzona z czterech ostatnich cyfr liczby dziewięciocyfrowej. Stosując terminologię matematyczną można powiedzieć, że funkcja H odwzorowuje zbiór dziewięciocyfrowych numerów ubezpieczenia na zbiór numerów czterocyfrowych, co pokazano na ilustracji 9.

Ilustracja 9. Graficzne przedstawienie funkcji haszującej

Na ilustracji 9. zobrazowano także kolizje, które mogą wystąpić w przypadku każdej funkcji haszującej. Przy odwzorowywaniu większego zbioru na mniejszy nie ma takiej funkcji haszującej, która dwóm elementom większego zbioru nie przyporządkowałaby tej samej wartości w zbiorze mniejszym. W naszym przykładzie wszystkie numery ubezpieczenia kończące się cyframi 0000 zostaną przekształcone na liczbę 0000. Oznacza to, że wynik haszowania wartości takich jak 000-00-0000, 113-14-0000, 933-66-0000 oraz wielu innych będzie wynosił 0000.

Wracając do wcześniejszego przykładu rozważmy, co by się stało, gdyby zatrudniono nowego pracownika o numerze ubezpieczenia 123-00-0191. Dodanie tego pracownika do bazy stanowi problemem, ponieważ w tablicy na pozycji 0191 wpisany jest już jakiś pracownik (Jisun Lee).

Uwaga matematyczna   Za pomocą terminologii matematycznej funkcję haszującą można opisać jako funkcję f : A -> B. Dopóki |A| > |B|, to funkcja f nie jest funkcją różnowartościową i kolizje będą występować.

Występowanie kolizji może stanowić poważny problem. W następnej sekcji przyjrzymy się powiązaniu funkcji haszującej z występowaniem kolizji, a następnie zajmiemy się sposobami radzenia sobie z kolizjami. Później przejdziemy do tematu klasy System.Collections.Hashtable, w której zaimplementowano tablicę z haszowaniem. Przyjrzymy się funkcji haszującej wykorzystywanej w klasie Hashtable, sposobom rozwiązywania kolizji oraz paru przykładom zastosowania klasy Hashtable w praktyce.

Unikanie kolizji oraz ich rozwiązywanie

Podczas dodawania danych do tablicy z haszowaniem wystąpienie kolizji może popsuć całą operację. Jeśli nie wystąpi kolizja, możemy normalnie umieścić dane w tablicy na pozycji o indeksie wskazanym przez funkcję haszującą. Jeśli jednak wystąpi kolizja, musimy znaleźć jakieś inne rozwiązanie. Ze względu na zwiększeniem kosztów działania w przypadku wystąpienia kolizji, naszym celem powinno być unikanie ich.

Częstość występowania kolizji jest bezpośrednio związana z zastosowaną funkcją haszującą oraz różnorodnością danych podawanych na wejściu funkcji haszującej. Zakładając, że numery ubezpieczenia nadawane są losowo, użycie ostatnich czterech cyfr numeru ubezpieczenia jest idealną funkcją haszującą. Jeśli jednak numery ubezpieczenia przyznawane są w taki sposób, że urodzeni w tym samym roku lub w tym samym miejscu będą mieli podobne cztery ostatnie cyfry, to kolizje wystąpią z większym prawdopodobieństwem, szczególnie w przypadku, gdy daty i miejsca urodzenia pracowników nie są zróżnicowane.

Uwaga   Gruntowna analiza wyników uzyskiwanych z funkcji haszujących wymaga znajomości statystyki, co wykracza poza tematykę tego artykułu. Najważniejsze jest zapewnienie, by prawdopodobieństwo odwzorowania dowolnej wartości na konkretny indeks w tablicy z haszowaniem, w której jest miejsce na k elementów, wynosiło mniej niż 1/k (nie przejmuj się, jeśli tego nie rozumiesz ;-).

Wybór odpowiedniej funkcji haszującej ma ogromny wpływ na możliwość uniknięcia kolizji. W związku z tym zagadnieniem przeprowadzono wiele badań, ponieważ to, jaką zastosowano funkcję haszującą, ma bardzo duży wpływ na całkowitą wydajność tablicy z haszowaniem. W następnej sekcji przyjrzymy się funkcji haszującej, zastosowanej w klasie Hashtable platformy .NET Framework.

Istnieje kilka strategii postępowania w przypadku wystąpienia kolizji. Zadanie, które trzeba wykonać, określane mianem rozwiązywania kolizji, polega na znalezieniu innego miejsca dla elementu, gdy pierwsza znaleziona pozycja jest już zajęta. Jednym z najprostszych rozwiązań jest adresowanie liniowe, które działa w następujący sposób:

1. Przy dodawaniu nowego elementu do tablicy z haszowaniem określ za pomocą funkcji haszującej pozycję docelową tego elementu.

2. Sprawdź, czy miejsce to nie jest już zajęte przez inny element. Jeśli jest puste, umieść tam element i zakończ działanie funkcji. Jeśli miejsce było zajęte, przejdź do punktu trzeciego.

3. Jeśli miejsce wskazywane przez funkcję haszującą to i, sprawdź, czy pozycja i + 1 jest wolna. Jeśli jest również zajęta, sprawdź pozycję i + 2 i tak dalej, dopóki nie znajdziesz wolnej pozycji.

Rozważmy przypadek, w którym do tablicy z haszowaniem zostali wpisani następujący czterej pracownicy: Alice (333-33-1234), Bob (444-44-1234), Cal (555-55-1237), Danny (000-00-1235) i Edward (111-00-1235). Po dodaniu ich rekordów tablica będzie wyglądała w następujący sposób:

Ilustracja 10. Tablica z haszowaniem zawierająca czterech pracowników o podobnych numerach ubezpieczenia

Numer ubezpieczenia Alice po haszowaniu to 1234, tak więc jej rekord zostaje wpisany na pozycji 1234. Numer Boba po haszowaniu także wynosi 1234, lecz na tej pozycji znajduje się już rekord Alice, dlatego rekord Boba zostanie wpisany na następnej pozycji — czyli pod numerem 1235. Następny pracownik po Bobie to Cal. Jego numer ubezpieczenia po haszowaniu to 1237. Pozycja o tym indeksie jest wolna, więc umieszczamy w niej rekord Cala. Następny jest Danny; jego numer po haszowaniu to 1235. Pozycja o indeksie 1235 jest już zajęta, więc sprawdzamy pozycję 1236. Ponieważ miejsce to jest wolne — umieszczamy w nim dane Danny'ego. Jako ostatni do tablicy dodawany jest wpis Edwarda. Jego numer po haszowaniu również wynosi 1235. Pozycja o tym indeksie jest już zajęta; sprawdzamy pozycję 1236, ale ona również jest już zajęta. Następnie sprawdzamy pozycję 1237 — jest zajęta przez Cala. Sprawdzamy kolejną pozycje —1238 — jest wolna, więc umieszczamy w niej dane Edwarda.

Kolizje stanowią również problem podczas przeszukiwania tablicy z haszowaniem. Weźmy na przykład tablicę opisaną powyżej i załóżmy, że szukamy danych Edwarda. Bierzemy jego numer ubezpieczenia — 111-00-1235; funkcja haszująca zwraca wartość 1235. Rozpoczynamy poszukiwania i sprawdzamy pozycję o indeksie 1235, jednak w tym miejscu znajdujemy rekord Boba, a nie Edwarda. Musimy więc sprawdzić pozycję o numerze 1236, ale w tym miejscu niestety znajduje się rekord Danny'ego. Liniowe przeszukiwanie kontynuujemy tak długo, aż znajdziemy albo dane Edwarda, albo puste miejsce, co świadczy o tym, że nie istnieje pracownik o numerze ubezpieczenia 111-00-1235.

Adresowanie liniowe jest łatwe w realizacji, ale nie jest dobrą metodą rozwiązywania problemu kolizji, ponieważ prowadzi do grupowania zajętych pozycji. Wyobraźmy sobie przypadek, w którym pierwszych dziesięciu wpisywanych do tablicy pracowników ma numer ubezpieczenia dający po haszowaniu taką samą wartość — na przykład 3344. Oznacza to, że w tablicy będzie zajęte 10 kolejnych pozycji (3344 - 3353). Grupa tych rekordów będzie wymagała adresowania liniowego za każdym razem, gdy będzie poszukiwany jeden z tych 10 rekordów. Co więcej, do tej grupy zostanie dołączony każdy pracownik, którego numer ubezpieczenia po haszowaniu da wartość z zakresu od 3345 do 3353. Aby umożliwić szybkie wyszukiwanie danych w tablicy, dane muszą być rozłożone w tablicy równomiernie, a nie grupować się wokół pewnych punktów.

Bardziej skomplikowana technika adresowania to adresowanie kwadratowe, które polega na sprawdzaniu pozycji odległych od pozycji znalezionej w pierwszej próbie o wartość, będącą podniesionym do kwadratu numerem próby. Czyli jeśli jakaś pozycja jest zajęta, to zamiast sprawdzać miejsca o indeksach s + 1, s + 2 itd. (jak miało to miejsce w przypadku adresowania liniowego), w adresowaniu kwadratowym sprawdzane są pozycje o indeksach s + 1², s - 1², a następnie s + 2², s - 2², s + 3² itd. Niestety adresowanie kwadratowe także może prowadzić do grupowania.

W następnej sekcji zajmiemy się trzecią metodą rozwiązywania kolizji — haszowaniem dwukrotnym, wykorzystywanym również w klasie Hashtable środowiska .NET Framework.

Klasa System.Collections.Hashtable

Klasa Hashtable biblioteki klas bazowych środowiska .NET Framework jest implementacją tablicy z haszowaniem. Przy dodawaniu elementu do tablicy z haszowaniem należy podać nie tylko dany element, ale także unikalny klucz, poprzez który będziemy uzyskiwali dostęp do tego elementu. Zarówno klucz jak i element mogą być obiektami dowolnego typu. W naszym poprzednim przykładzie kluczem jest numer ubezpieczenia pracownika. Do tablicy z haszowaniem elementy dodawane są za pośrednictwem metody Add().

Aby odczytać element z tablicy z haszowaniem, należy podać przyporządkowany elementowi klucz, tak jak w przypadku zwykłej tablicy podaje się liczbę porządkową, będącą indeksem tablicy. Podany niżej kod, napisany w języku C#, służy zaprezentowaniu tej koncepcji. W kodzie do tablicy z haszowaniem dodawane są kolejne elementy, a z każdym elementem związany jest klucz będący ciągiem znaków. Do każdego z dodanych elementów można uzyskać dostęp, podając odpowiedni łańcuch znaków.

using System;

using System.Collections;

public class HashtableDemo

{

private static Hashtable ages = new Hashtable();

public static void Main()

{

// Dodanie elementów do tablicy z haszowaniem,

// każdemu elementowi przypisywany jest łańcuch znaków

ages.Add("Scott", 25);

ages.Add("Sam", 6);

ages.Add("Jisun", 25);

// Uzyskanie dostępu do elementu o podanym kluczu

if (ages.ContainsKey("Scott"))

{

int scottsAge = (int) ages["Scott"];

Console.WriteLine("Scott, lat " + scottsAge.ToString());

}

else

Console.WriteLine("Danych Scotta nie ma w tablicy...");

}

}

W programie zastosowano również metodę ContainsKey(), która zwraca wartość boolowską wskazującą, czy wybrany klucz znajduje się w tablicy z haszowaniem. Klasa Hashtable posiada właściwość Keys, która zwraca zbiór wszystkich kluczy, wykorzystanych w danej tablicy z haszowaniem. Właściwością tą można się posłużyć, jeśli chcemy wypisać wszystkie elementy znajdujące się w tablicy z haszowaniem:

// Przejście przez wszystkie elementy znajdujące się w tablicy z haszowaniem

foreach(string key in ages.Keys)

Console.WriteLine("Wartość ages[\"" + key + "\"] = " + ages[key].ToString());

Kolejność, w jakiej klucze zostały dodane do tablicy, oraz kolejność kluczy w tablicy nie musi być taka sama. Porządek zbioru kluczy zależy od tego, na jakiej pozycji przechowywany jest w tablicy element związany z kluczem. Na przykład wykonanie powyższych fragmentów kodu daje następujący wynik:

Wartość ages["Jisun"] = 25

Wartość ages["Scott"] = 25

Wartość ages["Sam"] = 6

Wynik ten nie zależy od kolejności dodania elementów do tablicy ("Scott", "Sam", "Jisun").

Funkcja haszująca klasy Hashtable

Funkcja haszująca klasy Hashtable jest bardziej skomplikowana niż funkcja używana we wcześniejszym przykładzie z numerem ubezpieczenia. Po pierwsze, pamiętajmy o tym, że funkcja musi zwracać wartość porządkową. W przypadku numeru ubezpieczenia nie stanowiło to żadnego problemu, ponieważ numer ubezpieczenia był liczbą. Funkcja haszująca musiała tylko wyciąć cztery ostatnie cyfry numeru ubezpieczenia. W klasie Hashtable klucz mogą stanowić dane dowolnego typu. W ostatnim przykładzie kluczami były łańcuchy znaków, takie jak „Scott” lub „Sam”. Nic w tym niezwykłego, że w takim przypadku zastanawiamy się, w jaki sposób funkcja haszująca przekształca łańcuch znaków w liczbę.

Ta magiczna transformacja możliwa jest dzięki funkcji GetHashCode(), zdefiniowanej w klasie System.Object. Podstawowa implementacja metody GetHashCode() w klasie Object zwraca unikalną liczbę całkowitą, która nie zmienia się tak długo, jak długo istnieje egzemplarz obiektu. Każdy typ danych dziedziczy bezpośrednio lub pośrednio po typie Object, tak więc każdy element ma dostęp do tej metody. Dlatego każdy łańcuch znaków lub obiekt dowolnego innego typu może być reprezentowany przez unikalny numer identyfikacyjny.

Funkcja haszująca klasy Hashtable zdefiniowana jest w następujący sposób:

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

Domyślnie GetHash(key) zwraca wynik wywołania funkcji GetHashCode(key) (ale przy stosowaniu klasy Hashtable można podać własną funkcję haszującą, którą będzie wskazywać GetHash()). GetHash(key) >> 5 to wynik funkcji haszującej dla zadanego klucza key, przesunięty o 5 bitów w prawo, co jest równoważne podzieleniu wyniku przez 32. Wartość hashsize jest równa liczbie miejsc w tablicy z haszowaniem. Jak pisałem wcześniej, operator % wykorzystywany jest w arytmetyce modularnej (dla przypomnienia x % y jest równe reszcie z działania x / y i wartość ta zawsze należy do zakresu od 0 do y - 1). Dzięki tej końcowej operacji modulo, wartość H(key) zawsze będzie należeć do przedziału od 0 do hashsize - 1. Ponieważ wartość hashsize jest równa rozmiarowi tablicy z haszowaniem, wartość zwracana przez funkcję haszującą H zawsze będzie się znajdowała w dozwolonym przedziale wartości.

Rozwiązywanie kolizji w klasie Hashtable

Podczas umieszczania lub odczytywania elementu z tablicy z haszowaniem mogą wystąpić kolizje. Gdy dodajemy element, musimy znaleźć wolne miejsce. Gdy odczytujemy element z tablicy, musimy go odszukać, jeśli nie znajduje się na pierwszej wyszukanej pozycji. Wcześnie analizowaliśmy dwa sposoby rozwiązywania kolizji — adresowanie liniowe oraz adresowanie kwadratowe. W klasie Hashtable wykorzystano inną technikę, zwaną haszowaniem dwukrotnym (w niektórych źródłach metoda ta nazywana jest rehaszowaniem).

Haszowanie dwukrotne opiera się na istnieniu zbioru różnych funkcji haszujących H₁ - H_n. Podczas dodawania lub odczytywania elementu z tablicy z haszowaniem, początkowo wykorzystuje się funkcję haszującą H₁. Jeśli wynik funkcji H₁ prowadzi do kolizji, sprawdzamy wynik funkcji H₂ i w miarę potrzeby wyniki kolejnych funkcji haszujących aż do H_n. W poprzedniej sekcji przedstawiłem jedną funkcję haszującą — jest to właśnie początkowa funkcja haszująca (H₁). Inne funkcje haszujące są do niej bardzo podobne, różnią się tylko współczynnikiem, przez który mnożona jest część wyrażenia. Mówiąc ogólnie, funkcja haszująca H_k jest zdefiniowana w następujący sposób:

H_k(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)))] % hashsize

Uwaga matematyczna   Przy dwukrotnym haszowaniu ważne jest, by przy wykonywaniu hashsize prób każda pozycja w tablicy z haszowaniem była sprawdzona tylko jeden raz. Oznacza to, że dla danego klucza funkcje H_i i H_j nie powinny wskazać w tablicy tej samej pozycji. W formule dwukrotnego haszowania, wykorzystanej w klasie Hashtable, założenie to będzie spełnione, gdy wynik wyrażenia (1 + (((GetHash(key) >> 5) + 1) % (hashsize - 1)) oraz wartość hashsize są względnie pierwsze. Dwie liczby są względnie pierwsze, jeśli nie mają żadnych wspólnych dzielników poza jedynką. Jeśli hashsize jest liczbą pierwszą, to te dwie liczby na pewno będą względnie pierwsze.

Haszowanie dwukrotne zapewnia skuteczniejsze unikanie kolizji niż adresowanie liniowe oraz kwadratowe.

Współczynnik zapełnienia oraz powiększanie tablicy z haszowaniem

Klasa Hashtable zawiera prywatną zmienną składowa o nazwie loadFactor, która określa stosunek maksymalnej liczby elementów do całkowitej liczby miejsc w tablicy z haszowaniem. Współczynnik zapełnienia loadFactor o wartości 0,5 mówi nam, że w tablicy z haszowaniem można zapełnić co najwyżej połowę miejsc. Oznacza to, że połowa tablicy musi pozostać pusta.

Przeciążony konstruktor klasy Hashtable umożliwia określenie wartości współczynnika zapełnienia loadFactor jako dowolną wartość pomiędzy 0,1 i 1,0. Jednak bez względu na to, jaką wartość z tego zakresu podamy, zastosowany współczynnik zapełnienia będzie wynosił 72% podanej wartości. Jeśli więc podamy wartość 1, to wartość loadFactor będzie wynosiła 0,72. Liczba 0,72 została uznana przez firmę Microsoft za najbardziej optymalny współczynnik zapełnienia, dlatego najlepiej jest podawać domyślną wartość 1,0 (wartość ta zostanie automatycznie przeskalowana na 0,72). Można więc używać nieprzeciążonej wersji konstruktora, która stosuje domyślną wartość 1 (czyli prawdziwy współczynnik zapełnienia będzie wynosił 0,72).

Uwaga   Przez parę dni sondowałem uczestników różnych list dyskusyjnych oraz pracowników Microsoft, dlaczego zastosowano to automatyczne skalowanie. Zastanawiałem się, dlaczego nie zdefiniowano dozwolonego przedziału jako przedziału od 0,072 do 0,72, jeśli wyjściowe wartości i tak miały należeć do tego przedziału. W końcu dotarłem do zespołu, który pracował nad klasą Hashtable i który podzielił się ze mną swoimi przemyśleniami na ten temat. Z badań i testów wynikało, że wszelkie wartości współczynnika zapełnienia większe niż 0,72 znacznie obniżają wydajność tablicy. Zdaniem tego zespołu programiści łatwiej zapamiętają, że optymalną wartością współczynnika jest 1, a nie 0,72. Rozwiązanie to trochę zmniejsza funkcjonalność struktury, ale jednocześnie znacznie ułatwia jej stosowanie, wpływając tym samym na komfort pracy programistów.

Za każdym razem, gdy do obiektu klasy Hashtable dodawany jest nowy element, następuje sprawdzanie, czy operacja ta nie spowoduje przekroczenia dopuszczalnego współczynnika zapełnienia tablicy. Jeśli współczynnik miałby zostać przekroczony, tablica z haszowaniem jest automatycznie powiększana. Powiększanie tablicy odbywa się w dwóch etapach:

1. Liczba pozycji w tablicy z haszowaniem jest w przybliżeniu podwajana. Określając to ściślej, liczba miejsc w wewnętrznej tablicy jest zwiększana z liczby pierwszej, będącej aktualnym rozmiarem tablicy, do kolejnej większej liczby pierwszej (dla przypomnienia — aby haszowanie dwukrotne działało poprawnie, liczba miejsc w tablicy z haszowaniem musi być liczbą pierwszą).

2. Ponieważ wynik dwukrotnego haszowania zależy od liczby wszystkich miejsc w tablicy, należy ponownie wyliczyć za pomocą funkcji haszującej nowe pozycje dla wszystkich wartości wpisanych w tablicy (ze względu na powiększenie rozmiaru tablicy w punkcie pierwszym).

Na szczęście wszystkie te skomplikowane operacje są wykonywane przez klasę Hashtable w ramach metody Add(), dlatego nie musimy przejmować się szczegółami.

Współczynnik zapełnienia wpływa na rozmiar tablicy z haszowaniem oraz spodziewaną liczbę prób w przypadku kolizji. Z wysokim współczynnikiem zapełnienia, zezwalającym na względne zagęszczenie tablicy, związane jest mniejsze zapotrzebowanie na pamięć, ale z drugiej strony związana jest z nim większa liczba prób w przypadku kolizji. Spodziewana liczba prób w przypadku kolizji wynosi 1 / (1 - lf), gdzie lf jest współczynnikiem zapełnienia.

Jak wspomniałem wcześniej, Microsoft ustalił standardową wartość współczynnika zapełnienia na 0,72. Dlatego w przypadku kolizji można spodziewać się 3,5 kolejnych prób. Ponieważ szacowania te nie zależą od liczby elementów zapisanych w tablicy, asymptotyczna złożoność obliczeniowa związana ze znalezieniem konkretnego elementu w tablicy z haszowaniem wynosi O(1) — wynik ten znacznie przebija złożoność przeszukiwania zwykłej tablicy, wynoszącą O(n).

Na koniec warto sobie uświadomić, że powiększenie tablicy z haszowaniem jest kosztowną operacją. Dlatego — jeśli w przybliżeniu wiemy, ile elementów zostanie dodanych do tablicy z haszowaniem — powinniśmy za pomocą konstruktora odpowiednio ustawić początkowy rozmiar tablicy, aby uniknąć niepotrzebnego zwiększania tablicy.

Podsumowanie

W tym artykule poznaliśmy trzy rodzaje struktur danych zaimplementowanych w bibliotece klas bazowych środowiska .NET:

• kolejkę,

• stos,

• tablicę z haszowaniem.

Klasy Queue i Stack pozwalają na przechowywanie dowolnej liczby obiektów niejednorodnych. Różnią się one od klasy ArrayList tym, że klasa ArrayList pozwala na bezpośredni dostęp do dowolnego przechowywanego elementu. W przypadku klasy Queue i Stack do elementów można uzyskać dostęp jedynie w z góry określonej kolejności.

W kolejkach stosowane jest szeregowanie FIFO (pierwszy przyszedł — pierwszy obsłużony). Oznacza to, że elementy mogą być usuwane z kolejki jedynie w takiej samej kolejności, w jakiej zostały w niej umieszczone. Aby zapewnić taką kolejność, klasa Queue udostępnia metody Enqueue() i Dequeue(). Kolejki to struktury danych przydatne w szeregowaniu zadań oraz w innych sytuacjach, gdy ważna jest kolejność pojawiania się elementów.

Z kolei w stosie występuje szeregowanie LIFO (ostatni przyszedł — pierwszy obsłużony). Operacje na stosie można przeprowadzać za pomocą metod Push() oraz Pop(). Stos ma wiele zastosowań w informatyce — od wykonywania kodu po parsery.

Ostatnią omawianą strukturą danych była tablica z haszowaniem. Klasa Hashtable poszerza funkcjonalność klasy ArrayList o możliwość indeksowania tablicy kluczami dowolnego typu (nie tylko liczbami całkowitymi). Gdy potrzebne jest przeszukiwanie tablicy za pomocą unikalnego klucza, najbardziej wydajnym rozwiązaniem jest zastosowanie tablicy z haszowaniem, gdyż przeszukiwanie tablicy według klucza przeprowadzane jest w czasie stałym, w przeciwieństwie do liniowego czasu przeszukiwania zwykłej tablicy.

Na tym kończę drugi artykuł serii poświęconej strukturom danych. W następnym artykule przyjrzymy się drzewom wyszukiwań binarnych — strukturom danych, w których przeszukiwanie ma złożoność obliczeniową na poziomie O(log n). Drzewa wyszukiwań binarnych — tak samo jak tablice z haszowaniem — są najlepszym rozwiązaniem, gdy planujemy częste przeszukiwanie danych.

Życzę miłego programowania!

Bibliografia

• „Wprowadzenie do algorytmów”, Thomas H. Cormen, Charles E. Leiserson i Ronald L. Rivest, Wydawnictwa Naukowo-Techniczne

• „Data Abstraction and Structures Using C++", Mark R. Headington i David D. Riley, D.C. Heath and Company, 1994

• Applied Microsoft .NET Framework Programming — Jeffrey Richter

• Shared Source Common Language Infrastructure 1.0 Release (udostępnione w listopadzie 2002)

Scott Mitchell — autor 5 książek i założyciel witryny 4GuysFromRolla.com. Od 5 lat zajmuje się w Microsoft technologiami internetowymi. Scott pracuje jako niezależny konsultant, szkoleniowiec i autor artykułów, a niedawno zdobył dyplom z informatyki na Uniwersytecie Kalifornijskim w San Diego. Jego adres e-mail to [e-mail].

---