Dlaczego nazywa się to „hash table” lub „hash function”? Hash nie ma dla mnie żadnego sensu [zamknięte]

26

Obecnie używam około 4 lat rozwoju, którego używam, słyszę, mówię i wdrażam tabele skrótów i funkcje skrótu. Ale tak naprawdę nigdy nie rozumiem, dlaczego nazywa się to hash?

Pamiętam pierwsze dni, kiedy zaczynałem programować, termin ten był dla mnie trochę nieporęczną terminologią . Nigdy nie zastanawiałem się, co to jest, na podstawie jego nazwy . Właśnie eksperymentalnie zrozumiałem, co robi i dlaczego i kiedy powinniśmy go użyć .

Jednak nadal czasem próbuję dowiedzieć się, dlaczego nazywa się to hash . Nie mam problemu z tabelą ani funkcją i szczerze mówiąc, są to dość dedukcyjne, racjonalne warunki. Myślę jednak, że zamiast skrótu można użyć lepszych słów, takich jak klucz lub wyjątkowość . Nie wpisuj tabeli ani tabeli wyjątkowości .

Według mojego słownika hash oznacza:

  1. Smażone danie z ziemniaków i mięs (wysoce nieistotne)
  2. # symbol (znak numeru AKA, znak funta itp.) (wciąż nieistotny, może po prostu błędna nomenklatura)
  3. Zastosuj algorytm do łańcucha znaków (nadal nie ma to nic wspólnego z wyjątkowością , która jest najważniejszą cechą tabeli skrótów)
  4. Pokroić jedzenie
  5. Kolejny termin na haszysz

Czy ktoś wie, dlaczego nazywa się to hash?

Saeed Neamati
źródło
32
Wygląda na to, że nieco źle rozumiesz, czym są skróty. Unikalność nie jest wyraźnie cechą funkcji skrótu (tzn. Nigdy nie są iniekcyjne).
Peter Taylor
1
@Peter Taylor: tabele skrótów definiują iniekcyjne mapowania.
reinierpost
2
@Peter Taylor: aby być trochę podejrzanym, nie muszą być iniekcyjni , ale czasami są nawet biotywni. Pomyśl o typowej implementacji funkcji
skrótu
4
Hash może być unikalny, o ile przestrzeń klucza nie jest większa niż przestrzeń wartości skrótu (dla skrótów tabeli) lub przestrzeń wartości skrótu jest tak duża, że ​​kolizje są matematycznie niewykonalne (dla skrótów kryptograficznych).
Zabezpiecz
1
Ponadto „tablica kluczy” brzmi bardziej jak każda struktura danych „klucz / wartość” (zwana także „słownikiem”). Nie wszystkie struktury danych klucz / wartość to tabele skrótów.
barjak

Odpowiedzi:

46

Według wikipedii odnosi się do funkcji skrótu . Jeśli chcesz pójść o krok dalej, strona wiki dla funkcji skrótu mówi, że użycie słowa „hash” w funkcji skrótu pochodzi tak:

Termin „skrót” pochodzi od analogii z nietechnicznym znaczeniem, aby „posiekać i zmiksować”. Rzeczywiście, typowe funkcje skrótu, takie jak operacja mod, „rąbią” domenę wejściową na wiele subdomen, które „mieszają się” z zakresem wyjściowym, aby poprawić jednorodność dystrybucji klucza.

użytkownik937146
źródło
2
Nie jestem pewien, co tam robią „subdomeny”. Po prostu funkcja skrótu dokładnie „miesza” wartości swojej domeny.
reinierpost
15

W języku francuskim tablica skrótów nazywa się „table de hachage”, powiązany czasownik „hacher” oznacza siekać / siekać (głównie jedzenie). Czasownik to hashma to samo znaczenie w języku angielskim.

Tak jak inni zauważyli, nazywa się to hash, ponieważ siekasz swój wkład, który wkładasz w kawałki w różnych miejscach (wpisy w tabeli).

Xavier T.
źródło
2
Jest napisane „hachage” i „hacher” bez akcentu.
Ptival
10

Numer 3 ma z tym wszystko wspólnego. Z Wikipedii :

W sercu algorytmu tabeli skrótów jest prosta tablica elementów; jest to często nazywane po prostu tabelą skrótów . Algorytmy tabeli mieszania obliczają indeks na podstawie klucza elementu danych i używają tego indeksu do umieszczania danych w tablicy. Realizacja tego obliczenia jest funkcja skrótu , f:

index = f(key, arrayLength)

Funkcja skrótu oblicza w indexobrębie tablicy dane key. arrayLengthjest rozmiarem tablicy. W języku asemblera lub innych programach niskiego poziomu trywialna funkcja skrótu może często tworzyć indeks z jedną lub dwiema wbudowanymi instrukcjami maszyny .

Tak więc tabela skrótów tak naprawdę nie przechowuje wartości opartych na kluczu; przechowuje wartości na podstawie zaszyfrowanej wersji tego klucza.

Michelle Tilley
źródło
1
zależy to od tego, co rozumiesz przez tablicę skrótów. Struktura danych oferowana w językach takich jak Perl, Java i C # daje mapowanie klucza do wartości, przy użyciu rodzaju tablicy skrótów, do której się odwołujesz wewnętrznie.
reinierpost
10

tabele skrótów są nazywane w ten sposób, ponieważ używają kodu skrótu i są powiązane z „cut food”.

Pomyśl o tym w ten sposób - bierzesz swój ładny, ładny przedmiot, jak owoc, a następnie go haszujesz, aby zaczął wyglądać jak wszystko inne - tylko liczba - nie ma już w nim żadnej struktury. Ten kawałek „pokrojonego jedzenia” jest używany w tabeli mieszania, aby znaleźć ładny ładny obiekt.

  • Wygląda brzydiej niż twój ładny obiekt? może - ale pomaga to szybko znaleźć - o to właśnie chodzi. och, i to na pewno nie jest wyjątkowe.
     
    Kod mieszający znajduje wiadro w tabeli, w której Twój ładny obiekt znajduje się w małej grupie innych osób z tym samym kodem mieszającym. W tej małej firmie obiekt jest sprawdzany przy użyciu funkcji sprawdzania równości - która powinna być znacznie wolniejsza niż wyszukiwanie mieszania, ale nie jest to wielka sprawa, ponieważ jest ich tylko kilka (większość innych obiektów jest już ignorowana dzięki szybkiemu skrótowi) .
komar
źródło
3

Hashowanie (np. Krojenie na małe kawałki, niszczenie itp.) Wymaga wkładu (żywności lub czasem superwindykacji) i przekształca je w stosunkowo jednorodny wynik. Bez względu na to, co miałeś na początku, na końcu po prostu masz hash. I łyżka skrótu jest tak samo pomocna jak cały skrót w określaniu, co było wejściem (przy założeniu, że haszarka dobrze hashuje).
Tak więc haszowanie może zredukować dowolny jadalny lub zły przedmiot do łyżki haszu, w którym dwa różne obiekty dają różne hasze, podczas gdy dwa równe obiekty dają takie same hasze. Co oznacza, że ​​jeśli dwie supervillainy wpadną na twoją maszynę haszującą, wystarczy porównać ich hasze, aby ustalić, czy jedna była klonem drugiej.

W pewien sposób funkcje haszujące w informatyce są trochę podobne. Biorą cały wkład o różnej wielkości i semantyce, i - po prostu wkładają - po prostu kroją go na kawałki i mieszają te wokół, a następnie wycinają powstałą sekwencję z powrotem na kawałki i mieszają to wokół i tak dalej. Na koniec masz łyżkę (n bajtów) wprowadzonego hasła.

back2dos
źródło
Jednak z zastrzeżeniem, super czarny charakter może również zwrócić ten sam skrót jak super bohater z danym zestawem parametrów, ponieważ mieszanie nie wydaje się narzucać wyjątkowości. W końcu zdarzają się kolizje hash ... to, co robisz po kolizji ...
Rig