Primární shlukování - Primary clustering

v programování, primární shlukování je jedním ze dvou hlavních poruchových režimů otevřené adresování na základě hash tabulky, zejména těch, kteří používají lineární sondování Dochází k tomu po a hash kolize způsobí, že dva ze záznamů v hašovací tabulce budou hašovány do stejné polohy a způsobí, že jeden ze záznamů bude přesunut na další místo v jeho sekvenci sondy. Jakmile k tomu dojde, klastr tvořený touto dvojicí záznamů pravděpodobně naroste přidáním ještě více kolizních záznamů, bez ohledu na to, zda jsou nové záznamy zatříděny do stejného umístění jako první dva. Tento jev způsobuje hledání klíčů v klastr být delší.^[1]

Například v lineární sondování, záznam zapojený do kolize se vždy přesune do další dostupné buňky tabulky hash po poloze dané její funkcí hash, čímž se vytvoří souvislý shluk obsazených buněk tabulky hash. Kdykoli je jiný záznam hašován kamkoli v klastru, zvětší se jeho velikost o jednu buňku. Kvůli tomuto jevu je pravděpodobné, že lineární sonda hash tabulka s konstantou faktor zatížení (tj. s velikostí tabulky úměrné počtu položek, které ukládá) bude mít nějaké shluky logaritmické délky a bude trvat logaritmický čas na hledání klíčů v tomto klastru.^[2]

Související jev, sekundární shlukování, se vyskytuje obecněji v režimech otevřeného adresování, včetně lineárního sondování a kvadratické sondování ve kterém je sekvence sondy nezávislá na klíči, stejně jako v řetězci hash. V tomto jevu nízká kvalita hashovací funkce může způsobit, že mnoho klíčů bude hashovat na stejné místo, po kterém budou všechny následovat stejnou sekvenci sondy nebo budou umístěny do stejného hash řetězce jako každý jiný, což způsobí, že budou mít pomalé časy přístupu.^[1]

Oba typy klastrování lze snížit použitím kvalitnější hashovací funkce nebo pomocí metody hash, jako je dvojitý hash to je méně náchylné ke shlukování.^[1]

Reference

Tento počítačová věda článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.