A hash tabula ir datu struktūra, kas ļauj ātri ievietot, dzēst un izgūt datus. Tas darbojas, izmantojot jaucējfunkciju, lai kartētu atslēgu ar indeksu masīvā. Šajā rakstā mēs ieviesīsim jaukšanas tabulu Python, izmantojot atsevišķu ķēdi, lai apstrādātu sadursmes.

Jaukšanas sastāvdaļas

Atsevišķa ķēde ir paņēmiens, ko izmanto, lai apstrādātu sadursmes hash tabulā. Ja divas vai vairākas atslēgas ir saistītas ar vienu un to pašu indeksu masīvā, mēs tās saglabājam saistītā sarakstā šajā indeksā. Tas ļauj mums vienā indeksā saglabāt vairākas vērtības un joprojām varēsim tās izgūt, izmantojot to atslēgu.

Veids, kā ieviest hash tabulu, izmantojot atsevišķu ķēdi

Veids, kā ieviest hash tabulu, izmantojot atsevišķu ķēdi:

Izveidojiet divas klases: ' Mezgls ' un ' HashTable '.

' Mezgls ‘ klase pārstāvēs mezglu saistītā sarakstā. Katrā mezglā būs atslēgas-vērtības pāris, kā arī rādītājs uz nākamo mezglu sarakstā.

Python3

class> Node:> > def> __init__(> self> , key, value):> > self> .key> => key> > self> .value> => value> > self> .> next> => None>

Klase “HashTable” saturēs masīvu, kurā būs saistītie saraksti, kā arī metodes datu ievietošanai, izgūšanai un dzēšanai no hash tabulas.

Python3

class> HashTable:> > def> __init__(> self> , capacity):> > self> .capacity> => capacity> > self> .size> => 0> > self> .table> => [> None> ]> *> capacity>

' __karsts__ ' metode inicializē jaucējtabulu ar noteiktu ietilpību. Tas nosaka ' jaudu ' un ' Izmērs ' mainīgie un inicializē masīvu uz 'Nav'.

Nākamā metode ir ' _hash ‘metode. Šī metode izmanto atslēgu un atgriež indeksu masīvā, kurā jāsaglabā atslēgas un vērtības pāris. Mēs izmantosim Python iebūvēto jaukšanas funkciju, lai sajauktu atslēgu, un pēc tam izmantosim modulo operatoru, lai iegūtu indeksu masīvā.

Python3

def> _hash(> self> , key):> > return> hash> (key)> %> self> .capacity>

The 'ievietot' metode ievietos atslēgas vērtību pāri jaucēj tabulā. Tas aizņem indeksu, kur pāris jāsaglabā, izmantojot ' _hash ‘metode. Ja šajā indeksā nav saistīta saraksta, tas izveido jaunu mezglu ar atslēgu-vērtību pāri un iestata to kā saraksta galveni. Ja šajā indeksā ir saistīts saraksts, atkārtojiet sarakstu, līdz tiek atrasts pēdējais mezgls vai atslēga jau pastāv, un atjauniniet vērtību, ja atslēga jau pastāv. Ja tā atrod atslēgu, tā atjaunina vērtību. Ja tas neatrod atslēgu, tas izveido jaunu mezglu un pievieno to saraksta augšdaļā.

Python3

def> insert(> self> , key, value):> > index> => self> ._hash(key)> > if> self> .table[index]> is> None> :> > self> .table[index]> => Node(key, value)> > self> .size> +> => 1> > else> :> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > current.value> => value> > return> > current> => current.> next> > new_node> => Node(key, value)> > new_node.> next> => self> .table[index]> > self> .table[index]> => new_node> > self> .size> +> => 1>

The Meklēt metode izgūst vērtību, kas saistīta ar doto atslēgu. Vispirms tiek iegūts indekss, kurā jāsaglabā atslēgas vērtību pāris, izmantojot _hash metodi. Pēc tam šī rādītāja saistītajā sarakstā tiek meklēta atslēga. Ja tā atrod atslēgu, tā atgriež saistīto vērtību. Ja tas neatrod atslēgu, tas paceļ a KeyError .

Python3

def> search(> self> , key):> > index> => self> ._hash(key)> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > return> current.value> > current> => current.> next> > raise> KeyError(key)>

The 'noņemt' metode noņem atslēgu-vērtību pāri no hash tabulas. Vispirms tiek iegūts indekss, kurā pāris jāsaglabā, izmantojot ` _hash ` metode. Pēc tam šī rādītāja saistītajā sarakstā tiek meklēta atslēga. Ja tas atrod atslēgu, tas noņem mezglu no saraksta. Ja tas neatrod atslēgu, tas paceļ ` KeyError `.

Python3

def> remove(> self> , key):> > index> => self> ._hash(key)> > > previous> => None> > current> => self> .table[index]> > > while> current:> > if> current.key> => => key:> > if> previous:> > previous.> next> => current.> next> > else> :> > self> .table[index]> => current.> next> > self> .size> -> => 1> > return> > previous> => current> > current> => current.> next> > > raise> KeyError(key)>

“__str__” metode, kas atgriež hash tabulas virknes attēlojumu.

Python3

def> __str__(> self> ):> > elements> => []> > for> i> in> range> (> self> .capacity):> > current> => self> .table[i]> > while> current:> > elements.append((current.key, current.value))> > current> => current.> next> > return> str> (elements)>

Šeit ir pilna klases “HashTable” ieviešana:

Python3

class> Node:> > def> __init__(> self> , key, value):> > self> .key> => key> > self> .value> => value> > self> .> next> => None> > > class> HashTable:> > def> __init__(> self> , capacity):> > self> .capacity> => capacity> > self> .size> => 0> > self> .table> => [> None> ]> *> capacity> > > def> _hash(> self> , key):> > return> hash> (key)> %> self> .capacity> > > def> insert(> self> , key, value):> > index> => self> ._hash(key)> > > if> self> .table[index]> is> None> :> > self> .table[index]> => Node(key, value)> > self> .size> +> => 1> > else> :> > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > current.value> => value> > return> > current> => current.> next> > new_node> => Node(key, value)> > new_node.> next> => self> .table[index]> > self> .table[index]> => new_node> > self> .size> +> => 1> > > def> search(> self> , key):> > index> => self> ._hash(key)> > > current> => self> .table[index]> > while> current:> > if> current.key> => => key:> > return> current.value> > current> => current.> next> > > raise> KeyError(key)> > > def> remove(> self> , key):> > index> => self> ._hash(key)> > > previous> => None> > current> => self> .table[index]> > > while> current:> > if> current.key> => => key:> > if> previous:> > previous.> next> => current.> next> > else> :> > self> .table[index]> => current.> next> > self> .size> -> => 1> > return> > previous> => current> > current> => current.> next> > > raise> KeyError(key)> > > def> __len__(> self> ):> > return> self> .size> > > def> __contains__(> self> , key):> > try> :> > self> .search(key)> > return> True> > except> KeyError:> > return> False> > > # Driver code> if> __name__> => => '__main__'> :> > > # Create a hash table with> > # a capacity of 5> > ht> => HashTable(> 5> )> > > # Add some key-value pairs> > # to the hash table> > ht.insert(> 'apple'> ,> 3> )> > ht.insert(> 'banana'> ,> 2> )> > ht.insert(> 'cherry'> ,> 5> )> > > # Check if the hash table> > # contains a key> > print> (> 'apple'> in> ht)> # True> > print> (> 'durian'> in> ht)> # False> > > # Get the value for a key> > print> (ht.search(> 'banana'> ))> # 2> > > # Update the value for a key> > ht.insert(> 'banana'> ,> 4> )> > print> (ht.search(> 'banana'> ))> # 4> > > ht.remove(> 'apple'> )> > # Check the size of the hash table> > print> (> len> (ht))> # 3>

Izvade

True False 2 4 3 

Laika un telpas sarežģītība:

• The laika sarežģītība no ievietot , Meklēt un noņemt Metodes hash tabulā, izmantojot atsevišķu ķēdi, ir atkarīgas no hash tabulas lieluma, atslēgu-vērtību pāru skaita jaukšanas tabulā un saistītā saraksta garuma katrā indeksā.
• Pieņemot labu jaucējfunkciju un vienmērīgu atslēgu sadalījumu, šo metožu paredzamā laika sarežģītība ir O(1) katrai operācijai. Tomēr sliktākajā gadījumā laika sarežģītība var būt O(n) , kur n ir atslēgu-vērtību pāru skaits hash tabulā.
• Tomēr ir svarīgi izvēlēties labu jaucējfunkciju un atbilstošu hash tabulas izmēru, lai samazinātu sadursmju iespējamību un nodrošinātu labu veiktspēju.
• The telpas sarežģītība jaucēj tabulas, izmantojot atsevišķu ķēdi, ir atkarīgs no jaucēj tabulas lieluma un jaucēja tabulā saglabāto atslēgu vērtību pāru skaita.
• Pati hash tabula ņem O(m) telpa, kur m ir hash tabulas ietilpība. Katrs saistītais saraksta mezgls aizņem O(1) telpa, un saistītajos sarakstos var būt ne vairāk kā n mezgli, kur n ir jaucēja tabulā saglabāto atslēgu-vērtību pāru skaits.
• Tāpēc kopējā telpas sarežģītība ir O(m + n) .

Secinājums:

Praksē ir svarīgi izvēlēties atbilstošu jaucēja tabulas ietilpību, lai līdzsvarotu telpas izmantošanu un sadursmju iespējamību. Ja jauda ir pārāk maza, palielinās sadursmju iespējamība, kas var izraisīt veiktspējas pasliktināšanos. No otras puses, ja ietilpība ir pārāk liela, hash tabula var patērēt vairāk atmiņas nekā nepieciešams.