streamalism.org

1. Inleiding

In deze tutorial bekijken we hashing-technieken die worden gebruikt in verschillende datastructuren die constante tijd toegang bieden tot hun elementen.

We bespreken in meer detail de zogenaamde vouwtechniek en geef een korte inleiding tot mid-square en binning-technieken.

2. Overzicht

Wanneer we datastructuren kiezen voor het opslaan van objecten, is een van de overwegingen of we er snel toegang toe moeten hebben.

Het Java utility-pakket biedt ons heel wat datastructuren om onze objecten op te slaan. Raadpleeg voor meer informatie over datastructuren onze Java Collections-compilatiepagina die handleidingen over verschillende ervan bevat.

Zoals we weten, sommige van deze datastructuren stellen ons in staat om hun elementen in constante tijd op te halen, onafhankelijk van het aantal elementen dat ze bevatten.

Waarschijnlijk is de eenvoudigste de array. In feite hebben we toegang tot elementen in de array op basis van hun index. De toegangstijd is natuurlijk niet afhankelijk van de grootte van de array. In feite maken veel datastructuren achter de schermen intensief gebruik van arrays.

Het probleem is dat de array-indexen numeriek moeten zijn, terwijl we deze datastructuren vaak liever manipuleren met objecten.

Om dit probleem op te lossen, proberen veel datastructuren een numerieke waarde toe te kennen die kan dienen als een array-index aan objecten. We noemen deze waarde a hash-waarde of gewoon een hash.

3. Hashing

Hashing is een transformatie van een object in een numerieke waarde. Functies die deze transformaties uitvoeren, worden genoemd hash-functies.

Laten we voor de eenvoud eens kijken naar hash-functies die strings omzetten in array-indexen, dat wil zeggen in gehele getallen uit het bereik [0, N] met een eindig N.

Van nature, een hash-functie wordt toegepast op een grote verscheidenheid aan strings. Daarom worden zijn "globale" eigenschappen belangrijk.

Helaas is het niet mogelijk dat een hash-functie altijd verschillende strings in verschillende getallen omzet.

We kunnen onszelf vrij gemakkelijk overtuigen dat het aantal strings veel groter is dan het aantal gehele getallen in een willekeurig bereik [0, N]. Daarom is het onvermijdelijk dat er een paar niet-gelijke strings is waarvoor een hash-functie gelijke waarden produceert. Dit fenomeen wordt genoemd botsing.

We gaan niet in op de technische details achter hash-functies, maar het is duidelijk dat een goede hash-functie moet proberen om de strings waarop deze is gedefinieerd in getallen uniform in kaart te brengen.

Een andere voor de hand liggende vereiste is dat een goede hash-functie snel moet zijn. Als het te lang duurt om een ​​hash-waarde te berekenen, kunnen we niet snel toegang krijgen tot elementen.

In deze tutorial beschouwen we een van de technieken die proberen de mapping uniform te maken terwijl het snel wordt gehandhaafd.

4. Vouwtechniek

Ons doel is om een ​​functie te vinden die strings omzet in array-indexen. Om het idee te illustreren, stel dat we willen dat deze array de capaciteit heeft voor 105 elementen en laten we string gebruiken Java-taal als voorbeeld.

4.1. Omschrijving

Laten we beginnen met het omzetten van de tekens van de tekenreeks in cijfers. ASCII is een goede kandidaat voor deze operatie:

Nu rangschikken we de getallen die we zojuist hebben verkregen in groepen van een bepaalde grootte. Over het algemeen kiezen we de waarde voor de groepsgrootte op basis van de grootte van onze array, die 105 is. Aangezien de getallen waarin we de tekens hebben omgezet, twee tot drie cijfers bevatten, zonder verlies van algemeenheid, kunnen we de groepsgrootte instellen op twee:

De volgende stap is om de getallen in elke groep samen te voegen alsof het strings zijn en hun som te vinden:

Nu moeten we de laatste stap zetten. Laten we eens kijken of het nummer 348933 kan dienen als een index van onze reeks van grootte 105. Uiteraard overschrijdt het de maximaal toegestane waarde 99999. We kunnen dit probleem gemakkelijk oplossen door de modulo-operator toe te passen om het uiteindelijke resultaat te vinden:

348933 % 10000 = 48933

4.2. Laatste opmerkingen

We zien dat het algoritme geen tijdrovende bewerkingen bevat en daarom vrij snel is. Elk teken van de invoerstring draagt ​​bij aan het eindresultaat. Dit feit helpt zeker om botsingen te verminderen, maar niet om ze volledig te vermijden.

Als we bijvoorbeeld het vouwen willen overslaan en de modulo-operator rechtstreeks op de ASCII-getransformeerde invoertekenreeks willen toepassen (waarbij het overloopprobleem wordt genegeerd)

749711897321089711010311797103101 % 100000 = 3101

dan zou zo'n hash-functie dezelfde waarde produceren voor alle strings die dezelfde laatste twee karakters hebben als onze invoertekenreeks: age, pleeftijd, large, enzovoorts.

Uit de beschrijving van het algoritme kunnen we gemakkelijk zien dat het niet vrij is van botsingen. Het algoritme produceert bijvoorbeeld dezelfde hash-waarde voor Java-taal en vaJa taal snaren.

5. Andere technieken

De vouwtechniek is vrij gebruikelijk, maar niet de enige. Soms het binning of midden vierkant technieken kunnen ook nuttig zijn.

We illustreren hun idee door geen strings te gebruiken, maar getallen (stel dat we de strings al op de een of andere manier in getallen hebben omgezet). We zullen hun voor- en zwakke punten niet bespreken, maar u kunt een mening vormen na het zien van de algoritmen.

5.1. Binning-techniek

Stel dat we 100 gehele getallen hebben en we willen dat onze hashfunctie ze in een array van 10 elementen toewijst. Dan mogen we die 100 gehele getallen gewoon in tien groepen rangschikken, zodanig dat de eerste tien gehele getallen in de eerste bak terecht komen, de tweede tien gehele getallen in de tweede bak, etc .:

5.2. Mid-Square-techniek

Dit algoritme werd voorgesteld door John von Neumann en stelt ons in staat om pseudo-willekeurige getallen te genereren vanaf een bepaald getal.

Laten we het illustreren aan de hand van een concreet voorbeeld. Stel dat we een viercijferig nummer hebben 1111. Volgens het algoritme kwadrateren we het en verkrijgen we zo 1234321‬. Nu halen we vier cijfers uit het midden, bijvoorbeeld 2343. Met het algoritme kunnen we dit proces herhalen totdat we tevreden zijn met het resultaat.

6. Conclusie

In deze tutorial hebben we verschillende hash-technieken besproken. We hebben de vouwtechniek in detail beschreven en in een flits beschreven hoe binning en mid-square kunnen worden bereikt.

Zoals altijd kunnen we de bijbehorende codefragmenten vinden in onze GitHub-repository.