Кружни хеш

Кружни хеш је хеш функција код које се улаз обрађује помоћу прозора који секвенцијално пролази кроз податке. Постоји неколико хеш функција које омогућавају да се кружни хеш израчуна веома брзо - нова хеш вредност се брзо рачуна уз помоћ претходно израчунате а затим се стара вредност у прозору замењује новом. Многи алгоритми користе кружни хеш а једна од главних примена кружног хеша је Рабин-Карп алгоритам за претрагу који користи функцију описану испод. Још једна од популарних примена је рсyнц програм који као свој кружни хеш користи алгоритам за контролу преноса заснован на Адлеровом алгоритму. У најбољем случају, кружна хеш функција је парно независна или гарантује мали број колизија. На пример, кружни хеш не може бити троструко независан.

Рабин-Карп кружни хеш

Рабин-Карп алгоритам за претрагу стрингова се обично користи уз помоћ једноставне кружне хеш функције која користи само множење и сабирање: Х = ц₁а^к-1 + ц₂а^к-2 + ц₃а^к-3 + ... + ц_ка⁰ при чему је а константа, а ц₁, ..., ц_к улазни карактери. Како би се избегло руковање огромним вредностима Х, сва математика се врши по модулу н. Избор а и н је кључан да би се обавило добро хеширање. Избацивање и додавање нових карактера једноставно укључује избацивање или додавање првог или последњег терма. Шифтовање свих карактера за једно место у лево подразумева множење целе суме Х са а. У аритметици по модулу, а може бити изабрано тако да има мултипликативни инверз а^-1 који множењем са Х заправо врши дељење.

Сечење засновано на садржају користећи Рабин-Карп хеш

Једна од интересантних примена кружног хеша је стварање динамичких делова улазних података или фајла, оријентисаних ка садржају. Ово је поготово корисно када је потребно послати само промењене делове великог фајла и једноставно смештање додатног бајта испред почетка фајла би узроковало да се нпр. све фиксиране величине прозора подесе, а заправо је само први део података модификован.

Најједноставнији приступ израчунавању динамичких делова је употребити кружни хеш и ако се појави шаблон (нпр. нижих Н битова су нуле) то је онда граница једног дела. Овај приступ обезбеђује да било какве промене у фајлу утичу на текући и евентуално на следећи део података, али ни на шта више. Када су границе познате, делови се упоређују по својим хеш вредностима да би се утврдило који је део модификован и потребно га је поново слати.

Софтвер

• Јава кружни хеш Апаче лиценцирана Јава имплеметација функција кружног хеширања
• Нграм хеширање C++ имплементација неколико функција кружног хеширања

Спољашње везе

• Предавања МИТ Мит 6.006: Увод у алгоритме 2011 - Белешке са предавања - Кружни хеш