Array of buckets. Buckets are accessed by using modulo on the keys hashcode in order to access the right bucket. If an object has the same hash code as an existing one (hash collision), you effectively have a linked list in the given bucket. If the size of the linked list exceeds 7 or 8 and the key is of type Comparable, the list is transformed into a TreeMap. Explaining complexity all the way long.