structuri de date în java (v)vega.unitbv.ro/~galmeanu/java/suport/curs-5/doc/java... ·...
Post on 30-Dec-2019
12 Views
Preview:
TRANSCRIPT
1
Structuri de Date în Java (V)
● Hash codes● Metoda hashCode ()● Cerinţele suprascrierii hashCode ()● Tipuri utilizator cu şi fără hashCode● Folosirea colecţiilor Java● Colecţii generice● Iteratori● Ştergerea obiectelor din colecţie● Colecţiile List● Colecţiile Set
2
Hash code
“O funcţie hash este orice procedură sau funcţie matematică riguros definită care converteşte un volum de date apreciabil, posibil de dimensiune variabilă, într-o dată de lungime mică, de obicei un simplu întreg. Valorile returnate de o funcţie hash sunt denumite hash codes.”
(Wikipedia)
4
Ce este o valoare hash?
● O valoare întreagă care “se substituie” unui obiect
● Un mod rapid pentru a verifica inegalitatea a două obiecte
● Obiectele egale (ar trebui) să aibă valori hash egale
Q: De ce avem nevoie de ea?A: Pentru a distinge rapid între obiecte diferite
5
Metoda .hashCode()
public int hashCode ()
● Metodă a clasei Object, disponibilă a fi suprascrisă
● Definită în java.lang.Object să întoarcă o valoare aproape unică acelei instanţe
● Toate clasele o moştenesc iar unele o suprascriu
6
Cerinţele hashCode
● Valoarea hashCode a unui obiect nu se poate schimba dacă obiectul nu se modifică
● Două obiecte egale trebuie să aibă valori hashCode egale
● Este recomandabil ca două obiecte diferite să aibă valori hashCode distincte
7
Exemple hashCodeString radu = “Radu”;String radu2 = “Radu”;String diana = “Diana”;System.out.println (radu.hashCode());System.out.println (radu2.hashCode());System.out.println (diana.hashCode());// 1893428309, 1893428309, 7528268361
Integer int1 = 123456789;Integer int2 = 123456789;System.out.println (int1.hashCode());System.out.println (int2.hashCode());// 123456789, 123456789
8
Clasa Namepublic class Name {
public String first;public String last;
public Name (String first, String last) {this.first = first;this.last = last;
}public String toString () {
return first + " " + last;}public boolean equals (Object o) {
return (o instanceof Name && ((Name) o).first.equals (this.first) &&((Name) o).last.equals (this.last));
}}
9
Testarea funcţionării
Name radu = new Name ("Radu", "Ostrezu");Name dan = new Name ("Dan", "Apolosanu");Name dan2 = new Name ("Dan", "Apolosanu");
System.out.println (radu.equals (dan));System.out.println (dan.equals (dan2));System.out.println (radu.hashCode ());System.out.println (dan.hashCode ());System.out.println (dan2.hashCode ());// false, true, 17523401, 8567361, 9584176
● Obiectele sunt egale, hashCode-urile nu
10
Ce nevoie avem de hashCode?
● Clasa Name pare să funcţioneze
● Chiar e o problemă că n-am suprascris hashCode?
● Dacă nu folosim explicit hashCode, de ce ne-am obosi să o suprascriem?
11
JAVA foloseşte hashCode !
● Nu am respectat cerinţele hashCode!
● Avem două obiecte egale dar cu hashCode-uri diferite!
● Poate da naştere la comportamente ciudate şi imprevizibile
12
Comportament incorect
Set<String> strings = new HashSet<String> ();Set<Name> names = new HashSet<Name> (); strings.add ("Radu");names.add (new Name ("Dan", "Ostroveanu")); System.out.println (strings.contains ("Radu"));System.out.println (names.contains (
new Name ("Dan", "Ostroveanu")));
// true, false
13
Soluţia? Suprascrierea hashCode
Constrângeri:
● hashCode () trebuie să respecte egalitatea
● hashCode () trebuie să fie consistentă
● hashCode () trebuie să genereze int
● hashCode () ar fi bine să recunoască inegalitatea
14
O implementare posibilă
public class Name {// ...public int hashCode () {
return first.hashCode () + last.hashCode ();}
}
● Oare şi funcţionează?
15
Comportament corect, aşteptat
Set<Name> names = new HashSet<Name> (); names.add (new Name ("Dan", "Ostroveanu")); System.out.println (names.contains (
new Name ("Dan", "Ostroveanu")));
// true
● Se poate şi mai bine?
16
O implementare mai bună
public class Name {// ...public int hashCode () {
return first.hashCode () * 37 + last.hashCode ();
}}
● De ce este mai bună? (revedeţi cerinţele)
17
Cerinţele hashCode “reloaded”
● Valoarea hashCode a unui obiect nu se poate schimba dacă obiectul nu se modifică
● Două obiecte egale trebuie să aibă valori hashCode egale
● Este recomandabil ca două obiecte diferite să aibă valori hashCode distincte
● Exemplu: Dan Ostroveanu va fi diferit de Ostroveanu Dan
18
Înainte de a merge mai departe
● Aveţi nelămuriri în legătură cu hashCode? Întrebaţi acum!
● Vom folosi metoda ulterior în lucrul cu colecţii
● Vă poate cauza comportamente ciudate dacă nu-i înţelegeţi scopul
19
Colecţiile Java
● Sunt un ansambul de interfeţe şi clase ce realizează:
● Colectarea obiectelor laolaltă● Stocarea obiectelor● Sortarea obiectelor● Accesarea obiectelor
● Furnizează o sintaxă comună pentru toate variantele de implementare a colecţiilor
20
Cum folosim colecţiile
● Adăugăm import java.util.*; la începutul fişierului java unde folosim colecţia
package lab2;import java.util.*;public class CollectionUser {
List<String> list = new ArrayList<String> ();// ...
}
21
Sintaxa generală Collection<Ceva>
● boolean add (Ceva c);
● boolean contains (Object o);
● boolean remove (Ceva c);
● int size ();
Fiecare colecţie se particularizează pentru un tip de dată anume folosind '<' şi >' Spunem că folosim “şabloane”.
ex. Collection este o interfaţă şablon
22
Un exemplu de folosire
List<Name> unu = new ArrayList<Name> (); unu.add (new Name ("Dan", "Ostroveanu")); unu.add (new Name ("Radu", "Cuprescu")); System.out.println (unu.size()); unu.remove (new Name ("Dan", "Ostroveanu")); System.out.println (unu.size()); List<Name> doi = new ArrayList<Name> (); doi.add (new Name ("Mircea", "Kirakainen")); unu.addAll (doi); System.out.println (unu.size());
23
Colecţii generice
● Putem specifica tipul de dată pe care îl va folosi colecţia
● Ex: List<String> strings
● Suntem siguri că strings va conţine numai obiecte de tip String
● E opţional, însă foarte folositor
24
De ce folosim tipuri generice?
List untyped = new ArrayList ();List<String> typed = new ArrayList<String> ();
Object obj = untyped.get (0);String sillyString = (String) obj;String smartString = typed.get (0);
25
Accesarea obiectelor: iterator● Avem colecţia:
Collection<Ceva> col;● Iterator:
Iterator<Ceva> it = col.iterator ();while (it.hasNext ()) {
Ceva obj = it.next ();// procesăm obj
}● For each: // formă sinonimă, dar mai compactă
for (Ceva obj : col) {// procesăm obj
}
26
Ştergerea din colecţie a obiectelor
● Nu se pot scoate din colecţie obiectele în timp ce se iterează!for (Ceva obj : col) {
col.remove (obj); // ConcurrentModificatonException}
● Numai iteratorul poate şterge obiectul pe care iterează la acel moment
Iterator<Ceva> it = col.iterator ();while (it.hasNext ()) {
Ceva obj = it.next ();it.remove (obj); // şi nu col.remove (obj);
}● De remarcat că iter.remove este opţională şi nu toate obiectele ce implementează Iterator vor suporta metoda
27
Tipurile de colecţii generice
● List● ArrayList● LinkedList
● Set● HashSet● TreeSet
● Map● HashMap● TreeMap
28
Interfaţa List● Listă de obiecte accesabile într-o ordine, similară cu un
vector● Spre deosebire de vector, nu avem o mărime în care
trebuie să ne încadrăm● Ordinea elementelor din listă este dată de ordinea
introducerii lor
List<String> strings = new ArrayList<String> ();strings.add (“unu”); strings.add (“doi”);strings.add (“trei”);// strings = [ “unu”, “doi”, “trei” ]
29
Alte feluri de acces
● Introducerea cu un index:List<String> strings = new ArrayList<String> ();strings.add (“unu”);strings.add (“trei”);strings.add (1, “doi”);// strings = [ “unu”, “doi”, “trei” ]
● Accesarea obiectelor folosind un index:s.o.print (strings.get (0)); // “unu”s.o.print (strings.indexOf (“unu”)); // 0
30
Interfaţa Set
● Set-ul nu are nici size şi nici vreo ordine● Nu sunt permise obiecte duplicat!
Set<Name> names = new HashSet<Name> ();names.add (new Name (“Jack”, “Daniels”));names.add (new Name (“Jack”, “Daniels”));
System.out.println (names.size ()); // 1
31
Constrângerile folosirii Set-urilor
● Un obiect de tip Set nu poate fi modificat într-un fel care să-i afecteze testul de egalitate
● Toate metodele de modificare pot altera conţinutul, apelarea lor trebuie făcută selectiv
● Dacă nu respectaţi această constrângere, aşteptaţi-vă la comportamente bizare
32
Folosire incorectă
Set<Name> names = new HashSet<Name> ();Name jack = new Name (“Jack”, “Daniels”);names.add (jack);System.out.println (names.size ());
System.out.println (names.contains (jack)); // true
jack.last = "Rangers";
System.out.println (names.contains (jack)); // false System.out.println (names.size ()); // 1
top related