Informatika1-2014/eloadas4
(Új oldal, tartalma: „=== Listák === Ugyanúgy lehet '''szeletelni (slice)''', összeadni, többszörözni, mint a karakterláncot, de '''a lista változtatható (mutable)''': <python> >>…”) |
|||
(egy szerkesztő 7 közbeeső változata nincs mutatva) | |||
1. sor: | 1. sor: | ||
+ | == Gyűteményes adatszerkezetek, adatstruktúrák == | ||
+ | |||
+ | Érdemes a Python saját [https://docs.python.org/2/tutorial/datastructures.html tutoralját] is elolvasni. | ||
+ | |||
=== Listák === | === Listák === | ||
− | Ugyanúgy lehet '''szeletelni (slice)''', összeadni, többszörözni, mint a karakterláncot, de '''a lista változtatható (mutable)''': | + | Ugyanúgy lehet '''szeletelni (slice)''', mint a karakterláncot: |
+ | |||
+ | <python> | ||
+ | >>> x = [1, 2, 3, 4] | ||
+ | >>> x[1] | ||
+ | 2 | ||
+ | >>> x[2:] | ||
+ | [3, 4] | ||
+ | >>> x[0::2] | ||
+ | [1, 3] | ||
+ | >>> x[:] | ||
+ | [1, 2, 3, 4] | ||
+ | >>> x[-1:-3] | ||
+ | [] | ||
+ | >>> x[-1:-3:-1] | ||
+ | [4, 3] | ||
+ | >>> x[-1::-1] | ||
+ | [4, 3, 2, 1] | ||
+ | </python> | ||
+ | |||
+ | Ugyanúgy lehet összeadni, többszörözni, mint a karakterláncot, de '''a lista változtatható (mutable)''': | ||
<python> | <python> | ||
11. sor: | 35. sor: | ||
File "<stdin>", line 1, in <module> | File "<stdin>", line 1, in <module> | ||
TypeError: can only concatenate list (not "int") to list | TypeError: can only concatenate list (not "int") to list | ||
− | |||
− | |||
− | |||
− | |||
</python> | </python> | ||
36. sor: | 56. sor: | ||
− | ==== | + | ==== Listák kezelése, metódusai ==== |
Lista létrehozható értékadással, [] az üres lista. A range parancs is listát ad vissza: | Lista létrehozható értékadással, [] az üres lista. A range parancs is listát ad vissza: | ||
+ | |||
<python> | <python> | ||
>>> range(3) | >>> range(3) | ||
47. sor: | 68. sor: | ||
>>> range(1,10,3) | >>> range(1,10,3) | ||
[1, 4, 7] | [1, 4, 7] | ||
+ | </python> | ||
+ | |||
+ | A lehetséges metódusok például kiírhatók TAB billentyűvel ipythonban: | ||
+ | |||
+ | <python> | ||
+ | In [31]: x = range(1,5); x | ||
+ | Out[31]: [1, 2, 3, 4] | ||
+ | |||
+ | In [32]: x.append(99); x | ||
+ | Out[32]: [1, 2, 3, 4, 99] | ||
+ | |||
+ | In [33]: x. | ||
+ | x.append x.extend x.insert x.remove x.sort | ||
+ | x.count x.index x.pop x.reverse | ||
+ | |||
+ | In [33]: x.extend([1,1,1]); x | ||
+ | Out[33]: [1, 2, 3, 4, 99, 1, 1, 1] | ||
+ | |||
+ | In [34]: x.count(1); x | ||
+ | Out[34]: [1, 2, 3, 4, 99, 1, 1, 1] | ||
+ | |||
+ | In [35]: x.index(2) | ||
+ | Out[35]: 1 | ||
+ | |||
+ | In [36]: x.insert(4,5); x | ||
+ | Out[36]: [1, 2, 3, 4, 5, 99, 1, 1, 1] | ||
+ | |||
+ | In [37]: x.pop(5); x | ||
+ | Out[37]: [1, 2, 3, 4, 5, 1, 1, 1] | ||
+ | |||
+ | In [38]: x.re | ||
+ | x.remove x.reverse | ||
+ | |||
+ | In [38]: x.reverse(); x | ||
+ | Out[38]: [1, 1, 1, 5, 4, 3, 2, 1] | ||
+ | |||
+ | In [39]: x.remove(1); x | ||
+ | Out[39]: [1, 1, 5, 4, 3, 2, 1] | ||
+ | |||
+ | In [40]: x.sort(); x | ||
+ | Out[40]: [1, 1, 1, 2, 3, 4, 5] | ||
+ | </python> | ||
+ | |||
+ | ==== Listaértelmezés ==== | ||
+ | |||
+ | '''''Írjuk egy listába a 100-nál kisebb nem negatív négyzetszámokat!''''' Egy megoldás: | ||
+ | |||
+ | <python> | ||
+ | >>> negyzetek = [] | ||
+ | >>> for x in range(10): | ||
+ | negyzetek.append(x**2) | ||
+ | |||
+ | >>> negyzetek | ||
+ | [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] | ||
+ | </python> | ||
+ | |||
+ | Egy egyszerű -- igazi Pythonos -- megoldás: | ||
+ | |||
+ | <python> | ||
+ | >>> negyzetek = [x**2 for x in range(10)] | ||
+ | </python> | ||
+ | |||
+ | Rövid listák létrehozásának egyszerű módja a listaértelmezés. Általános alakja: | ||
+ | <python> | ||
+ | [expression for expr in sequence1 | ||
+ | if condition1 | ||
+ | for expr2 in sequence2 | ||
+ | if condition2 | ||
+ | ... | ||
+ | for exprN in sequenceN | ||
+ | if conditionN] | ||
+ | </python> | ||
+ | Kis programrészek helyettesíthetők vele. Például '''''soroljuk fel az 1890 és 1915 közé eső szökőéveket!''''' | ||
+ | |||
+ | <python> | ||
+ | szoko = [] | ||
+ | for ev in range(1890, 1922): | ||
+ | if (ev%4 == 0 and ev%100 != 0) or (ev%400 == 0): | ||
+ | szoko.append(ev) | ||
+ | print szoko | ||
+ | [1892, 1896, 1904, 1908, 1912, 1916, 1920] | ||
+ | </python> | ||
+ | Lépésenként egyre összetettebb listaértelmezéssel állítsuk elő ugyanezt: | ||
+ | <python> | ||
+ | >>> szoko = [ev for ev in range(1890, 1915)] | ||
+ | >>> szoko # ez még az összes év | ||
+ | [1890, 1891, 1892, 1893, 1894, 1895, 1896, 1897, 1898, 1899, 1900, 1901, 1902, 1903, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914] | ||
+ | >>> szoko = [ev for ev in range(1890, 1915) if ev%4 == 0] | ||
+ | >>> szoko # ez a 4-gyel osztható évek listája | ||
+ | [1892, 1896, 1900, 1904, 1908, 1912] | ||
+ | >>> szoko = [ev for ev in range(1890, 1915) | ||
+ | if (ev%4 == 0 and ev%100 != 0) or ev%400 == 0] | ||
+ | >>> szoko | ||
+ | [1892, 1896, 1904, 1908, 1912] | ||
+ | </python> | ||
+ | |||
+ | |||
+ | ==== del utasítás ==== | ||
+ | |||
+ | A del utasítással törölhetők elemek, a lista tartalma vagy az egész lista: | ||
+ | |||
+ | <python> | ||
+ | >>> l = range(2,7) | ||
+ | >>> del l[2]; l | ||
+ | [2, 3, 5, 6] | ||
+ | >>> del l[:]; l | ||
+ | [] | ||
+ | >>> del l | ||
+ | >>> l | ||
+ | Traceback (most recent call last): | ||
+ | File "<stdin>", line 1, in <module> | ||
+ | NameError: name 'l' is not defined | ||
+ | </python> | ||
+ | |||
+ | === Sorozat (tuple) === | ||
+ | |||
+ | Változtathatatlan (immutable), mint a karakterlánc, műveletei: | ||
+ | szeletelés [], összefűzés (+), szorzás (*), összehasonlítás, tagsági viszony (in, not in) | ||
+ | <python> | ||
+ | >>> t = () | ||
+ | >>> t | ||
+ | () | ||
+ | >>> t = 1, 5, 5, 5, 3 # itt elhagyható a zárójel | ||
+ | >>> t | ||
+ | (1, 5, 5, 5, 3) | ||
+ | >>> t[1] | ||
+ | 5 | ||
+ | >>> t.index(3) | ||
+ | 4 | ||
+ | >>> t.count(5) | ||
+ | 3 | ||
+ | >>> t[0] = 9 | ||
+ | Traceback (most recent call last): | ||
+ | File "<stdin>", line 1, in <module> | ||
+ | TypeError: 'tuple' object does not support item assignment | ||
+ | </python> | ||
+ | |||
+ | Maga nem változtatható, de változtatható elemei lehetnek: | ||
+ | |||
+ | <python> | ||
+ | >>> t = [1,2], [3,4,5], 6 | ||
+ | >>> t | ||
+ | ([1, 2], [3, 4, 5], 6) | ||
+ | </python> | ||
+ | |||
+ | Az üres és az 1-hosszú sorozat kényes dolog, mert a ()-jeleket másra is használjuk: | ||
+ | |||
+ | <python> | ||
+ | >>> t=() | ||
+ | >>> t | ||
+ | () | ||
+ | >>> t = (3) | ||
+ | >>> type(t) | ||
+ | <type 'int'> | ||
+ | >>> t = 3, | ||
+ | >>> type(t) | ||
+ | <type 'tuple'> | ||
+ | </python> | ||
+ | |||
+ | A sorozatba való be- és kicsomagolás: | ||
+ | |||
+ | <python> | ||
+ | >>> t = 2, 3, 4 | ||
+ | >>> t | ||
+ | (2, 3, 4) | ||
+ | >>> x, y, z = t | ||
+ | >>> x, y, z | ||
+ | (2, 3, 4) | ||
+ | >>> x | ||
+ | 2 | ||
+ | </python> | ||
+ | |||
+ | === Halmaz (set) === | ||
+ | |||
+ | A halmaz rendezetlen, duplikált elemek nélküli gyűjteményes adattípus. Tagsági viszony gyorsabb ellenőrzésére, duplikált elemek törlésére használható. A matematikai halmazműveletek használhatók. | ||
+ | |||
+ | <python> | ||
+ | >>> a = set('matematika'); a | ||
+ | set(['a', 'e', 'i', 'k', 'm', 't']) | ||
+ | >>> b = set('matek'); b | ||
+ | set(['a', 'e', 'k', 'm', 't']) | ||
+ | >>> a - b # halmazok különbsége | ||
+ | set(['i']) | ||
+ | >>> b - a | ||
+ | set([]) | ||
+ | >>> a | b # halmazok uniója (vagy) | ||
+ | set(['a', 'e', 'i', 'k', 'm', 't']) | ||
+ | >>> a & b # halmazok metszete (és) | ||
+ | set(['a', 'm', 'k', 'e', 't']) | ||
+ | >>> a ^ b # halmazok szimmetrikus differenciája (kizáró vagy) | ||
+ | set(['i']) | ||
+ | </python> | ||
+ | |||
+ | Bevitelnél a kapcsos zárójel is használható, kivéve az üres halmazt: | ||
+ | |||
+ | <python> | ||
+ | >>> t = {1, 2, 3, 4} | ||
+ | >>> type(t) | ||
+ | <type 'set'> | ||
+ | >>> t | ||
+ | set([1, 2, 3, 4]) | ||
+ | >>> t = {} | ||
+ | >>> type(t) | ||
+ | <type 'dict'> | ||
+ | </python> | ||
+ | |||
+ | |||
+ | A listaértelmezéshez hasonlóan van halmazértelmezés is: | ||
+ | |||
+ | <python> | ||
+ | >>> {x for x in 'asztrológia' if x not in 'asztronómia'} | ||
+ | set(['l', 'g']) | ||
+ | </python> | ||
+ | |||
+ | |||
+ | |||
+ | === Szótár (dict) === | ||
+ | |||
+ | A szótár kulcs-érték párokból álló halmaz. Nem a 0, 1, 2,... számokkal van indexelve, mint a sorozat vagy a karakterlánc, hanem bármilyen nem változtatható objektumokkal. Ezeket nevezzük kulcsnak. A kulcs tehát lehet szám, karakterlánc, sorozat, de nem lehet lista. A kulcshoz tartozó érték bármi lehet. Egy szótárban minden kulcsból csak egy lehet. | ||
+ | |||
+ | <python> | ||
+ | >>> tel = {'Laci': 1243, 'Ági': 2221, 'Zoli': 3321} | ||
+ | >>> type(tel) | ||
+ | <type 'dict'> | ||
+ | >>> tel['Laci'] | ||
+ | 1243 | ||
+ | >>> tel = dict([('Laci',1243), ('Ági',2221), ('Zoli',3321)]) | ||
+ | >>> tel['Laci'] | ||
+ | 1243 | ||
+ | >>> tel = dict(Laci=1243, Ági=2221, Zoli=3321) | ||
+ | File "<stdin>", line 1 | ||
+ | tel = dict(Laci=1243, Ági=2221, Zoli=3321) | ||
+ | ^ | ||
+ | SyntaxError: invalid syntax | ||
+ | >>> tel = dict(Laci=1243, Agi=2221, Zoli=3321) | ||
+ | >>> tel['Agi'] | ||
+ | 2221 | ||
+ | </python> | ||
+ | |||
+ | A listaértelmezésnek szótárakra is van változata: | ||
+ | |||
+ | <python> | ||
+ | >>> {x: x**3 for x in (11, 12, 13)} | ||
+ | {11: 1331, 12: 1728, 13: 2197} | ||
+ | </python> | ||
+ | |||
+ | ==== Hasító tábla (hash table) ==== | ||
+ | |||
+ | Általában a '''hash tábla''' (hash table, '''hasító tábla''') egy olyan adatszerkezet, amely egy hash függvény (hasító függvény) segítségével állapítja meg, hogy melyik kulcshoz milyen érték tartozik. A Python dict adattípusa hash tábla. A hash függvény minden objektumhoz egy véges tartományba eső egész számot rendel. A hash tábla kezelésekor kezelni kell az esetleges ütközéseket, azaz azokat az eseteket, amikor két különböző kulcshoz azonos hash-érték tartozik. A Python a hash függvény értékkészletébe eső egészeken az identikus leképezés, tehát | ||
+ | <python> | ||
+ | >>> hash(1) | ||
+ | 1 | ||
+ | >>> hash(1.0) | ||
+ | 1 | ||
+ | >>> hash(1123) | ||
+ | 1123 | ||
+ | >>> hash(-1123) | ||
+ | -1123 | ||
+ | >>> hash(1111111111111111111111111111) | ||
+ | 497554224548382901 | ||
+ | </python> | ||
+ | |||
+ | Így e függvényhez könnyű '''ütközést''' kreálni (a születésnapi paradoxon is besegít), de a gyakorlatban nagyon ritka, és a hash tábla kezelés föl van ilyen esetekre készülve (a kriptográfiai célokra használt hash függvényt úgy kell megkonstruálni, hogy ütközést belátható időn belül ne lehessen könnyen találni). | ||
+ | |||
+ | <python> | ||
+ | >>> hash(0.1) | ||
+ | 2576882278 | ||
+ | >>> hash(2576882278) | ||
+ | 2576882278 | ||
+ | </python> | ||
+ | |||
+ | Csak változtathatatlan (immutable) objektumoknak lehet hash értéke: | ||
+ | |||
+ | <python> | ||
+ | >>> l = [1, 2] # változtatható (mutable) | ||
+ | >>> c = "hash" # változtathatatlan (immutable) | ||
+ | >>> hash(c) | ||
+ | 7799588877615763652 | ||
+ | >>> hash(l) | ||
+ | Traceback (most recent call last): | ||
+ | File "<stdin>", line 1, in <module> | ||
+ | TypeError: unhashable type: 'list' | ||
</python> | </python> |
A lap jelenlegi, 2014. október 14., 13:01-kori változata
Tartalomjegyzék |
Gyűteményes adatszerkezetek, adatstruktúrák
Érdemes a Python saját tutoralját is elolvasni.
Listák
Ugyanúgy lehet szeletelni (slice), mint a karakterláncot:
>>> x = [1, 2, 3, 4] >>> x[1] 2 >>> x[2:] [3, 4] >>> x[0::2] [1, 3] >>> x[:] [1, 2, 3, 4] >>> x[-1:-3] [] >>> x[-1:-3:-1] [4, 3] >>> x[-1::-1] [4, 3, 2, 1]
Ugyanúgy lehet összeadni, többszörözni, mint a karakterláncot, de a lista változtatható (mutable):
>>> x = [1, 2, 3, 4] >>> x[:2]*2 + x[-1:] [1, 2, 1, 2, 4] >>> x[:2]*2 + x[-1] Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: can only concatenate list (not "int") to list
Az értékadás (=) csak objektumhivatkozással jár, nem történik adatmásolás. Ennek következtében egy y = x
parancs után, ahol x lista (vagy valamilyen más gyűjteményes adattípus), az y ugyanarra az objektumra fog mutatni. Így ha megváltoztatjuk x-et vagy y-t, változik a másik is. Az objektumhivatkozások megtörténhetnek egy szinttel mélyebben is, a (z = x[:]
kód esetén az x elemeire mutató hivatkozások másolódnak, de ekkor sem jön létre a teljes objektumról másolat. Ezt hívjuk
sekély másolásnak (shallow copy).
Egy másik példa sekély másolásra:
Mély másolás (deep copy), amikor valóban új példány keletkezik az objektumból:
import copy w = copy.deepcopy(x)
Listák kezelése, metódusai
Lista létrehozható értékadással, [] az üres lista. A range parancs is listát ad vissza:
>>> range(3) [0, 1, 2] >>> range(3, 6) [3, 4, 5] >>> range(1,10,3) [1, 4, 7]
A lehetséges metódusok például kiírhatók TAB billentyűvel ipythonban:
In [31]: x = range(1,5); x Out[31]: [1, 2, 3, 4] In [32]: x.append(99); x Out[32]: [1, 2, 3, 4, 99] In [33]: x. x.append x.extend x.insert x.remove x.sort x.count x.index x.pop x.reverse In [33]: x.extend([1,1,1]); x Out[33]: [1, 2, 3, 4, 99, 1, 1, 1] In [34]: x.count(1); x Out[34]: [1, 2, 3, 4, 99, 1, 1, 1] In [35]: x.index(2) Out[35]: 1 In [36]: x.insert(4,5); x Out[36]: [1, 2, 3, 4, 5, 99, 1, 1, 1] In [37]: x.pop(5); x Out[37]: [1, 2, 3, 4, 5, 1, 1, 1] In [38]: x.re x.remove x.reverse In [38]: x.reverse(); x Out[38]: [1, 1, 1, 5, 4, 3, 2, 1] In [39]: x.remove(1); x Out[39]: [1, 1, 5, 4, 3, 2, 1] In [40]: x.sort(); x Out[40]: [1, 1, 1, 2, 3, 4, 5]
Listaértelmezés
Írjuk egy listába a 100-nál kisebb nem negatív négyzetszámokat! Egy megoldás:
>>> negyzetek = [] >>> for x in range(10): negyzetek.append(x**2) >>> negyzetek [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
Egy egyszerű -- igazi Pythonos -- megoldás:
>>> negyzetek = [x**2 for x in range(10)]
Rövid listák létrehozásának egyszerű módja a listaértelmezés. Általános alakja:
[expression for expr in sequence1 if condition1 for expr2 in sequence2 if condition2 ... for exprN in sequenceN if conditionN]
Kis programrészek helyettesíthetők vele. Például soroljuk fel az 1890 és 1915 közé eső szökőéveket!
szoko = [] for ev in range(1890, 1922): if (ev%4 == 0 and ev%100 != 0) or (ev%400 == 0): szoko.append(ev) print szoko [1892, 1896, 1904, 1908, 1912, 1916, 1920]
Lépésenként egyre összetettebb listaértelmezéssel állítsuk elő ugyanezt:
>>> szoko = [ev for ev in range(1890, 1915)] >>> szoko # ez még az összes év [1890, 1891, 1892, 1893, 1894, 1895, 1896, 1897, 1898, 1899, 1900, 1901, 1902, 1903, 1904, 1905, 1906, 1907, 1908, 1909, 1910, 1911, 1912, 1913, 1914] >>> szoko = [ev for ev in range(1890, 1915) if ev%4 == 0] >>> szoko # ez a 4-gyel osztható évek listája [1892, 1896, 1900, 1904, 1908, 1912] >>> szoko = [ev for ev in range(1890, 1915) if (ev%4 == 0 and ev%100 != 0) or ev%400 == 0] >>> szoko [1892, 1896, 1904, 1908, 1912]
del utasítás
A del utasítással törölhetők elemek, a lista tartalma vagy az egész lista:
>>> l = range(2,7) >>> del l[2]; l [2, 3, 5, 6] >>> del l[:]; l [] >>> del l >>> l Traceback (most recent call last): File "<stdin>", line 1, in <module> NameError: name 'l' is not defined
Sorozat (tuple)
Változtathatatlan (immutable), mint a karakterlánc, műveletei: szeletelés [], összefűzés (+), szorzás (*), összehasonlítás, tagsági viszony (in, not in)
>>> t = () >>> t () >>> t = 1, 5, 5, 5, 3 # itt elhagyható a zárójel >>> t (1, 5, 5, 5, 3) >>> t[1] 5 >>> t.index(3) 4 >>> t.count(5) 3 >>> t[0] = 9 Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: 'tuple' object does not support item assignment
Maga nem változtatható, de változtatható elemei lehetnek:
>>> t = [1,2], [3,4,5], 6 >>> t ([1, 2], [3, 4, 5], 6)
Az üres és az 1-hosszú sorozat kényes dolog, mert a ()-jeleket másra is használjuk:
>>> t=() >>> t () >>> t = (3) >>> type(t) <type 'int'> >>> t = 3, >>> type(t) <type 'tuple'>
A sorozatba való be- és kicsomagolás:
>>> t = 2, 3, 4 >>> t (2, 3, 4) >>> x, y, z = t >>> x, y, z (2, 3, 4) >>> x 2
Halmaz (set)
A halmaz rendezetlen, duplikált elemek nélküli gyűjteményes adattípus. Tagsági viszony gyorsabb ellenőrzésére, duplikált elemek törlésére használható. A matematikai halmazműveletek használhatók.
>>> a = set('matematika'); a set(['a', 'e', 'i', 'k', 'm', 't']) >>> b = set('matek'); b set(['a', 'e', 'k', 'm', 't']) >>> a - b # halmazok különbsége set(['i']) >>> b - a set([]) >>> a | b # halmazok uniója (vagy) set(['a', 'e', 'i', 'k', 'm', 't']) >>> a & b # halmazok metszete (és) set(['a', 'm', 'k', 'e', 't']) >>> a ^ b # halmazok szimmetrikus differenciája (kizáró vagy) set(['i'])
Bevitelnél a kapcsos zárójel is használható, kivéve az üres halmazt:
>>> t = {1, 2, 3, 4} >>> type(t) <type 'set'> >>> t set([1, 2, 3, 4]) >>> t = {} >>> type(t) <type 'dict'>
A listaértelmezéshez hasonlóan van halmazértelmezés is:
>>> {x for x in 'asztrológia' if x not in 'asztronómia'} set(['l', 'g'])
Szótár (dict)
A szótár kulcs-érték párokból álló halmaz. Nem a 0, 1, 2,... számokkal van indexelve, mint a sorozat vagy a karakterlánc, hanem bármilyen nem változtatható objektumokkal. Ezeket nevezzük kulcsnak. A kulcs tehát lehet szám, karakterlánc, sorozat, de nem lehet lista. A kulcshoz tartozó érték bármi lehet. Egy szótárban minden kulcsból csak egy lehet.
>>> tel = {'Laci': 1243, 'Ági': 2221, 'Zoli': 3321} >>> type(tel) <type 'dict'> >>> tel['Laci'] 1243 >>> tel = dict([('Laci',1243), ('Ági',2221), ('Zoli',3321)]) >>> tel['Laci'] 1243 >>> tel = dict(Laci=1243, Ági=2221, Zoli=3321) File "<stdin>", line 1 tel = dict(Laci=1243, Ági=2221, Zoli=3321) ^ SyntaxError: invalid syntax >>> tel = dict(Laci=1243, Agi=2221, Zoli=3321) >>> tel['Agi'] 2221
A listaértelmezésnek szótárakra is van változata:
>>> {x: x**3 for x in (11, 12, 13)} {11: 1331, 12: 1728, 13: 2197}
Hasító tábla (hash table)
Általában a hash tábla (hash table, hasító tábla) egy olyan adatszerkezet, amely egy hash függvény (hasító függvény) segítségével állapítja meg, hogy melyik kulcshoz milyen érték tartozik. A Python dict adattípusa hash tábla. A hash függvény minden objektumhoz egy véges tartományba eső egész számot rendel. A hash tábla kezelésekor kezelni kell az esetleges ütközéseket, azaz azokat az eseteket, amikor két különböző kulcshoz azonos hash-érték tartozik. A Python a hash függvény értékkészletébe eső egészeken az identikus leképezés, tehát
>>> hash(1) 1 >>> hash(1.0) 1 >>> hash(1123) 1123 >>> hash(-1123) -1123 >>> hash(1111111111111111111111111111) 497554224548382901
Így e függvényhez könnyű ütközést kreálni (a születésnapi paradoxon is besegít), de a gyakorlatban nagyon ritka, és a hash tábla kezelés föl van ilyen esetekre készülve (a kriptográfiai célokra használt hash függvényt úgy kell megkonstruálni, hogy ütközést belátható időn belül ne lehessen könnyen találni).
>>> hash(0.1) 2576882278 >>> hash(2576882278) 2576882278
Csak változtathatatlan (immutable) objektumoknak lehet hash értéke:
>>> l = [1, 2] # változtatható (mutable) >>> c = "hash" # változtathatatlan (immutable) >>> hash(c) 7799588877615763652 >>> hash(l) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unhashable type: 'list'