Structuri de Date n Java (V)

Hash codes
Metoda hashCode ()
Cerinele suprascrierii hashCode ()
Tipuri utilizator cu i fr hashCode
Folosirea coleciilor Java
Colecii generice
Iteratori
tergerea obiectelor din colecie
Coleciile List
Coleciile Set

Hash code
O funcie hash este orice procedur sau funcie
matematic riguros definit care convertete un
volum de date apreciabil, posibil de dimensiune
variabil, ntr-o dat de lungime mic, de obicei un
simplu ntreg. Valorile returnate de o funcie hash
sunt denumite hash codes.
(Wikipedia)
2

Funciile hash la lucru

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
4

Metoda .hashCode()
public int hashCode ()

Metod a clasei Object, disponibil a fi suprascris

Definit n [Link] s ntoarc o valoare

aproape unic acelei instane

Toate clasele o motenesc iar unele o suprascriu

5

Cerinele 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

Exemple hashCode
String radu = Radu;
String radu2 = Radu;
String diana = Diana;
[Link] ([Link]());
[Link] ([Link]());
[Link] ([Link]());
// 1893428309, 1893428309, 7528268361
Integer int1 = 123456789;
Integer int2 = 123456789;
[Link] ([Link]());
[Link] ([Link]());
// 123456789, 123456789
7

Clasa Name
public class Name {
public String first;
public String last;
public Name (String first, String last) {
[Link] = first;
[Link] = last;
}
public String toString () {
return first + " " + last;
}
public boolean equals (Object o) {
return (o instanceof Name &&
((Name) o).[Link] ([Link]) &&
((Name) o).[Link] ([Link]));
}
}

Testarea funcionrii
Name radu = new Name ("Radu", "Ostrezu");
Name dan = new Name ("Dan", "Apolosanu");
Name dan2 = new Name ("Dan", "Apolosanu");
[Link] ([Link] (dan));
[Link] ([Link] (dan2));
[Link] ([Link] ());
[Link] ([Link] ());
[Link] ([Link] ());
// false, true, 17523401, 8567361, 9584176

Obiectele sunt egale, hashCode-urile nu

Ce nevoie avem de hashCode?

Clasa Name pare s funcioneze

Chiar e o problem c n-am suprascris hashCode?

Dac nu folosim explicit hashCode, de ce ne-am

obosi s o suprascriem?

10

JAVA folosete hashCode !

Nu am respectat cerinele hashCode!

Avem dou obiecte egale dar cu hashCode-uri

diferite!

Poate da natere la comportamente ciudate i

imprevizibile

11

Comportament incorect
Set<String> strings = new HashSet<String> ();
Set<Name> names = new HashSet<Name> ();
[Link] ("Radu");
[Link] (new Name ("Dan", "Ostroveanu"));
[Link] ([Link] ("Radu"));
[Link] ([Link] (
new Name ("Dan", "Ostroveanu")));
// true, false
12

Soluia? Suprascrierea hashCode

Constrngeri:

hashCode () trebuie s respecte egalitatea

hashCode () trebuie s fie consistent

hashCode () trebuie s genereze int

hashCode () ar fi bine s recunoasc inegalitatea

13

O implementare posibil
public class Name {
// ...
public int hashCode () {
return [Link] () + [Link] ();
}
}

Oare i funcioneaz?
14

Comportament corect, ateptat

Set<Name> names = new HashSet<Name> ();
[Link] (new Name ("Dan", "Ostroveanu"));
[Link] ([Link] (
new Name ("Dan", "Ostroveanu")));
// true

Se poate i mai bine?

15

O implementare mai bun

public class Name {
// ...
public int hashCode () {
return [Link] () * 37
+ [Link] ();
}
}

De ce este mai bun? (revedei cerinele)

16

Cerinele 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

17

nainte de a merge mai departe

Avei nelmuriri n legtur cu hashCode?
ntrebai acum!

Vom folosi metoda ulterior n lucrul cu colecii

V poate cauza comportamente ciudate dac nu-i

nelegei scopul

18

Coleciile Java
Sunt un ansambul de interfee i clase ce
realizeaz:
Colectarea obiectelor laolalt
Stocarea obiectelor
Sortarea obiectelor
Accesarea obiectelor

Furnizeaz o sintax comun pentru toate

variantele de implementare a coleciilor

19

Cum folosim coleciile

Adugm import [Link].*; la nceputul fiierului
java unde folosim colecia

package lab2;
import [Link].*;
public class CollectionUser {
List<String> list = new ArrayList<String> ();
// ...
}
20

Sintaxa general Collection<Ceva>

boolean add (Ceva c);

boolean contains (Object o);

boolean remove (Ceva c);

int size ();

Fiecare colecie se particularizeaz pentru un tip de dat

anume folosind '<' i >' Spunem c folosim abloane.
ex. Collection este o interfa ablon
21

Un exemplu de folosire
List<Name> unu = new ArrayList<Name> ();
[Link] (new Name ("Dan", "Ostroveanu"));
[Link] (new Name ("Radu", "Cuprescu"));
[Link] ([Link]());
[Link] (new Name ("Dan", "Ostroveanu"));
[Link] ([Link]());
List<Name> doi = new ArrayList<Name> ();
[Link] (new Name ("Mircea", "Kirakainen"));
[Link] (doi);
[Link] ([Link]());
22

Colecii generice
Putem specifica tipul de dat pe care l va folosi
colecia

Ex: List<String> strings

Suntem siguri c strings va conine numai obiecte

de tip String

E opional, ns foarte folositor

23

De ce folosim tipuri generice?

List untyped = new ArrayList ();

List<String> typed = new ArrayList<String> ();
Object obj = [Link] (0);
String sillyString = (String) obj;
String smartString = [Link] (0);
24

Accesarea obiectelor: iterator

Avem colecia:
Collection<Ceva> col;
Iterator:
Iterator<Ceva> it = [Link] ();
while ([Link] ()) {
Ceva obj = [Link] ();
// procesm obj
}
For each:
// form sinonim, dar mai compact
for (Ceva obj : col) {
// procesm obj
}

25

tergerea din colecie a obiectelor

Nu se pot scoate din colecie obiectele n timp ce se itereaz!
for (Ceva obj : col) {
[Link] (obj);
// ConcurrentModificatonException
}
Numai iteratorul poate terge obiectul pe care itereaz la acel
moment
Iterator<Ceva> it = [Link] ();
while ([Link] ()) {
Ceva obj = [Link] ();
[Link] (obj);
// i nu [Link] (obj);
}
De remarcat c [Link] este opional i nu toate obiectele ce
implementeaz Iterator vor suporta metoda

26

Tipurile de colecii generice

List

Set

ArrayList
LinkedList
HashSet
TreeSet

Map

HashMap
TreeMap
27

Interfaa List
List de obiecte accesabile ntr-o ordine, similar cu un
vector
Spre deosebire de vector, nu avem o mrime n care
trebuie s ne ncadrm
Ordinea elementelor din list este dat de ordinea
introducerii lor

List<String> strings = new ArrayList<String> ();

[Link] (unu);
[Link] (doi);
[Link] (trei);
// strings = [ unu, doi, trei ]
28

Alte feluri de acces

Introducerea cu un index:
List<String> strings = new ArrayList<String> ();
[Link] (unu);
[Link] (trei);
[Link] (1, doi);
// strings = [ unu, doi, trei ]
Accesarea obiectelor folosind un index:
[Link] ([Link] (0));
[Link] ([Link] (unu));
29

// unu
// 0

Interfaa Set
Set-ul nu are nici size i nici vreo ordine
Nu sunt permise obiecte duplicat!

Set<Name> names = new HashSet<Name> ();

[Link] (new Name (Jack, Daniels));
[Link] (new Name (Jack, Daniels));
[Link] ([Link] ()); // 1
30

Constrngerile 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 coninutul,
apelarea lor trebuie fcut selectiv
Dac nu respectai aceast constrngere, ateptaiv la comportamente bizare
31

Folosire incorect
Set<Name> names = new HashSet<Name> ();
Name jack = new Name (Jack, Daniels);
[Link] (jack);
[Link] ([Link] ());
[Link] ([Link] (jack)); // true
[Link] = "Rangers";
[Link] ([Link] (jack)); // false
[Link] ([Link] ());
// 1
32

Soluii pentru rezolvare?

Nu avem

Aa c nu se recomand o astfel de abordare

Dac e posibil, folosii seturi de date ce nu se

modific
Altfel, procedai cu atenie
33