Kunt u de interne structuur en het werkingsmechanisme van de hash-tabel in Java uitleggen?

Een hash-tabel in Java (bijvoorbeeld HashMap) is een datastructuur die paren van sleutel en waarde opslaat en snelle toegang via de sleutel biedt.

Interne structuur:

• De basis is een array van buckets (emmers).
• Elke bucket bevat ofwel null, of een gekoppelde lijst (of een boom, als er veel elementen zijn) van elementen met dezelfde hash-code modulo de grootte van de array.

Werking:

1. Bij het toevoegen van een element wordt de hash-code van de sleutel berekend en wordt de index van de bucket bepaald.
2. Als de bucket leeg is, wordt het element daar geplaatst.
3. Als de bucket bezet is, wordt gezocht in de gekoppelde lijst (of boom) of de sleutel al bestaat:
   • Als de sleutel gevonden wordt, wordt de waarde bijgewerkt.
   • Zo niet, wordt het element aan de lijst toegevoegd.
4. Wanneer een bepaald vulpercentage bereikt wordt, wordt de array uitgebreid (rehash) om de prestaties te behouden.

Deze aanpak zorgt voor een gemiddelde complexiteit van invoegen, zoeken en verwijderen die dicht bij O(1) ligt.

Voorbeeld van gebruik:

Map<String, Integer> map = new HashMap<>();
map.put("key1", 100);
Integer value = map.get("key1"); // snelle toegang via de sleutel