Problem G
Hashtabell2
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
-
Öppet fall 1, se Sample Input 1 nedan.
-
Öppet fall 2, se Sample Input 2 nedan.
-
Initialisering av flera hashtabeller.
-
Används metoden hashfunction för indexberäkningen?
-
Alla nycklar krockar med varandra.
-
Ändring av värde för nyckel som har krockat.
-
Insättning av nycklar i slutet av tabellen.
-
Ä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 # |
