Կարող եք բացատրել երկակի հեշավորման մեթոդի սկզբունքը հեշ աղյուսակներում բախումները լուծելու համար:

Երկակի հեշավորման մեթոդը հեշ աղյուսակներում բախումների լուծման միջոց է, որի ժամանակ բախում առաջանալիս հաշվարկվում է երկրորդ հեշը, և հաջորդ ինդեքսը, որով որոնվում է տարրն, որոշվում է այդ երկրորդ հեշի միջոցով:

Նկատում.

• Կան երկու հեշային ֆունկցիաներ՝ h1(key) և h2(key):

• Տարր ավելացնելու կամ որոնելու ժամանակ առաջինը հաշվարկվում է h1(key) — սկզբնական ինդեքսը:

• Եթե դիրքը զբաղված է (բախում), ապա հաջորդ ինդեքսը հաշվարկվում է հետևյալ բանաձևով՝

  index = (h1(key) + i * h2(key)) mod աղյուսակի չափը, որտեղ i փորձերի թիվն է (0,1,2,...):

Այս մեթոդը թույլ է տալիս խուսափել բախումներից՝ անցնելով աղյուսակով քայլերով, որոնք կախված են բանալիից, ինչը նվազեցնում է կլաստերացումը՝ համեմատած գծային որոնման հետ:

Go-ում օրինակ՝

func doubleHashing(key int, i int, tableSize int) int {
    h1 := key % tableSize
    h2 := 1 + (key % (tableSize - 1))
    return (h1 + i*h2) % tableSize
}

Այստեղ h2 միշտ չէ, որ զրո է, և ապահովում է, որ անհրաժեշտության դեպքում կանցնենք ամբողջ աղյուսակով։