Map

Iskalna tabela (Map) predstavlja tabelo parov <ključ,vrednost>, ki omogoča učinkovito iskanje vrednosti po ključih.

V angleščini jo imenujemo

• Hash (v Perl jeziku)
• map
• lookup table
• associative array
• dictionary

Ključi

• ključi so enolični (se ne smejo ponavljati)
• lahko so poljubnega tipa (ne nujno celoštevilski)

Primer ključa: vpisna številka

Vrednosti

Vrednosti vsebujejo podatke

Primer vrednosti: objekt tipa študent z vsebino

Primeri:

• slovar

niz(beseda),niz(pomen)

• legenda

barva,pomen

• kazalo

poglavje,podpoglavje

• seznam lokacij

lokacija,ime

Collection Framework

Collection Framework vsebuje:

• generični vmesnika Map in SortedMap

Map je bolj splošen

SortedMap je urejena iskalna tabela

• generični abstraktni razred AbstractMap

• več realiziranih generičnih razredov:

• HashMap
• TreeMap
• WeakHashMap

public interface Map
  { int size();
    boolean isEmpty(); //ali je prazen ali ne
    boolean containsKey(Object k);     //pove ali obstaja nek kljuc
    boolean containsValue(Object v);   //pove ali obstaja vrednost
    Object get(Object k);              //vrne kljuc
    Object put (Object k, Object v);   //metoda za dodajanje
    Object remove(Object k);           //odstranjevanje po kljucu
    putAll(Map);   //doda celo iskalno tabelo
    clear();       //izprazni
    Set keySet();    //vrne mnozico kljucev
    Set entrySet();  //vrne mnozico parov
    ...
    Collection values(); //vrne zbirko vrednosti (ni mnozica ker omogoca ponavljanje)
 
  public interface Entry {   //vmesnik za 1 par
    Object getKey();           //vrne kljuc
    Object getvalue();         //vrne vrednost
    Object setValue(Object v);  //nastavi vrednost
    boolean equals(Object o);   //preveri enakost 2 parov
    int hashCode();            //hash koda para
  }
  boolean equals(Object o);  //preveri enakost 2 iskalnih tabel
  int hashCode();          //hash koda celote
}

HashMap

Razred HashMap

• realizacija z (zaprto) razpršeno tabelo (hash table)
• v ozadju tabela določene kapacitete
• razporejanje s pomočjo razpršilne funkcije:

• zagotavlja hitro vstavljanje in iskanje
• problem kolizij:

• linerno ponovno razprševanje
• kvadratično ponovno razprševanje
• odprte razpršene tabele

• zagotavljanje primerne kapacitete in zasedenosti

Primer

Prikaz razprševanja v Javi

slovensko – angleški slovar

import java.util.*;
public class Slovar {
  public static void main(String[] args) {
 
    Map<String,String> slovar = new HashMap<String,String>();
 
    slovar.put("day","dan");
    slovar.put("ear","uho");
    slovar.put("hat","klobuk");
    slovar.put("one","ena");
    slovar.put("six","sest");
    slovar.put("ten","deset");
    slovar.put("two","dva");
    slovar.put("yes","da");
 
    System.out.println("Slovar: "+slovar);
 
    System.out.println("Velikost: "+ slovar.size());
    System.out.println("Slovar.keySet(): "+ slovar.keySet());
    System.out.println("Slovar.values(): "+ slovar.values());
    System.out.println("Slovar.entrySet(): "+ slovar.entrySet());
    System.out.println("Slovar.get(one): "+ slovar.get("one"));
    System.out.println("Slovar.remove(one): "+ slovar.remove("one"));
    System.out.println("Slovar.get(one): "+ slovar.get("one"));
 
    System.out.println("Slovar: "+slovar);
    System.out.println("Velikost: "+ slovar.size());
 
    //System.out.println("Slovar.put(six,6): "+ slovar.put("six",new Integer(6)));
    System.out.println("Slovar.put(six,sestica): "+ slovar.put("six","sestica"));
    System.out.println("Slovar.put(yes,null): "+ slovar.put("yes",null));
    System.out.println("Slovar.put(null,dva): "+ slovar.put(null,"dva"));
 
    System.out.println("Slovar: "+slovar);
    System.out.println("Velikost: "+ slovar.size());
 
    System.out.println();
 
    Map<String,String> slovar1 = new HashMap<String,String>();
 
    slovar1.put("yes","da");
    slovar1.put("two","dva");
    slovar1.put("ten","deset");
    slovar1.put("six","sest");
    slovar1.put("one","ena");
    slovar1.put("hat","klobuk");
    slovar1.put("ear","uho");
    slovar1.put("day","dan");
 
    System.out.println("Slovar1: "+slovar1);
 
    print("yes");
    print("two");
    print("ten");
    print("six");
    print("one");
    print("hat");
    print("ear");
    print("day");
 
    Map<String,String> slovar2 = new TreeMap<String,String>();
 
    slovar2.put("yes","da");
    slovar2.put("two","dva");
    slovar2.put("ten","deset");
    slovar2.put("six","sest");
    slovar2.put("one","ena");
    slovar2.put("hat","klobuk");
    slovar2.put("ear","uho");
    slovar2.put("day","dan");
 
    System.out.println("Slovar2: "+slovar2);
  }
 
  public static void print(String s) {
    final int MASK= 0x7FFFFFFF; //2**32-1
    final int CAPACITY = 16;
    System.out.println(s+" - "+s.hashCode()+" : "+(s.hashCode()&MASK)%CAPACITY);
  }
}

TreeMap

Razred TreeMap

• realizacija z dvojiškim iskalnim drevesom
• v ozadju ustrezno povezano drevo objektov
• upošteva urejenost po ključih – izpis

Primer uporabe: kazalo

WeakHashMap

Razred WeakHashMap

• realizacija s šibkimi razpršenimi tabelami
• ko ključ (ali vrednost) ni več dosegljiv, se element odstani iz tabele

Primer uporabe: seznam datotek na disku ...