Kot vemo, je HashSet znan razred v Javi. HashSet se uporablja za shranjevanje vrednosti z uporabo zgoščene tabele. V tej vadnici bomo obravnavali HashSet v Pythonu. Spoznali bomo tudi, kako lahko oblikujemo HashSet v Pythonu.
HashSet je temeljna podatkovna struktura v programiranju, ki jo običajno najdemo v jezikih, kot je Java. Spada v Java Collections Framework in služi kot implementacija nastavljenega vmesnika. Posebnost HashSeta je njegova sposobnost shranjevanja elementov na način, ki omogoča učinkovito preverjanje obstoja določenih elementov in zagotavlja edinstvenost znotraj niza. Za razliko od struktur, kot so seznami, HashSet ne vzdržuje posebnega vrstnega reda med svojimi elementi.
Ena od ključnih značilnosti HashSeta je jamstvo za edinstvenost; ne dovoljuje podvojenih elementov. Operacije, kot so dodajanje, odstranjevanje in preverjanje prisotnosti elementov, imajo običajno konstantno povprečno zmogljivost, zaradi česar je učinkovita izbira za takšne naloge. Vendar pa je pomembno upoštevati, da vrstni red elementov v HashSet ni zajamčen.
Ključne značilnosti:
Edinstvenost: HashSet ne dovoljuje podvojenih elementov. Za preverjanje dvojnikov uporablja metodo equals(), s čimer zagotovi, da je vsak element v nizu edinstven.
Brez naročila: Elementi v HashSet-u niso shranjeni v določenem vrstnem redu. Če morate ohraniti vrstni red elementov, lahko razmislite o uporabi LinkedHashSet, ki ohranja vrstni red vstavljanja.
Osnovna struktura podatkov: Interno HashSet uporablja zgoščeno tabelo za shranjevanje elementov. To omogoča stalno časovno povprečno kompleksnost za osnovne operacije, kot so dodajanje, odstranjevanje in vsebovanje.
Ničelni elementi: HashSet dovoljuje en ničelni element. Če poskusite dodati podvojeni ničelni element, bo zamenjal obstoječega.
Uvod
HashSet lahko oblikujemo brez uporabe knjižnic zgoščevalnih tabel. Spodaj je več različnih funkcij -
dodaj (x) - Metoda add(x) se uporablja predvsem za vstavljanje vrednosti x v HashSet.
vsebuje(x) - Metoda contains(x) se uporablja predvsem za preverjanje, ali je vrednost x prisotna v HashSet ali ne.
odstrani(x) - Metoda remove(x) se uporablja predvsem za brisanje x iz HashSet. Če HashSet nima nobene vrednosti, ne bo storil ničesar.
Razumejmo te metode s spodnjim primerom.
Najprej inicializirajte HashSet in pokličite funkcijo add(1). Dodal bo 1 v zgoščeni niz. Pokličite add(3), ki bo dodal 3, nato pokličite contains(1). Preveril bo, ali je 1 prisoten ali ne v zgoščenem nizu. Zdaj kličemo contains(2), add(2), contains(2), remove(2), contains(2).
Izhod bo vrnjen kot true za 1 je prisoten, false za 2 ni prisoten, true za 2 je prisoten, false za 2 ni prisoten.
Osnovne operacije HashSet v Pythonu
V HashSet-u lahko izvedemo nekaj osnovnih operacij z naslednjimi metodami. Razumejmo te metode.
Dodajanje novih vrednosti v HashSet
V spodnjem primeru bomo dodali vrednost v zgoščeni niz s funkcijo add(). Funkcija add() doda vrednost eno za drugo. Poglejmo naslednjo kodo.
Primer -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6)
Izhod:
Adding value: 2 Adding value: 7 Adding value: 6
Odstranjevanje vrednosti v HashSet
Obstoječo vrednost lahko odstranimo s funkcijo remove(). Razumejmo naslednjo kodo.
Primer -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.remove(7) obj.remove(6)
Izhod:
Adding value: 2 Adding value: 7 Adding value: 6 Removed value: 7 Removed value: 6
Preverjanje, ali obstajajo vrednosti v HashSet
V tem primeru bomo pokazali, kako lahko preverimo, ali določena vrednost obstaja ali ne uporablja vsebuje() funkcijo. Razumejmo naslednjo kodo.
Primer -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.contains(2)
Izhod:
kdaj je bil izumljen prvi računalnik
Adding value: 2 Adding value: 7 Adding value: 6 It contains: 2
Algoritem za HashSet v Pythonu
V prvem koraku definiramo eno podatkovno strukturo, imenovano HashList. Nato inicializiramo prazen seznam kot nov_seznam . Nato definiramo funkcijo update(), v kateri bo found shranil logično vrednost False. Zdaj uporabimo zanko for za vsak indeks I in K. če je ključ enak 'k', potem nov_seznam[i]=k in najdena vrednost je nastavljena na True. Če vrednost ni najdena, bo vrednost vstavljena na zadnjo stran seznama.
Naslednji korak je definiranje funkcije get(), ki jo bomo uporabili za zanko, in če je vrednost k enaka ključu, bo izhod True; drugače, False. Če je ključ enak 'k', izbrišite vrednost s seznama nov_seznam. Enak postopek bo uporabljen v funkciji remove().
Zdaj bomo ustvarili glavni razred HashSet. Ta razred bo deklariral inicializacijsko funkcijo, kjer je vrednost key_space = 2096. Zgoščevalna_tabela bo imela seznam objektov vrste new_list velikosti key_space . Nato bomo ustvarili funkcijo add(), v kateri hash_key = key%key_space in posodobite ključ hash_table[hash_key]. Po tem bomo poklicali odstranite funkcijo , v katerem hash_key = ključ % key_space, in izbrišite ključ hash_table[hash_key]. Po tem bomo poklicali vsebuje funkcijo , v katerem
hash_key = ključ % key_space in pridobite ključ hash_table[hash_key].
Oglejmo si algoritem izvajanja po korakih.
Algoritem -
- Ustvarite podatkovno strukturo, imenovano HashSet, jo inicializirajte kot spodaj
- nov_seznam = []
- Definirajte funkcijo update(). To bo vzelo ključ
- najdeno := False
- za vsak indeks i in ključ k na new_list naredite
- če je ključ enak k, potem
- new_list[i]:= ključ
- najdeno:= Res
- izstopite iz zanke
- če se ugotovi, da je lažna, potem
- vstavite ključ na konec new_list
- Definirajte funkcijo get(). To bo vzelo ključ
- za vsak k na novem_seznamu naredite
- če je k enak ključu, potem
- vrni True
- vrni False
- Definirajte funkcijo remove(). To bo vzelo ključ
- za vsak indeks i in ključ k na new_list naredite
- če je ključ enak k, potem
- izbriši nov_seznam[i]
- Zdaj ustvarite hashSet po meri. Naslednjih metod bo nekaj
- Inicializirajte to na naslednji način -
- presledek_ključa := 2096
- hash_table:= seznam predmetov vrste vedra velikosti key_space
- Definirajte funkcijo add(). To bo vzelo ključ
- hash_key:= key mod key_space
- pokliči posodobitev (ključ) razpršilne_tabele [razpršitveni ključ]
- Definirajte funkcijo remove(). To bo vzelo ključ
- hash_key:= keymodkey_space
- izbriši ključ iz razpršilne_tabele [hash_key]
- Definirajte funkcijo contains(). To bo vzelo ključ
- hash_key:= keymodkey_space
- vrni get(key) of hash_table[hash_key]
Implementacija HashSet v Pythonu
Tukaj bomo implementirali zgornji algoritem in ustvarili program Python. Določili bomo dva razreda: HashSet in CreateHashset. Poglejmo spodnjo kodo.
Koda -
# Here, we are Designing the HashSet in python # Here, we are checking the values and will return the output class class verifyvalues: # Here, we are initialization function which has list new_list def __init__(self): self.new_list=[] # Here, we have the function to update values def update(self, key): found=False for i,k in enumerate(self.new_list): if key==k: self.new_list[i]=key found=True break if not found: self.new_list.append(key) # Here, we have function to get values def get(self, key): for k in self.new_list: if k==key: return True return False # Here, we have function to remove values def remove(self, key): for i,k in enumerate(self.new_list): if key==k: del self.new_list[i] # Here, we have defined a class as HashSet class HashSet: # Here, we have defined an Initialization function def __init__(self): self.key_space = 2096 self.hash_table=[verifyvalues() for i in range(self.key_space)] def hash_values(self, key): hash_key=key%self.key_space return hash_key # Here, we have also defined an add function def add(self, key): self.hash_table[self.hash_values(key)].update(key) # Here, we have also defined a remove function def remove(self, key): self.hash_table[self.hash_values(key)].remove(key) # Here, we have defined the contains function def contains(self, key): return self.hash_table[self.hash_values(key)].get(key) def display(self): ls=[] for i in self.hash_table: if len(i.new_list)!=0:ls.append(i.new_list[0]) print(ls) ob = HashSet() print(ob.hash_values(10)) print('Add 10') ob.add(10) print(ob.hash_values(6)) print('Add 6 ') ob.add(6) print(ob.hash_values(5)) print('Add 5 ') ob.add(5) print('Contains 10 : ',ob.contains(10)) print('Contains 3: ',ob.contains(3)) print('Contains 8 : ',ob.contains(9))
Izhod:
10 Add 10 6 Add 6 5 Add 5 Contains 10 : True Contains 3: False Contains 8 : False 2 Add 2 3 Add 3 Contains 2 : True Remove 2 Contains 2 : False Contains 3 : True [3, 5, 6, 10]
Pojasnilo: