Mulțimea cu hash

  • 2 minute de citit
  • 9 exemple de cod în Go

Disponibil și în English

Pe această pagină

Introducere

Un hash set (mulțime cu hash) este o structură de date care permite stocarea elementelor într-o mulțime folosind o funcție de hash.

Mulțimea este o structură de date care oferă acces eficient la elementele sale și nu permite duplicate. Unicitatea unui element din hash set este determinată de funcția de hash; în această implementare, coliziunile de hash nu sunt tratate. Dacă hash-ul lui “a” este 123 și hash-ul lui “b” este tot 123, atunci considerăm că “a” și “b” au o coliziune de hash, iar dacă “a” este deja prezent în mulțime, adăugarea lui “b” nu are niciun efect.

Complexitatea spațiului și a timpului

Complexitatea spațiului și a timpului depinde de structura de date folosită pe dedesubt; în cazul de față, se folosește un map.

Complexitatea timpului pentru map-urile din Golang este în medie O(1) pentru toate operațiile, iar complexitatea spațiului este O(n).

Operații

Au fost implementate următoarele operații:

Add

Add adaugă un element în mulțime; nu tratează coliziunile.

func (s *MySet[T, H]) Add(element T) {	// Calculează hash-ul elementului	hash := element.Hash()	// Salvează	_, ok := s.storage[hash]	if !ok {		s.storage[hash] = element	}}

AddAll

AddAll adaugă toate elementele în mulțime. Este o metodă de comoditate, care permite apelarea o singură dată.

// AddAll adaugă toate elementele în mulțime.func (s *MyHashSet[T, H]) AddAll(elements ...T) {	for _, element := range elements {		s.Add(element)	}}

Contains

// Contains verifică dacă hash set-ul conține elementul T.// Returnează true dacă elementul face parte din mulțime, altfel false.func (s *MyHashSet[T, H]) Contains(element T) bool {	// Calculează hash-ul elementului	hash := element.Hash()	_, ok := s.storage[hash]	return ok}

Delete

// Delete șterge un element din mulțime.// Returnează true dacă elementul a fost șters, altfel false.func (s *MyHashSet[T, H]) Delete(element T) bool {	// Calculează hash-ul elementului	hash := element.Hash()	_, ok := s.storage[hash]	if ok {		delete(s.storage, hash)		return true	}	return false}

Union

// Union creează reuniunea a două mulțimifunc (s *MyHashSet[T, H]) Union(other *MyHashSet[T, H]) {	for _, v := range other.storage {		s.Add(v)	}}

Sub

// Sub creează diferența a două mulțimifunc (s *MyHashSet[T, H]) Sub(other *MyHashSet[T, H]) {	for _, v := range other.storage {		s.Delete(v)	}}

Note suplimentare

Pentru a implementa mulțimea într-un mod generic, a fost definită o interfață personalizată care reprezintă un hash:

type MyHash interface {	~string | ~int | ~uint | ~int64 | ~uint64 | ~int32 | ~uint32 | ~int16 | ~uint16 | ~int8 | ~uint8}

Simbolul ~ (tildă) definește o constrângere de tip, care se traduce prin ~string - toate subtipurile lui string, precum și string.

Permite scrierea unui cod de forma:

type String stringfunc (a String) Hash() string {	return string(a)}func TestMyHashSet_Constraint(t *testing.T) {	// Pregătire	newSet := NewSet[String, string]()	// Test	newSet.AddAll("type", "constraints", "rock")	// Atunci	assert.True(t, newSet.Contains("type"))	assert.True(t, newSet.Contains("constraints"))	assert.True(t, newSet.Contains("rock"))}

Structura hash set-ului este definită astfel:

// MyHashSet este o implementare de hash set.type MyHashSet[T Hasher[H], H MyHash] struct {	storage map[H]T}

Parametrii generici sunt specificați sub forma [T Hasher[H], H MyHash], unde T este Hasher[H], iar H este un tip concret de MyHash. Hasher nu poate fi inițializat fără un tip concret.

La inițializarea hash set-ului va trebui să specificați String

Puteți consulta implementarea completă pe GitHub-ul meu.