Kollisionsprocesseren

Kollisionsprocesseren er et begreb inden for datalogi, der beskriver de mekanismer, der anvendes til at håndtere kollisionssituationen, hvor to eller flere elementer får samme adresse eller nøgle i en dataorganisation. Kollisionshåndtering optræder blandt andet i hash-tabeller, databaser og netværkskommunikation, hvor målet er at sikre korrekt lagring og hurtig adgang uden at miste data eller ydeevne.

I hash-tabeller anvendes to hovedmetoder: separat kædning og åben adressering. Ved separat kædning lagres alle elementer, der hash’er til samme placering, i en kæde (typisk en linked list eller dynamisk struktur). Ved åben adressering finde man en alternativ ledig plads ved hjælp af en probe-funktion (lineær, kvadratisk eller dobbelt hashing). Ved indførsel og sletning skal man håndtere rekkefølgen og mulighederne for tombstones eller remisehashing for at bevare ydeevnen.

I netværk er kollisionshåndtering ofte forbundet med delte medieadgangsmekanismer som CSMA/CD, hvor noder lytter før transmission og anvender tilfældige backoff-tider, hvis en kollision registreres. Moderne switchbaserede netværk begrænser kollisionsområder og har mindre behov for komplekse backoff-algoritmer end ældre Ethernet-netværk.

Ydeevne og vedligeholdelse afhænger af belastning, valg af struktur og størrelse. Vigtige faktorer inkluderer belastningsfaktoren, hash-funktionens kvalitet, valg af kollisionsstrategi og nødvendig omstrukturering (f.eks. rehashing og udvidelse af tabellen) for at bevare effektive søge- og indsættelsesoperationer.