Klasyfikacja funkcji skrótu

9

W Internecie natknąłem się na to pytanie:

Klasyfikuj funkcje mieszania na podstawie różnych metod, za pomocą których można znaleźć wartość klucza.

z odpowiedziami jak

  • Metoda bezpośrednia
  • Metoda odejmowania
  • Metoda podziału modulo
  • Metoda ekstrakcji cyfrowej
  • Metoda połowy kwadratu
  • Metoda składania
  • Metoda pseudolosowa

co wydaje mi się dziwne. Myślę, że dużo wiem o haszowaniu, ale to dla mnie zwykły bełkot, czy ktoś mógłby to wyjaśnić?

maaartinus
źródło

Odpowiedzi:

4

Są to metody przekształcania kodu skrótu w indeks tablicy zawierającej wartości. Załóżmy, że masz kod skrótu 0x12345678. Bardzo duża liczba i prawdopodobnie nie będziesz mieć tablicy o takim rozmiarze. Jeśli tak, możesz to zrobić

Value = array[0x12345678];

I gotowe (metoda bezpośrednia).

Jeśli tego nie zrobisz, masz sposób, aby zmienić tę wartość na taką, która pasuje do rozmiaru tablicy, starając się unikać zbyt wielu kolizji. Używane terminy są prawdopodobnie znane także pod innymi nazwami, ale na przykład możesz po prostu zamaskować wyższe bity haszyszu

Value = array[hashcode & 0xffff];

Lub zmodyfikuj kod skrótu względem rozmiaru tablicy

Value = array[hashcode % array.size()]; // modulo division

Itd itd

Edycja: ten link może pomóc

James
źródło
Dzięki, to wszystko - link wydaje się być źródłem tego ***. Nadal nie ma sensu, ponieważ łączą ze sobą wiele rzeczy: 1. obliczanie kodu mieszającego z klucza (np. Składanie i dodawanie), 2. poprawianie (= rozmazywanie) skrótu (np. W połowie kwadratu), 3. mapowanie skrót do indeksu (np. moduł, „&”).
maaartinus,