Patrizia Scandurra [email protected]

EXE su tabelle hash

INFORMATICA III

Parte B - Progettazione e Algoritmi

Patrizia Scandurra [email protected]

Università degli Studi di Bergamo a.a. 2011-12

Hash table in JCF

• Hashing based collection classes: Hashtable, HashMap, and HashSet

•

keys:

Hashtable<String, Integer> numbers

= new Hashtable<String, Integer>();

numbers.put("one", 1);

numbers.put("two", 2);

numbers.put("three", 3);

To retrieve a number, use the following code:

Integer n = numbers.get("two");

if (n != null) {

System.out.println("two = " + n);

}

http://download.oracle.com/javase/6/docs/api/java/util/Hashtable.html

Hashtable (1/2)

• An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor.

• Generally, the default load factor (.75) offers a good tradeoff between time and space costs.

• Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most

Hashtable operations, including get and put).

• Constructors:

– Hashtable(): Constructs a new, empty hashtable with a default initial capacity (11) and load factor (0.75).

– Hashtable(int initialCapacity): Constructs a new, empty hashtable with the specified initial capacity and default load factor (0.75).

– Hashtable(int initialCapacity, float loadFactor): Constructs a new, empty hashtable with the specified initial capacity and the specified load

factor.

3

Hashtable (2/2)

• Hashtable is basically a data structure to retain values of key- value pair.

• It didn’t allow null for both key and value. You will get NullPointerException if you add null value.

• It is synchronized. So it comes with its cost. Only one thread can access in one time

Hashtable<Integer,String>; cityTable = new Hashtable<Integer,String>();

cityTable.put(1, "Lahore");

cityTable.put(2, "Karachi");

cityTable.put(3, null); /* NullPointerEcxeption at runtime*/

System.out.println(cityTable.get(1));

System.out.println(cityTable.get(2));

System.out.println(cityTable.get(3));

HashMap

• The default initial capacity is 16 and the default load factor is 0.75

• It allows null for both key and value

• It is unsynchronized. So come up with better

performance. If required, it must be synchronized externally.

HashMap<Integer,String> productMap = new HashMap<Integer,String>();

productMap.put(1, "Keys");

productMap.put(2, null);

//At creation time, to prevent accidental unsynchronized access //to the map

Map m = Collections.synchronizedMap(new HashMap(...));

HashSet

• HashSet does not allow duplicate values.

• HashSet can be used where you want to maintain a unique list.

• Default initial capacity is 16 and default load factor is 0.75.

• It provides add method rather put method.

• You also use its contain method to check whether the object is already available in HashSet.

• It is unsynchronized

HashSet<String> stateSet = new HashSet<String>();

stateSet.add ("CA"); stateSet.add ("WI"); stateSet.add ("NY");

if (stateSet.contains("PB")) /* if CA, it will not add but shows following message*/ System.out.println("Already found");

else stateSet.add("PB");

// At creation time, to prevent accidental unsynchronized access

Set s = Collections.synchronizedSet(new HashSet(...));

Equals() and hashcode()

The Java super class java.lang.Object has two very important methods defined in it:

– public boolean equals(Object obj): returns true if and only if x and y refer to the same object (x==y has the value true)

– public int hashCode(): returns the hash code value for the object on which this method is invoked. The hash code value is an integer supported for the benefit of hashing based

collection classes such as Hashtable, HashMap, HashSet etc.

These two methods are interrelated and they should be overridden correctly:

– It is generally necessary to override the hashCode method whenever the equals method is overridden,

– so as to maintain the general contract for the hashCode method, which states that equal objects must have equal

hash codes.

Correct Implementation Example

This implementation will

ensure that equal objects

will have equal hash codes.

Guidelines for implementing hashCode()

• Store an arbitrary non-zero constant integer value (say 7) in an int variable hash.

• Compute an hash code int var_code for each variable var of your object as follows:

– If the variable(var) is byte, char, short or int: var_code = (int)var;

– If the variable(var) is long: var_code = (int)(var ^ (var >>> 32));

– If the variable(var) is float: var_code = Float.floatToIntBits(var);

– If the variable(var) is double:

long bits = Double.doubleToLongBits(var);

var_code = (int)(bits ^ (bits >>> 32));

– If the variable(var) is boolean: var_code = var ? 1 : 0;

– If the variable(var) is an object reference:

var_code = (null == var ? 0 : var.hashCode());

• Combine this individual variable hash code var_code in the original hash code hash as follows: hash = 31 * hash + var_code;

• Follow these steps for all the significant variables and in the end return the resulting integer hash.

• Lastly, review your hashCode method and check if it is returning equal hash codes for equal objects. Also, verify that the hash codes returned for the object are

consistently the same for multiple invocations during the same execution. ⁹

Esercizi

1. Completare la definizione della classe CoordinatePair ridefinendo i metodi equals e hashCode:

public class CoordinatePair { private int x, y;

public int hashCode() {…}

public boolean equals(Object o) {…}

}

2. Come in 1. per la classe FourWheeler :

publicclass FourWheeler implements Vehicle { private String name;

private int purchaseValue;

private int noOfTyres;

}

3. Definire e testare la classe

FinancialHistory

• Attributi (privati):

int cashOnHand = la cifra presente sul conto Hashtable incomes = le entrate

Hashtable expenditures = le uscite

• Nello stesso file definire due classi per eccezioni: NegAmountException e NegCashException.

• Costruttore della classe FinancialHistory:

FinancialHistory(int amount) -- prende come argomento la cifra iniziale da mettere sul conto, che deve essere > = 0 altrimenti solleva eccezione negAmountException

• Metodi che leggono la situazione del conto:

– int cashOnHand() -- ritorna la cifra presente sul conto

– int receivedFrom(String s) -- se la stringa corrisponde alla descrizione di un'entrata, restituisce la cifra entrata

– int spentFor(String s) -- se la stringa corrisponde alla descrizione di un'uscita, restituisce la cifra uscita

Nota: l'implementazione di receivedFor e spentFor interroga la tabella hash, che ritorna un oggetto, tale oggetto viene convertito forzatamente a Integer, infine ne viene preso il valore int. <CONTINUA>

12

• Metodi che modificano la situazione del conto:

– void receiveFrom(int amount, String s) -- registra una nuova entrata con cifra amount e stringa di descrizione s, modifica sia la tabella hash

incomes che la cifra corrente sul conto (cashOnHand) aggiungendo amount

– void spendFor(int amount, String s) -- registra una nuova uscita con cifra amount e stringa di descrizione s, modifica sia la tabella hash

expenditures che la cifra corrente sul conto (cashOnHand) sottraendo amount

Nota: entrambe le funzioni vogliono amount > = 0 altrimenti sollevano

eccezione NegAmountException; la funzione spendFor controlla anche che dopo la spesa il conto non vada in rosso, e nel caso solleva eccezione

NegCashException.

• Metodi per stampa:

– String printIncomes() -- genera stringa con scritte tutte le entrate – String printExpenditures() -- genera stringa con scritte tutte le uscite