Ako vieme, HashSet je slávna trieda v Jave. HashSet sa používa na ukladanie hodnôt pomocou hašovacej tabuľky. V tomto návode sa budeme zaoberať HashSet v Pythone. Dozvieme sa tiež, ako môžeme navrhnúť HashSet v Pythone.
HashSet je základná dátová štruktúra v programovaní, ktorá sa bežne vyskytuje v jazykoch ako Java. Patrí do Java Collections Framework a slúži ako implementácia nastaveného rozhrania. Charakteristickým rysom HashSet je jeho schopnosť ukladať prvky spôsobom, ktorý uľahčuje efektívnu kontrolu existencie špecifických prvkov a zaisťuje jedinečnosť v rámci súboru. Na rozdiel od štruktúr, ako sú zoznamy, hashSet neudržiava žiadne špecifické poradie medzi svojimi prvkami.
Jednou z kľúčových vlastností HashSet je jeho záruka jedinečnosti; nepovoľuje duplicitné prvky. Operácie ako pridávanie, odstraňovanie a kontrola prítomnosti prvkov majú zvyčajne priemerný výkon v konštantnom čase, čo z nich robí efektívnu voľbu pre takéto úlohy. Je však dôležité poznamenať, že poradie prvkov v HashSet nie je zaručené.
k najbližšiemu susedovi
Kľúčové vlastnosti:
Jedinečnosť: HashSet neumožňuje duplicitné prvky. Používa metódu equals() na kontrolu duplikátov, čím zaisťuje, že každý prvok v sade je jedinečný.
Žiadna objednávka: Prvky v HashSet nie sú uložené v žiadnom konkrétnom poradí. Ak potrebujete zachovať poradie prvkov, môžete zvážiť použitie LinkedHashSet, ktorý zachováva poradie vkladania.
Základná dátová štruktúra: HashSet interne používa na ukladanie prvkov hašovaciu tabuľku. To umožňuje priemernú zložitosť v konštantnom čase pre základné operácie, ako je pridanie, odstránenie a začlenenie.
Nulové prvky: HashSet umožňuje jeden nulový prvok. Ak sa pokúsite pridať duplicitný nulový prvok, nahradí existujúci prvok.
Úvod
Môžeme navrhnúť HashSet bez použitia knižníc hašovacích tabuliek. Nižšie sú uvedené rôzne funkcie -
pridať (x) - Metóda add(x) sa používa hlavne na vloženie hodnoty x do HashSet.
obsahuje(x) - Metóda obsahuje(x) sa používa hlavne na kontrolu, či je hodnota x prítomná v HashSet alebo nie.
odstrániť (x) - Metóda remove(x) sa používa hlavne na odstránenie x z HashSet. Ak HashSet nemá žiadnu hodnotu, neurobí nič.
Poďme pochopiť tieto metódy na nižšie uvedenom príklade.
Najprv inicializujte HashSet a zavolajte funkciu add(1). Pridá 1 do množiny hash. Zavolajte add(3), čím sa pridá 3, potom call obsahuje(1). Skontroluje, či je 1 v množine hash prítomný alebo nie. Teraz voláme obsahuje(2), pridať(2), obsahuje(2), odobrať(2), obsahuje(2).
Výstup sa vráti ako true pre 1 je prítomný, false pre 2 nie je prítomný, true pre 2 je prítomný, false pre 2 nie je prítomný, resp.
Základné operácie HashSet v Pythone
Niektoré základné operácie v HashSet môžeme vykonávať pomocou nasledujúcich metód. Poďme pochopiť tieto metódy.
Pridanie nových hodnôt do HashSet
V nižšie uvedenom príklade pridáme hodnotu do množiny hash pomocou funkcie add(). Funkcia add() pridáva hodnotu po jednej. Pozrime sa na nasledujúci kód.
Príklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6)
Výkon:
Adding value: 2 Adding value: 7 Adding value: 6
Odstránenie hodnôt v HashSet
Existujúcu hodnotu môžeme odstrániť pomocou funkcie remove(). Poďme pochopiť nasledujúci kód.
Príklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.remove(7) obj.remove(6)
Výkon:
Adding value: 2 Adding value: 7 Adding value: 6 Removed value: 7 Removed value: 6
Kontrola, či hodnoty existujú v HashSet
V tomto príklade ukážeme, ako môžeme skontrolovať, či konkrétna hodnota existuje alebo nepoužíva obsahuje() funkciu. Poďme pochopiť nasledujúci kód.
Príklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.contains(2)
Výkon:
Adding value: 2 Adding value: 7 Adding value: 6 It contains: 2
Algoritmus pre HashSet v Pythone
V prvom kroku definujeme jednu dátovú štruktúru s názvom HashList. Potom inicializujeme prázdny zoznam ako nový_zoznam . Potom definujeme funkciu update(), v ktorej nájdená bude ukladať booleovskú hodnotu False. Teraz použijeme cyklus for pre každý index I a K. ak je kľúč rovnaký ako 'k' new_list[i]=k a nájdená hodnota nastavená na True. Ak sa nenájde žiadna hodnota, hodnota sa vloží na koniec zoznamu.
Ďalším krokom je definovanie funkcie get(), ktorú použijeme pre cyklus a ak je hodnota k rovnaká ako kľúč, výstup bude True; inak False. Ak je kľúč rovnaký ako „k“, odstráňte hodnotu zo zoznamu nový_zoznam. Rovnaký proces sa použije vo funkcii remove().
Teraz vytvoríme hlavnú triedu HashSet. Táto trieda deklaruje inicializačnú funkciu, kde hodnota key_space = 2096. Hash_table bude mať zoznam objektov typu new_list veľkosti key_space . Potom vytvoríme funkciu add(), v ktorej hash_key = key%key_space a aktualizujte kľúč hash_table[hash_key]. Potom zavoláme na odstrániť funkciu , v ktorom hash_key = kľúč % key_space, a vymažte kľúč hash_table[hash_key]. Potom zavoláme na obsahuje funkciu , v ktorom
hash_key = kľúč % key_space a získajte kľúč hash_table[hash_key].
obojsmerné plánovanie
Pozrime sa na postupný implementačný algoritmus.
Algoritmus -
- Vytvorte dátovú štruktúru s názvom HashSet, inicializujte ju ako nižšie
- new_list = []
- Definujte funkciu update(). Toto bude vyžadovať kľúč
- nájdené := Nepravda
- pre každý index i a kľúč k v novom_zozname urobte
- ak je kľúč rovnaký ako k, potom
- new_list[i]:= kľúč
- nájdené:= Pravda
- vyjsť zo slučky
- ak sa zistí nepravda, potom
- vložte kľúč na koniec nového_zoznamu
- Definujte funkciu get() . Toto bude vyžadovať kľúč
- pre každé k v novom_zozname urobte
- ak je k rovnaké ako kľúč, potom
- vrátiť Pravda
- návrat False
- Definujte funkciu remove(). Toto bude vyžadovať kľúč
- pre každý index i a kľúč k v novom_zozname urobte
- ak je kľúč rovnaký ako k, potom
- vymazať nový_zoznam[i]
- Teraz vytvorte vlastný hashSet. Nižšie uvedených metód bude niekoľko
- Inicializujte to takto -
- key_space := 2096
- hash_table:= zoznam objektov typu bucket s veľkosťou key_space
- Definujte funkciu add(). Toto bude vyžadovať kľúč
- hash_key:= kľúč mod key_space
- call update(key) of hash_table[hash_key]
- Definujte funkciu remove(). Toto bude vyžadovať kľúč
- hash_key:= keymodkey_space
- odstrániť kľúč z tabuľky hash[hash_key]
- Definujte funkciu obsahuje(). Toto bude vyžadovať kľúč
- hash_key:= keymodkey_space
- return get(key) of hash_table[hash_key]
Implementácia HashSet v Pythone
Tu implementujeme vyššie uvedený algoritmus a vytvoríme program Python. Definujeme dve triedy: HashSet a CreateHashset. Pozrime sa na nižšie uvedený kód.
kód -
# 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))
Výkon:
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]
Vysvetlenie: