Blog
Skip to end of metadata
Go to start of metadata

...avagy a jó, a rossz és a csúf. A közös tulajdonságuk egyszerű, implementálják a Map interfészt, s kulcs-érték mentén tárolnak adatokat, illetve a hatékony működést a kulcs hash értéke alapján végzik. Mi a különbség a HashMap, a TreeMap és a Hashtable között? A legelső implementáció a Hashtable, amely az 1.0 óta van jelen a Java nyelvben, mondhatni együtt nőtt fel vele. Manapság eléggé mellőzött szerepe van, szinte alig találkozunk a Hashtable alapon szervezett tárolókkal, s ennek egyik oka a szinkronizált működés adta lassúsága. További érdekessége a Hashtable osztálynak, hogy nem szereti a null értékeket, az alábbi program:

Map map = new Hashtable();
map.put("a", null);

Szép kivételt okoz futásidőben:

Exception in thread "main" java.lang.NullPointerException
        at java.util.Hashtable.put(Hashtable.java:394)
        at test.Main.test(Main.java:16)

Hasznos lehet tudni, hogy a Properties osztály a Hashtable osztályból származik, ezért nem tudunk null értéket vagy kulcsot felvenni, mint property.

A HashMap és a TreeMap egyidőben, az Java 1.2 idejében került a nyelv alapvető osztályai közé, és mindketten megvalósítják a Map interfészt, így mind a három implementáció könnyedén cserélhető, ha jól írtuk meg a programot (érdekességképp megemlíteném, hogy a Hashtable csak az 1.2 verziótól implementálja a Map interfészt).

A HashMap két alapvető dologban különbözik a Hashtable osztálytól: elviseli a null értéket, illetve működése nem szinkronizált, így nem kell vizsgálnunk a kulcsot vagy az értéket, azonban szálbiztos környezetben tudjuk csak használni.

A TreeMap - ellentétben az előző kettővel - képes rendezett sorrendben tartani a beledobott értékeket a kulcs alapján, tehát a hozzáadott értékeken a kulcs alapján növekvő sorrendben tudunk végiglépkedni:

Map map = new TreeMap();
map.put("d", "d");
map.put("a", "a");
map.put("b", "b");
map.put("c", "c");
for (Object key : map.keySet())
{
  System.out.println(key);
}

Az eredmény a kulcs objektuma által diktált sorbarendezés (vagy a compareTo metódus):

a
b
c
d

A TreeMap ilyen viselkedése okán a kulcs általában nem lehet null, mivel ekkor a legtöbb osztály bizony kivételre fut:

Exception in thread "main" java.lang.NullPointerException
        at java.lang.String.compareTo(String.java:1167)
        at java.lang.String.compareTo(String.java:92)

Lezárásképp nézzük meg, hogy milyen teljesítményre számíthatunk a három implementáció esetén. A méréshez egy objektum tárat használunk, mivel a Map interfész nem fogad el primitív típust, így előre el kell készítenünk sok ezer különböző példányt, különben meghamisítanánk a mérést, a kód így néz ki:

Integer[] objectPool = new Integer[2000000];
for (Integer j = 0; j < 2000000; j++)
{
  objectPool[j] = j;
}

long startTime = System.nanoTime();
for (Integer i = 0; i < 100; i++)
{
  map = new HashMap();
  for (int j = 0; j < 2000000; j++)
  {
    map.put(objectPool[j], i);
  }
}
System.out.println(Math.round((System.nanoTime() - startTime) / 10000) / 100.0 + " ms");

startTime = System.nanoTime();
for (Integer i = 0; i < 100; i++)
{
  for (int j = 0; j < 2000000; j++)
  {
    map.get(objectPool[j]);
  }
}
System.out.println(Math.round((System.nanoTime() - startTime) / 10000) / 100.0 + " ms");

Ebben fogjuk a konkrét implementációt lecserélni sorban a három osztály egyikére. Nos, nézzük az eredményeket (vagyis 200 millió put és 200 millió get hívás idejét):

Hashtable:
90611.36 ms 
3974.38 ms 
HashMap: 
86662.92 ms 
3982.17 ms 
TreeMap: 
143784.58 ms 
38699.3 ms

A következtetéseket mindenki vonja le magának.

      
      
Page viewed times

3 Comments

  1. Auth Gábor AUTHOR

    Nálatok is ilyen lassú a TreeMap? Én csalódtam kicsit benne...

    1. Nálatok is ilyen lassú a TreeMap? Én csalódtam kicsit benne...

      Én őszintén nem nagyon használtam eddig,csak a HashMap-t. Viszont az egyik alkalmazásomnál használnom kellett a db4o objektum orientált adatbázist és ott a HashMap-el több idő volt a bejárás és a memória használata is, mint a TreeMap-nél. Százezres nagyságú Map-el dolgoztam. A TreeMap ebben az esetben nálam látványosan jobban teljesített, mint a HashMap.

    2. Az alap "gyorsaság":

      TreeMap:  guaranteed log(n) time cost for the containsKey, get, put and remove operations.
      HashMap: provides constant-time performance for the basic operations (get and put), The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls. 

      A Hashmap egy kulcsból képez egy hash-t és azt használja indexnek, olyan mint egy asszociatív tömb. A Treemap egy red-black tree implementáció.
      Mind a kettőnek meg van a maga alkalmazási helye, szerintem nincs értelme összehasonlíztani, mert egész más esetekben van értelme használni az egyiket és a másikat. Treemap-et akkor használj, ha a kulcsok sorrendjének van jelentősége.

#trackbackRdf ($trackbackUtils.getContentIdentifier($page) $page.title $trackbackUtils.getPingUrl($page))