Blog o PHPi tematyce pokrewnej

Tablica haszująca to niezwykła struktura danych. Pozwala ona na odnajdowanie elementów w niej zawartych (np. string’ów) ze złożonością obliczeniową równą O(c). Stąd też bierze się jej największa zaleta - szybkość szukania. Pewnie wielu z Was zadaje sobie pytanie, czym jest ów złożoność obliczeniowa? Wytłumaczę to najprościej jak potrafię. Jest to ilość zasobów (czas procesora, itp.), które musimy użyć w celu rozwiązania naszego problemu.

tablica haszująca w teorii

Podstawę stanowi zwykła tablica. Aby móc efektywnie z niej korzystać musimy dodatkowo zaimplementować 3 algorytmy:

• funkcja numeryzacji klucza
• funkcja mieszająca
• funkcja usuwania kolizji

funkcja numeryzacji klucza - zazwyczaj element, który chcemy umieścić w naszej strukturze danych jest ciągiem znaków, a niektóre języki programowania (Pascal,C) oferują wyłącznie tablice o indeksach numerycznych. Funkcja ta zajmuję się więc odwzorowaniem string’a na integer’a (z dużą wrażliwością na każdy bit wejścia).

funkcja mieszająca - dzięki niej integer zostaje “skrócony” do takiej postaci, w której może być indeksem naszej tablicy. Jest to ważne tam, gdzie rozmiar tablicy jest np. z góry narzucony.

funkcja usuwania kolizji - w sytuacji w której dla dwóch różnych string’ów, otrzymujemy ten sam numer indeksu, pod którym mają one zostać umieszczone, potrzebny nam jest ostatni algorytm. Dba on o odpowiednią obsługę takich sytuacji.

tablica haszująca w praktyce

Prześledźmy nasze algorytmy i ich funkcję na przykładzie string’a “piekna pogoda“.
1. Etap pierwszy - numeryzacja klucza
Tutaj nasz string dostaje swoją reprezentację numeryczną - np. 312432543.
2. Etap drugi - funkcja mieszająca
Nasza tablica może przechować 32 elementy. Stąd też dla wartości 312432543 musimy uzyskać liczbę z przedziału od 0 do 31. Zakładamy, że będzie to 18. Pod tym indeksem umieszczamy nasz string “piekna pogoda”.
3.Etap trzeci - usuwanie kolizji
Jeśli się zdarzy sytuacja, że dla string’a “super dzionek” indeksem jest też 18, to musimy zadbać o to. aby nasze dane nie zostały utracone. Jednym z rozwiązań jest dodatkowa tablica, pod każdym z indeksów tablicy pierwotnej. Daje to następujący rezultat:
tablica[18][0] -> “piekna pogoda”
tablica[18][1] -> “super dzionek”

tablica haszująca w PHP

Na szczęście implementacja tablicy mieszającej w PHP jest bardzo prosta. Popatrzmy na kod klasy:

class HashTable {

	public $hash_table;

	public function __construct () {

		$this->hash_table = array();

	}

	public function AddElement ($string) {

		if ($this->hash_table[md5($string)][0] !== NULL)
			$this->hash_table[md5($string)][count($this->hash_table[md5($string)])] = $string;
		else
			$this->hash_table[md5($string)][0] = $string;

		return TRUE;

	}

	public function DeleteElement ($string) {

		if ($this->hash_table[md5($string)][0] !== NULL) {
			$size = count($this->hash_table[md5($string)]);
			for ($i=0;$i<$size;$i++)
				if ($this->hash_table[md5($string)][$i] === $string) {
					unset($this->hash_table[md5($string)][$i]);
					return TRUE;
				}
		}

		return FALSE;

	}

	public function ElementExists ($string) {

		if ($this->hash_table[md5($string)][0] !== NULL)
			foreach ($this->hash_table[md5($string)] as $value)
				if ($value === $string)
					return TRUE;

		return FALSE;

	}

}

$hash = new HashTable();

$hash->AddElement(’a');
$hash->AddElement(’dsa’);
$hash->AddElement(’adasasd’);
$hash->DeleteElement(’dsa’);

var_dump ($hash);
var_dump ($hash->ElementExists(’dsa’));

Pewnie ciężko znaleźć w tym kodzie odseparowane od siebie trzy algorytmy, o których tak dużo pisałem. To prawda, nie widać ich na pierwszy rzut oka. Dlaczego? Ponieważ w PHP mamy dostęp do tablic asocjacyjnych. Stąd brak funkcji numeryzacji klucza. Funkcję mieszającą stanowi md5(). Jak wiecie istnieje małe prawdopodobieństwo, iż znajdą się dwa ciągi znaków o tym samym md5, stąd też funkcja usuwania kolizji polega na przechowywaniu elementów o tym samym 32 bajtowym “skrócie” w dodatkowej tablicy.

uwagi końcowe

Moja implementacja stanowi tylko przykład. Możecie zrezygnować z usuwania kolizji, dodać obsługę wyjątków, na co tylko macie ochotę. Nasuwa się jeszcze jedno pytanie? Gdzie używać? Sprawdzanie dostępności nicków przy rejestracji user’ów jest jedną z możliwości. Mam nadzieję, że ułatwiłem Wam w choć małym stopniu zrozumienie tego zagadnienia.

Chcesz wiedzieć więcej?
Złożoność obliczeniowa:
http://www.ds5.agh.edu.pl/~evolic/badania_op/teoria/ogolnie01.html
http://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa

Funkcja numeryzacji klucza:
Poczytaj o metodach
- składanie zygzakowe
- składanie cykliczne z sumowaniem arytmetycznym

Funkcja mieszająca:
Poczytaj o
- metoda randomizacji
- metoda środka kwadratu
- metoda dzielenia
- metoda mnożenia

Funkcja usuwania kolizji:
Poczytaj o
- usuwaniu konfliktów bez obszaru nadmiarowego
- usuwaniu konfliktów z obszarem nadmiarowym