...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.
3 Comments
Auth Gábor AUTHOR
Nálatok is ilyen lassú a TreeMap? Én csalódtam kicsit benne...
Tóth Tamás
É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.
Kocsis Gergő
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.