Jak wiemy, HashSet jest znaną klasą w Javie. HashSet służy do przechowywania wartości za pomocą tabeli mieszającej. W tym samouczku omówimy HashSet w Pythonie. Dowiemy się także jak zaprojektować HashSet w Pythonie.
HashSet to podstawowa struktura danych w programowaniu, powszechnie spotykana w językach takich jak Java. Należy do Java Collections Framework i służy jako implementacja ustawionego interfejsu. Cechą wyróżniającą HashSet jest możliwość przechowywania elementów w sposób ułatwiający sprawne sprawdzenie istnienia określonych elementów i zapewniający niepowtarzalność w obrębie zbioru. W przeciwieństwie do struktur takich jak listy, HashSet nie utrzymuje żadnej określonej kolejności między swoimi elementami.
Jedną z kluczowych cech HashSet jest gwarancja niepowtarzalności; nie pozwala na powielanie elementów. Operacje takie jak dodawanie, usuwanie i sprawdzanie obecności elementów zazwyczaj charakteryzują się średnią wydajnością w stałym czasie, co czyni je skutecznym wyborem w przypadku takich zadań. Należy jednak pamiętać, że kolejność elementów w zestawie HashSet nie jest gwarantowana.
Cechy charakterystyczne:
Wyjątkowość: HashSet nie pozwala na duplikaty elementów. Używa metody równości() do sprawdzania duplikatów, zapewniając, że każdy element w zestawie jest unikalny.
Brak zamówienia: Elementy w HashSet nie są przechowywane w żadnej określonej kolejności. Jeśli chcesz zachować kolejność elementów, możesz rozważyć użycie LinkedHashSet, który zachowuje kolejność wstawiania.
Podstawowa struktura danych: Wewnętrznie HashSet używa tablicy mieszającej do przechowywania elementów. Pozwala to na stałą średnią złożoność podstawowych operacji, takich jak dodawanie, usuwanie i zawiera.
Elementy zerowe: HashSet dopuszcza jeden element null. Jeśli spróbujesz dodać zduplikowany element null, zastąpi on istniejący.
Wstęp
Możemy zaprojektować HashSet bez korzystania z bibliotek tablic mieszających. Poniżej znajduje się wiele różnych funkcji -
dodaj(x) - Metoda add(x) jest używana głównie do wstawiania wartości x do HashSet.
lista tablic w sortowaniu w Javie
zawiera(x) - Metoda zawiera(x) służy głównie do sprawdzania, czy wartość x występuje w zestawie HashSet, czy nie.
usuń(x) - Metoda usuwania (x) jest używana głównie do usuwania x z HashSet. Jeśli HashSet nie ma żadnej wartości, nic nie zrobi.
Przyjrzyjmy się tym metodom na poniższym przykładzie.
Najpierw zainicjuj HashSet i wywołaj funkcję add(1). Dodaje 1 do zestawu skrótów. Wywołaj add(3), który doda 3, a następnie wywołaj zawiera(1). Sprawdzi, czy 1 jest obecny w zestawie skrótów. Teraz wywołujemy: zawiera(2), dodaje(2), zawiera(2), usuwa(2), zawiera(2).
Dane wyjściowe zostaną zwrócone, jeśli występuje odpowiednio prawda dla 1, fałsz dla 2 nie jest obecny, prawda dla 2 jest obecna, fałsz dla 2 nie jest obecny.
Podstawowe operacje HashSet w Pythonie
Podstawowe operacje w HashSet możemy wykonywać następującymi metodami. Rozumiemy te metody.
Dodawanie nowych wartości w HashSet
W poniższym przykładzie dodamy wartość do zestawu skrótów za pomocą funkcji add(). Funkcja add() dodaje wartość pojedynczo. Zobaczmy następujący kod.
Przykład -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6)
Wyjście:
Adding value: 2 Adding value: 7 Adding value: 6
Usuwanie wartości w HashSet
Istniejącą wartość możemy usunąć za pomocą funkcji usuwania(). Rozumiemy następujący kod.
Przykład -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.remove(7) obj.remove(6)
Wyjście:
Adding value: 2 Adding value: 7 Adding value: 6 Removed value: 7 Removed value: 6
Sprawdzanie, czy wartości istnieją w HashSet
W tym przykładzie pokażemy, jak możemy sprawdzić, czy dana wartość istnieje lub nie korzysta z zawiera() funkcjonować. Rozumiemy następujący kod.
Przykład -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.contains(2)
Wyjście:
mój flixer
Adding value: 2 Adding value: 7 Adding value: 6 It contains: 2
Algorytm dla HashSet w Pythonie
W pierwszym kroku definiujemy jedną strukturę danych o nazwie HashList. Następnie inicjujemy pustą listę jako nowa_lista . Następnie definiujemy funkcję update(), w której found będzie przechowywana wartość logiczna False. Teraz używamy pętli for dla każdego indeksu I i K. Jeśli klucz jest taki sam jak „k”, to nowa_lista[i]=k i znaleziono wartość ustawioną na True. Wartość zostanie wstawiona na końcu listy, jeśli nie zostanie znaleziona żadna wartość.
Następnym krokiem jest zdefiniowanie funkcji get(), której użyjemy dla pętli i jeśli wartość k będzie taka sama jak klucz, wynikiem będzie True; w przeciwnym razie fałsz. Jeśli klucz jest taki sam jak „k”, usuń wartość z listy Nowa lista. Ten sam proces zostanie zastosowany w funkcji usuwania().
Teraz utworzymy klasę główną HashSet. Ta klasa zadeklaruje funkcję inicjującą, gdzie wartość key_space = 2096. Hash_table będzie zawierała listę obiektów typu new_list o rozmiarze klucz_space . Następnie utworzymy funkcję add(), w której hash_key = klucz%klawisz_space i zaktualizuj klucz hash_table [hash_key]. Następnie zadzwonimy do usuń funkcję , w którym hash_key = klucz % key_space i usuń klucz hash_table[hash_key]. Następnie zadzwonimy do zawiera funkcję , w którym
hash_key = klucz % key_space i uzyskaj klucz hash_table [hash_key].
Zobaczmy krokowy algorytm implementacji.
Algorytm -
- Utwórz strukturę danych o nazwie HashSet, zainicjuj ją jak poniżej
- nowa_lista = []
- Zdefiniuj funkcję update(). To zajmie klucz
- znaleziono := Fałsz
- dla każdego indeksu i i klucza k w nowej_liście wykonaj
- jeśli klucz jest taki sam jak k, to
- nowa_lista[i]:= klucz
- znaleziono:= Prawda
- wyjść z pętli
- jeśli okaże się fałszywe, to
- wstaw klucz na końcu nowej_listy
- Zdefiniuj funkcję get() . To zajmie klucz
- dla każdego k w new_list wykonaj
- jeśli k jest tym samym co klucz, to
- zwróć Prawda
- zwróć Fałsz
- Zdefiniuj funkcję usuń(). To zajmie klucz
- dla każdego indeksu i i klucza k w nowej_liście wykonaj
- jeśli klucz jest taki sam jak k, to
- usuń nową_listę[i]
- Teraz utwórz niestandardowy zestaw hashSet. Będzie kilka następujących metod
- Zainicjuj to w następujący sposób -
- key_space := 2096
- hash_table:= lista obiektów typu wiadro o rozmiarze key_space
- Zdefiniuj funkcję add(). To zajmie klucz
- hash_key:= klucz mod key_space
- wywołaj aktualizację (klucz) hash_table [hash_key]
- Zdefiniuj funkcję usuń(). To zajmie klucz
- hash_key:= keymodkey_space
- usuń klucz z hash_table[hash_key]
- Zdefiniuj funkcję zawiera(). To zajmie klucz
- hash_key:= keymodkey_space
- zwróć get(key) z hash_table[hash_key]
Implementacja HashSet w Pythonie
Tutaj zaimplementujemy powyższy algorytm i utworzymy program w Pythonie. Zdefiniujemy dwie klasy: HashSet i CreateHashset. Zobaczmy poniższy kod.
Kod -
# 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))
Wyjście:
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]
Wyjaśnienie: