Java-ban, a 8-as verziótól kezdve, ha egy HashMap vödörben túl sok ütközés van (több mint 8 elem), a vödörben lévő listát vörös-fekete fára alakítják a teljesítmény javítása érdekében.

Ebben az esetben a HashMap-ból való elemlekérés időbeli komplexitása az amortizált O(1)-ről (láncolt lista használatával) O(log n)-re változik, ahol n az adott vödörben lévő elemek száma (azaz a fa mélysége).

Ezért, a vödörben vörös-fekete fa használatával, az elem keresése O(log n) idő alatt történik.

Korábbi Következő