Feature phone - puzzle online
Puzzle online Feature phone
Funkcja skrótu, funkcja mieszająca lub funkcja haszująca – funkcja przyporządkowująca dowolnie dużej liczbie krótką, zawsze posiadającą stały rozmiar, niespecyficzną, quasi-losową wartość, tzw. skrót nieodwracalny.
W informatyce funkcje skrótu pozwalają na ustalenie krótkich i łatwych do weryfikacji sygnatur dla dowolnie dużych zbiorów danych. Sygnatury mogą chronić przed przypadkowymi lub celowo wprowadzonymi modyfikacjami danych (sumy kontrolne), a także mają zastosowania przy optymalizacji dostępu do struktur danych w programach komputerowych (tablice mieszające).
Algorytmy funkcji skrótu
Doskonała funkcja haszująca
Dla zbioru S, doskonała funkcja haszująca przyporządkowuje każdemu elementowi z tego zbioru liczbę całkowitą bez kolizji. Innymi słowy, funkcja ta jest iniekcją.
Minimalna doskonała funkcja haszująca
Minimalna doskonała funkcja haszująca jest doskonałą funkcją haszującą, która n argumentom przyporządkowuje wartości ze zbioru n kolejnych liczb całkowitych. Formalnie można to wyrazić w następujący sposób: Niech j i k będą elementami pewnego skończonego zbioru kluczy K. F jest minimalną doskonałą funkcją haszującą wtedy i tylko wtedy, gdy wartość funkcji dla argumentów j i k implikuje równość tych argumentów oraz istnieje liczba całkowita a, taka, że zbiór wartości F to
[
a
,
a
+
|
K
|
−
1
]
.
{\displaystyle [a,a+|K|-1].}
Haszowanie danych o rozkładzie jednostajnym
Jeśli dane wejściowe to dane o określonej długości i jednostajnym rozkładzie prawdopodobieństwa, funkcja haszująca może wykorzystać haszowanie modularne lub haszowanie przez mnożenie. Przykładowo, na wejściu pojawiają się liczby z zakresu od 0 do N-1, a na wyjściu chcemy otrzymać wartości h ze zbioru od 0 do n-1, gdzie N jest istotnie większe od n.