Hide

Problem G
Hashtabell2

/problems/kth.tilda.hashtabell2/file/statement/sv/img-0001.png
Kollisionshantering med probning.
Wikimedia, cc-by-sa 3.0

Här ska du testa din hashtabell.

Klassen Hashtable

Du skall skicka in en fil, hashtable.py, som innehåller en klass Hashtable med följande gränssnitt:

class Hashtable:
    def __init__(self, size):
        self.size = size 
        ...

    def store(self, key, data):
        ...

    def search(self, key):
        """Hämtar det objekt som finns lagrat med
        nyckeln "key" och returnerar det.
        Om "key" inte finns ska vi få en Exception,
        KeyError."""
        ...
        else:
            raise KeyError

    def hashfunction(self, key):
        ...

Vad svarar testrutorna mot

  1. Öppet fall 1, se Sample Input 1 nedan.

  2. Öppet fall 2, se Sample Input 2 nedan.

  3. Initialisering av flera hashtabeller.

  4. Används metoden hashfunction för indexberäkningen?

  5. Alla nycklar krockar med varandra.

  6. Ändring av värde för nyckel som har krockat.

  7. Insättning av nycklar i slutet av tabellen.

  8. Är tidskomplexiteten $O(1)$ för sökning? Stort fall.

Testningen bryts redan på första rutan om filen, klassen, metoderna eller attributet size saknas. Samma gäller om din klass använder dict, Pythons inbyggda hashtabell. Det gör till exempel DictHash.

Input

Den här kattisuppgiften innehåller sin egen main.py som läser indata, anropar metoderna i din kod och skriver ut svaret. Du behöver bara skicka in hashtable.py.

Filen måste laddas upp! Editorn på submitsidan döper din inskickade fil till hashtabell2.py.

Indata består av insättningar och sökningar blandade. En rad kan se ut på fyra sätt:

  • Initialisering – init <size>, skapar ny hashtabell size lång.

  • Insättning – nyckelsträng och värdesträng skilda åt med minst ett mellanslag eller tabulatortecken eller en blandning av dem.

  • Sökning – nyckelsträng.

  • Sista raden – #.

Output

För varje indatarad skall en utdatarad skrivas.

  • Initialisering – bekräftas med, New size: <size>.

  • Insättning – bekräftas med, <nyckelsträng> <– <värdesträng>.

  • Sökning har två fall:

    • Om nyckeln hittas ska programmet svara med värdet.

    • Om nyckeln inte finns skall programmet svara med, KeyError: <nyckelsträng>.

  • Sista raden – #.

Sample Input 1 Sample Output 1
init 5
H
H 1
H
H 1.00794
H
He
He 4
He
He 4.002602
He
H
#
New size: 5
KeyError: H
H <- 1
H: 1
H <- 1.00794
H: 1.00794
KeyError: He
He <- 4
He: 4
He <- 4.002602
He: 4.002602
H: 1.00794
#
Sample Input 2 Sample Output 2
init 227
H  1.00794
He 4.002602
Li 6.941
Be 9.012182
B  10.811
C  12.0107
N  14.0067
O  15.9994
F  18.9984032
Ne 20.1797
Na 22.98976928
Mg 24.3050
Al 26.9815386
Si 28.0855
P  30.973762
S  32.065
Cl 35.453
K  39.0983
Ar 39.948
Ca 40.078
Sc 44.955912
Ti 47.867
V  50.9415
Cr 51.9961
Mn 54.938045
Fe 55.845
Ni 58.6934
Co 58.933195
Cu 63.546
Zn 65.38
Ga 69.723
Ge 72.64
As 74.92160
Se 78.96
Br 79.904
Kr 83.798
Rb 85.4678
Sr 87.62
Y  88.90585
Zr 91.224
Nb 92.90638
Mo 95.96
Tc 98
Ru 101.07
Rh 102.90550
Pd 106.42
Ag 107.8682
Cd 112.411
In 114.818
Sn 118.710
Sb 121.760
I  126.90447
Te 127.60
Xe 131.293
Cs 132.9054519
Ba 137.327
La 138.90547
Ce 140.116
Pr 140.90765
Nd 144.242
Pm 145
Sm 150.36
Eu 151.964
Gd 157.25
Tb 158.92535
Dy 162.500
Ho 164.93032
Er 167.259
Tm 168.93421
Yb 173.054
Lu 174.9668
Hf 178.49
Ta 180.94788
W  183.84
Re 186.207
Os 190.23
Ir 192.217
Pt 195.084
Au 196.966569
Hg 200.59
Tl 204.3833
Pb 207.2
Bi 208.98040
Po 209
At 210
Rn 222
Fr 223
Ra 226
Ac 227
Pa 231.03588
Th 232.03806
Np 237
U  238.02891
Am 243
Pu 244
Cm 247
Bk 247
Cf 251
Es 252
Fm 257
Md 258
No 259
Lr 262
Rf 265
Db 268
Hs 270
Sg 271
Bh 272
Mt 276
Rg 280
Ds 281
Cn 285
H
He
Li
Be
B
C
N
O
F
Ne
Na
Mg
Al
Si
P
S
Cl
K
Ar
Ca
Sc
Ti
V
Cr
Mn
Fe
Ni
Co
Cu
Zn
Ga
Ge
As
Se
Br
Kr
Rb
Sr
Y
Zr
Nb
Mo
Tc
Ru
Rh
Pd
Ag
Cd
In
Sn
Sb
I
Te
Xe
Cs
Ba
La
Ce
Pr
Nd
Pm
Sm
Eu
Gd
Tb
Dy
Ho
Er
Tm
Yb
Lu
Hf
Ta
W
Re
Os
Ir
Pt
Au
Hg
Tl
Pb
Bi
Po
At
Rn
Fr
Ra
Ac
Pa
Th
Np
U
Am
Pu
Cm
Bk
Cf
Es
Fm
Md
No
Lr
Rf
Db
Hs
Sg
Bh
Mt
Rg
Ds
Cn
#
New size: 227
H <- 1.00794
He <- 4.002602
Li <- 6.941
Be <- 9.012182
B <- 10.811
C <- 12.0107
N <- 14.0067
O <- 15.9994
F <- 18.9984032
Ne <- 20.1797
Na <- 22.98976928
Mg <- 24.3050
Al <- 26.9815386
Si <- 28.0855
P <- 30.973762
S <- 32.065
Cl <- 35.453
K <- 39.0983
Ar <- 39.948
Ca <- 40.078
Sc <- 44.955912
Ti <- 47.867
V <- 50.9415
Cr <- 51.9961
Mn <- 54.938045
Fe <- 55.845
Ni <- 58.6934
Co <- 58.933195
Cu <- 63.546
Zn <- 65.38
Ga <- 69.723
Ge <- 72.64
As <- 74.92160
Se <- 78.96
Br <- 79.904
Kr <- 83.798
Rb <- 85.4678
Sr <- 87.62
Y <- 88.90585
Zr <- 91.224
Nb <- 92.90638
Mo <- 95.96
Tc <- 98
Ru <- 101.07
Rh <- 102.90550
Pd <- 106.42
Ag <- 107.8682
Cd <- 112.411
In <- 114.818
Sn <- 118.710
Sb <- 121.760
I <- 126.90447
Te <- 127.60
Xe <- 131.293
Cs <- 132.9054519
Ba <- 137.327
La <- 138.90547
Ce <- 140.116
Pr <- 140.90765
Nd <- 144.242
Pm <- 145
Sm <- 150.36
Eu <- 151.964
Gd <- 157.25
Tb <- 158.92535
Dy <- 162.500
Ho <- 164.93032
Er <- 167.259
Tm <- 168.93421
Yb <- 173.054
Lu <- 174.9668
Hf <- 178.49
Ta <- 180.94788
W <- 183.84
Re <- 186.207
Os <- 190.23
Ir <- 192.217
Pt <- 195.084
Au <- 196.966569
Hg <- 200.59
Tl <- 204.3833
Pb <- 207.2
Bi <- 208.98040
Po <- 209
At <- 210
Rn <- 222
Fr <- 223
Ra <- 226
Ac <- 227
Pa <- 231.03588
Th <- 232.03806
Np <- 237
U <- 238.02891
Am <- 243
Pu <- 244
Cm <- 247
Bk <- 247
Cf <- 251
Es <- 252
Fm <- 257
Md <- 258
No <- 259
Lr <- 262
Rf <- 265
Db <- 268
Hs <- 270
Sg <- 271
Bh <- 272
Mt <- 276
Rg <- 280
Ds <- 281
Cn <- 285
H: 1.00794
He: 4.002602
Li: 6.941
Be: 9.012182
B: 10.811
C: 12.0107
N: 14.0067
O: 15.9994
F: 18.9984032
Ne: 20.1797
Na: 22.98976928
Mg: 24.3050
Al: 26.9815386
Si: 28.0855
P: 30.973762
S: 32.065
Cl: 35.453
K: 39.0983
Ar: 39.948
Ca: 40.078
Sc: 44.955912
Ti: 47.867
V: 50.9415
Cr: 51.9961
Mn: 54.938045
Fe: 55.845
Ni: 58.6934
Co: 58.933195
Cu: 63.546
Zn: 65.38
Ga: 69.723
Ge: 72.64
As: 74.92160
Se: 78.96
Br: 79.904
Kr: 83.798
Rb: 85.4678
Sr: 87.62
Y: 88.90585
Zr: 91.224
Nb: 92.90638
Mo: 95.96
Tc: 98
Ru: 101.07
Rh: 102.90550
Pd: 106.42
Ag: 107.8682
Cd: 112.411
In: 114.818
Sn: 118.710
Sb: 121.760
I: 126.90447
Te: 127.60
Xe: 131.293
Cs: 132.9054519
Ba: 137.327
La: 138.90547
Ce: 140.116
Pr: 140.90765
Nd: 144.242
Pm: 145
Sm: 150.36
Eu: 151.964
Gd: 157.25
Tb: 158.92535
Dy: 162.500
Ho: 164.93032
Er: 167.259
Tm: 168.93421
Yb: 173.054
Lu: 174.9668
Hf: 178.49
Ta: 180.94788
W: 183.84
Re: 186.207
Os: 190.23
Ir: 192.217
Pt: 195.084
Au: 196.966569
Hg: 200.59
Tl: 204.3833
Pb: 207.2
Bi: 208.98040
Po: 209
At: 210
Rn: 222
Fr: 223
Ra: 226
Ac: 227
Pa: 231.03588
Th: 232.03806
Np: 237
U: 238.02891
Am: 243
Pu: 244
Cm: 247
Bk: 247
Cf: 251
Es: 252
Fm: 257
Md: 258
No: 259
Lr: 262
Rf: 265
Db: 268
Hs: 270
Sg: 271
Bh: 272
Mt: 276
Rg: 280
Ds: 281
Cn: 285
#

Please log in to submit a solution to this problem

Log in