Jak víme, HashSet je slavná třída v Javě. HashSet se používá k ukládání hodnot pomocí hash tabulky. V tomto tutoriálu se budeme zabývat HashSet v Pythonu. Dozvíme se také, jak můžeme navrhnout HashSet v Pythonu.
HashSet je základní datová struktura v programování, běžně se vyskytující v jazycích, jako je Java. Patří do Java Collections Framework a slouží jako implementace nastaveného rozhraní. Charakteristickým rysem HashSet je jeho schopnost ukládat prvky způsobem, který usnadňuje efektivní kontrolu existence konkrétních prvků a zajišťuje jedinečnost v sadě. Na rozdíl od struktur, jako jsou seznamy, hashSet neudržuje žádné konkrétní pořadí mezi svými prvky.
Jednou z klíčových vlastností HashSet je jeho záruka jedinečnosti; neumožňuje duplicitní prvky. Operace jako přidávání, odebírání a kontrola přítomnosti prvků mají obvykle průměrný výkon v konstantním čase, což z nich činí efektivní volbu pro takové úkoly. Je však nezbytné poznamenat, že pořadí prvků v HashSet není zaručeno.
příkaz java if
Klíčové vlastnosti:
Jedinečnost: HashSet neumožňuje duplicitní prvky. Ke kontrole duplikátů používá metodu equals() a zajišťuje, že každý prvek v sadě je jedinečný.
Žádná objednávka: Prvky v HashSet nejsou uloženy v žádném konkrétním pořadí. Pokud potřebujete zachovat pořadí prvků, můžete zvážit použití LinkedHashSet, který zachovává pořadí vkládání.
Základní datová struktura: Interně HashSet používá k ukládání prvků hashovací tabulku. To umožňuje průměrnou složitost v konstantním čase pro základní operace, jako je přidávání, odebírání a obsahuje.
Nulové prvky: HashSet umožňuje jeden nulový prvek. Pokud se pokusíte přidat duplicitní prvek null, nahradí stávající prvek.
Úvod
Můžeme navrhnout HashSet bez použití knihoven hash tabulek. Níže je několik různých funkcí -
přidat (x) - Metoda add(x) se používá hlavně pro vložení hodnoty x do HashSet.
spát v js
obsahuje(x) - Metoda obsahuje(x) se používá hlavně ke kontrole, zda je hodnota x přítomna v HashSet nebo ne.
odstranit (x) - Metoda remove(x) se používá hlavně k odstranění x ze sady HashSet. Pokud HashSet nemá žádnou hodnotu, neudělá nic.
Pojďme pochopit tyto metody na níže uvedeném příkladu.
Nejprve inicializujte HashSet a zavolejte funkci add(1). Přidá 1 do sady hash. Volání add(3), které přidá 3, pak call obsahuje(1). Zkontroluje, zda je 1 v sadě hash přítomna nebo ne. Nyní zavoláme obsahuje(2), přidat(2), obsahuje(2), odebrat(2), obsahuje(2).
Výstup bude vrácen jako true pro 1 je přítomen, false pro 2 není přítomen, true pro 2 je přítomen, false pro 2 není přítomen.
Základní operace HashSet v Pythonu
Některé základní operace v HashSet můžeme provádět pomocí následujících metod. Pojďme pochopit tyto metody.
c# obsahuje řetězec
Přidání nových hodnot do HashSet
V níže uvedeném příkladu přidáme hodnotu v sadě hash pomocí funkce add(). Funkce add() přidává hodnotu jednu po druhé. Podívejme se na následující kód.
Příklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6)
Výstup:
Adding value: 2 Adding value: 7 Adding value: 6
Odebrání hodnot v HashSet
Stávající hodnotu můžeme odstranit pomocí funkce remove(). Pojďme pochopit následující kód.
Příklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.remove(7) obj.remove(6)
Výstup:
tučné písmo v css
Adding value: 2 Adding value: 7 Adding value: 6 Removed value: 7 Removed value: 6
Kontrola, zda v HashSet existují hodnoty
V tomto příkladu si ukážeme, jak můžeme zkontrolovat, zda určitá hodnota existuje nebo nepoužívá obsahuje() funkce. Pojďme pochopit následující kód.
Příklad -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.contains(2)
Výstup:
Adding value: 2 Adding value: 7 Adding value: 6 It contains: 2
Algoritmus pro HashSet v Pythonu
V prvním kroku definujeme jednu datovou strukturu nazvanou HashList. Poté inicializujeme prázdný seznam jako nový_seznam . Poté definujeme funkci update(), ve které bude found ukládat booleovskou hodnotu False. Nyní použijeme cyklus for pro každý index I a K. pokud je klíč stejný jako 'k' nový_seznam[i]=k a nalezená hodnota nastavena na True. Pokud nebude nalezena žádná hodnota, bude hodnota vložena na konec seznamu.
Dalším krokem je definování funkce get(), kterou použijeme pro cyklus, a pokud je hodnota k stejná jako klíč, výstup bude True; jinak False. Pokud je klíč stejný jako 'k', odstraňte hodnotu ze seznamu nový_seznam. Stejný proces bude použit ve funkci remove().
Nyní vytvoříme hlavní třídu HashSet. Tato třída deklaruje inicializační funkci, kde hodnota key_space = 2096. Hash_table bude mít seznam objektů typu new_list o velikosti key_space . Poté vytvoříme funkci add(), ve které hash_key = key%key_space a aktualizujte klíč hash_table[hash_key]. Poté zavoláme odstranit funkci , ve kterém hash_key = klíč % key_space, a odstraňte klíč hash_table[hash_key]. Poté zavoláme obsahuje funkci , ve kterém
hash_key = klíč % key_space a získejte klíč hash_table[hash_key].
rolovací kolečko nefunguje
Podívejme se na postupný implementační algoritmus.
Algoritmus -
- Vytvořte datovou strukturu s názvem HashSet, inicializujte ji jako níže
- new_list = []
- Definujte funkci update(). To bude vyžadovat klíč
- nalezeno := Falešné
- pro každý index i a klíč k v novém_seznamu proveďte
- pokud je klíč stejný jako k, pak
- new_list[i]:= klíč
- nalezeno:= Pravda
- vyjít ze smyčky
- pokud bude shledán nepravdivým, pak
- vložte klíč na konec nového_seznamu
- Definujte funkci get() . To bude vyžadovat klíč
- pro každé k v novém_seznamu udělejte
- pokud je k stejné jako klíč, pak
- vrátit True
- návrat False
- Definujte funkci remove(). To bude vyžadovat klíč
- pro každý index i a klíč k v novém_seznamu proveďte
- pokud je klíč stejný jako k, pak
- smazat nový_seznam[i]
- Nyní vytvořte vlastní hashSet. Následujících metod bude několik
- Inicializujte to následovně -
- key_space := 2096
- hash_table:= seznam objektů typu bucket o velikosti key_space
- Definujte funkci add(). To bude vyžadovat klíč
- hash_key:= klíč mod key_space
- volání aktualizace(klíč) hash_table[hash_key]
- Definujte funkci remove(). To bude vyžadovat klíč
- hash_key:= keymodkey_space
- odstranit klíč z hash_table[hash_key]
- Definujte funkci obsahuje(). To bude vyžadovat klíč
- hash_key:= keymodkey_space
- return get(key) of hash_table[hash_key]
Implementace HashSet v Pythonu
Zde implementujeme výše uvedený algoritmus a vytvoříme program Python. Definujeme dvě třídy: HashSet a CreateHashset. Podívejme se na níže 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ýstup:
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]
Vysvětlení: