haszowanie, kodowanie mieszające,
inform. technika szybkiego dostępu do rekordów zapisanych w bazie danych.
haszowanie
Encyklopedia PWN
Polega na podziale zbioru wszystkich możliwych wartości klucza (klucz, inform. ) na n podzbiorów; podział ten określa tzw. funkcja haszująca — w najprostszym przypadku jest to reszta z dzielenia wartości klucza przez pewną liczbę pierwszą. Jeśli klucz nie jest liczbą (np. kombinacja daty urodzenia i nazwiska), to najpierw przypisuje mu się wartość liczbową, np. sumując kody kolejnych znaków. Rekordy zawierające klucze należące do tego samego podzbioru są zapisywane fizycznie obok siebie w pamięci zewn., zorganizowanej jako n-elementowa tablica. Wyszukiwanie rekordu o podanym kluczu polega na określeniu podzbioru, do którego należy dany klucz (czyli wyliczeniu wartości funkcji haszującej), a następnie przejrzeniu rekordów z tego podzbioru. Jeśli liczba podzbiorów n jest większa od całkowitej liczby rekordów w bazie, a podziału na podzbiory dokonano tak, że prawdopodobieństwo włączenia losowo wybranego rekordu do każdego podzbioru jest takie samo, to większość podzbiorów będzie zawierała tylko jeden rekord; dostęp do rekordu będzie zwykle wymagał tylko jednego obliczenia wartości funkcji haszującej i sięgnięcia do właściwego miejsca w tablicy. Dla przypadku, gdy klucze 2 lub więcej rekordów należą do tego samego podzbioru (kolizja) musi być zdefiniowany sposób zapisywania i znajdowania kolejnych rekordów z tego samego podzbioru; zwykle zapisuje się je w kolejnych wolnych miejscach tablicy albo w dodatkowym obszarze nadmiarowym.
