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)

3

Funcţiile hash “la lucru”

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

33

Soluţii pentru rezolvare?

● Nu avem

● Aşa că nu se recomandă o astfel de abordare

● Dacă e posibil, folosiţi seturi de date ce nu se modifică

● Altfel, procedaţi cu atenţie