Paiskfunktsioon seab igale elemendile vastavusse ühtlase jaotusega

16-bitise täisarvu piirides 0 . . . 2

Vähemalt mitu elementi tuleb lisada tühja paisktabelisse, et tõenäosusega üle 50% tekiks mõnel lisamisel põrge?

Vastus:

Vihje.

Vaata Vikipeedia artikleid

Paisktabelisse pikkusega 4 paigutatakse elemente paiskfunktsiooni h(k) =

k mod 4 abil. Sama võtmeväärtusega elemendid organiseeritakse

kahendpuuna järgmisel viisil.

Kahendpuu esimesel tasemel määratakse elemendi lõpust lugedes 3. bitt

ning vastavalt selle väärtusele 0 või 1 suunatakse element kas vasakusse

või paremasse harusse. Kahendpuu teisel tasemel leitakse elemendi lõpust

lugedes 4. bitt ning analoogiliselt valitakse vasak või parem haru jne.

Haru jaotatakse kaheks ainult siis, kui seda on vaja.

Milline järgmisest elementide lisamiste jadadest annab tulemuseks

sellise struktuuriga paisktabeli?

Plaadimasin esitab juhuslikult lugusid oma mälus oleva 4000 loo seast.

Sama lugu võib valida korduvalt.

Vähemalt mitu järjestikust lugu peab kuulama, et tõenäosus kuulda mõnda

lugu teist korda oleks üle 50%?

Vastus:

Vihje.

Vaata Vikipeedia artikleid

Milline järgnevatest paiskfunktsioonidest jaotab täisarve, mis muutuvad

0-st 999-ni, kõige ühtlasemalt kümnesse kimpu numbritega 0 kuni 9?

Paljud Java klassid sisaldavad meetodit hashCode()

, mille ülesanne on

seada objektile vastavusse teda identifitseeriv täisarv ehk räsi.

Objekti räsi peaks olema kiiresti väljaarvutatav ning tõenäosus, et

erinevate objektide räsid kokku langevad, peaks olema võimalikult väike.

Meetodi

Vaatleme klassi

class Isik {
    private String nimi;
    private int vanus;
    private int pikkus;
    public int hashCode() {
        return /* ... */;
    }
}

Märgi kõik laused, mis sobivad hästi meetodi hashCode() sisuks.