Come sappiamo, HashSet è una classe famosa in Java. HashSet viene utilizzato per memorizzare i valori utilizzando una tabella hash. In questo tutorial tratteremo HashSet in Python. Impareremo anche come progettare HashSet in Python.
Un HashSet è una struttura dati fondamentale nella programmazione, comunemente presente in linguaggi come Java. Appartiene al Java Collections Framework e funge da implementazione dell'interfaccia impostata. La caratteristica distintiva di un HashSet è la sua capacità di memorizzare elementi in modo da facilitare il controllo efficiente dell'esistenza di elementi specifici e garantire l'unicità all'interno del set. A differenza delle strutture come le liste, un HashSet non mantiene alcun ordine specifico tra i suoi elementi.
Una caratteristica fondamentale di un HashSet è la sua garanzia di unicità; non consente elementi duplicati. Operazioni come l'aggiunta, la rimozione e il controllo della presenza di elementi in genere hanno prestazioni medie a tempo costante, rendendole una scelta efficiente per tali attività. Tuttavia, è essenziale notare che l'ordine degli elementi in un HashSet non è garantito.
casuale non in Java
Caratteristiche principali:
Unicità: Un HashSet non consente elementi duplicati. Utilizza il metodo equals() per verificare la presenza di duplicati, assicurando che ogni elemento nel set sia unico.
Nessun ordine: Gli elementi in un HashSet non vengono archiviati in un ordine particolare. Se è necessario mantenere l'ordine degli elementi, potresti prendere in considerazione l'utilizzo di un LinkedHashSet, che mantiene l'ordine di inserimento.
Struttura dei dati sottostante: Internamente, un HashSet utilizza una tabella hash per memorizzare gli elementi. Ciò consente una complessità media costante nel tempo per operazioni di base come aggiunta, rimozione e contenimento.
Elementi nulli: Un HashSet consente un elemento null. Se tenti di aggiungere un elemento null duplicato, sostituirà quello esistente.
introduzione
Possiamo progettare HashSet senza utilizzare librerie di tabelle hash. Di seguito sono riportate le molteplici funzioni diverse:
aggiungi(x) - Il metodo add(x) viene utilizzato principalmente per inserire un valore x nell'HashSet.
contiene(x) - Il metodo contiene(x) viene utilizzato principalmente per verificare se un valore x è presente o meno nell'HashSet.
rimuovi(x) - Il metodo rimuovi(x) viene utilizzato principalmente per eliminare x dall'HashSet. Se HashSet non ha alcun valore, non farà nulla.
Comprendiamo questi metodi con l'esempio seguente.
Innanzitutto, inizializza HashSet e chiama la funzione add(1). Aggiungerà 1 al set di hash. Chiama add(3), che aggiungerà 3, quindi chiama contiene(1). Verificherà se 1 è presente o meno nel set di hash. Ora chiamiamo contiene(2), aggiungi(2), contiene(2), rimuove(2), contiene(2).
L'output verrà restituito rispettivamente come vero per 1 è presente, falso per 2 non presente, vero per 2 presente, falso per 2 non presente.
Operazioni di base di HashSet in Python
Possiamo eseguire alcune operazioni di base in HashSet utilizzando i seguenti metodi. Comprendiamo questi metodi.
Aggiunta di nuovi valori in HashSet
Nell'esempio seguente, aggiungeremo il valore nel set di hash utilizzando la funzione add(). La funzione add() aggiunge il valore uno alla volta. Vediamo il codice seguente.
Esempio -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6)
Produzione:
Adding value: 2 Adding value: 7 Adding value: 6
Rimozione di valori in HashSet
Possiamo rimuovere il valore esistente usando la funzione rimuovi(). Comprendiamo il seguente codice.
Esempio -
jtextfield
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.remove(7) obj.remove(6)
Produzione:
Adding value: 2 Adding value: 7 Adding value: 6 Removed value: 7 Removed value: 6
Verifica se esistono valori in HashSet
In questo esempio, dimostreremo come possiamo verificare se un particolare valore esiste o non utilizza il file contiene() funzione. Comprendiamo il seguente codice.
Esempio -
from hs import HashSet obj = HashSet() obj.add(2) obj.add(7) obj.add(6) obj.contains(2)
Produzione:
Adding value: 2 Adding value: 7 Adding value: 6 It contains: 2
Algoritmo per HashSet in Python
Nel primo passaggio, definiamo una struttura dati chiamata HashList. Quindi, inizializziamo un elenco vuoto come una nuova_lista . Quindi, definiamo una funzione update() in cui find memorizzerà un valore booleano False. Ora usiamo il ciclo for per ogni indice I e K. Se la chiave è la stessa di 'k', allora nuova_lista[i]=k e ho trovato un valore impostato su True. Il valore verrà inserito all'ultimo dell'elenco se non viene trovato alcun valore.
Il passo successivo è definire la funzione get(), che utilizzeremo per il ciclo, e se il valore di k è uguale alla chiave, l'output sarà True; altrimenti Falso. Se la chiave è uguale a 'k', elimina il valore dall'elenco nuova_lista. Lo stesso processo verrà applicato nella funzione rimuovi().
Ora creeremo la classe Main HashSet. Questa classe dichiarerà la funzione di inizializzazione in cui il valore key_space = 2096. La hash_table avrà un elenco di oggetti di tipo new_list di dimensione key_space . Quindi, creeremo la funzione add(), in cui chiave_hash = chiave%spazio_chiave e aggiorna la chiave di hash_table[hash_key]. Successivamente chiameremo il rimuovere la funzione , in cui hash_key = key % key_space ed elimina la chiave di hash_table[hash_key]. Successivamente chiameremo il contiene la funzione , in quale
hash_key = key % key_space e ottieni la chiave di hash_table[hash_key].
albero binario trasversale per corrispondenza
Vediamo l'algoritmo di implementazione passo-passo.
Algoritmo -
- Crea una struttura dati chiamata HashSet, inizializzala come di seguito
- nuova_lista = []
- Definire una funzione update(). Questo sarà fondamentale
- trovato := Falso
- per ogni indice i e chiave k in new_list, esegui
- se la chiave è uguale a k, allora
- nuova_lista[i]:= chiave
- trovato:= Vero
- uscire dal giro
- se trovato falso, allora
- inserire la chiave alla fine di new_list
- Definire una funzione get() . Questo sarà fondamentale
- per ogni k in new_list, fai
- se k è uguale alla chiave, allora
- restituisce Vero
- restituire Falso
- Definire una funzione rimuovi(). Questo sarà fondamentale
- per ogni indice i e chiave k in new_list, esegui
- se la chiave è uguale a k, allora
- elimina nuova_lista[i]
- Ora crea un hashSet personalizzato. Ci saranno alcuni metodi come segue
- Inizializzalo come segue:
- spazio_chiave := 2096
- hash_table:= un elenco di oggetti di tipo bucket di dimensione key_space
- Definire una funzione add(). Questo sarà fondamentale
- hash_key:= chiave mod key_space
- chiama update(key) di hash_table[hash_key]
- Definire una funzione rimuovi(). Questo sarà fondamentale
- hash_key:= keymodkey_space
- elimina la chiave da hash_table[hash_key]
- Definire una funzione contiene(). Questo sarà fondamentale
- hash_key:= keymodkey_space
- restituisce get(chiave) di hash_table[hash_key]
Implementazione di HashSet in Python
Qui implementeremo l'algoritmo di cui sopra e creeremo il programma Python. Definiremo le due classi: HashSet e CreateHashset. Vediamo il codice seguente.
Codice -
# 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))
Produzione:
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]
Spiegazione: