HashMap的底层结构主要由数组和链表组成，当链表的长度超过一定阈值时，链表会转换为红黑树以优化搜索效率。以下是HashMap的底层结构及其扩容过程的详细说明：

底层结构：

1. 数组（Buckets）：HashMap内部维护了一个名为table的数组，数组的每个槽位（slot）被称为一个桶（bucket），用来存储键值对（Entry或Node）。
2. 链表（Chains）：当不同的键通过哈希函数计算出相同的索引时，它们会以链表的形式存储在同一个桶中。
3. 红黑树（Trees）：在Java 8及以后的版本中，为了优化长链表的查询效率，当链表中的元素数量超过一定阈值（默认为8）时，链表会被转换成红黑树。

扩容过程：

1. 扩容触发：当HashMap中的元素数量达到当前容量与负载因子（load factor）的乘积时，就会触发扩容。
2. 计算新容量：新容量通常是当前容量的两倍，除非当前容量已经达到了最大容量（MAXIMUM_CAPACITY），此时不再进行扩容。
3. 创建新数组：根据新的容量创建一个新的数组。
4. 重新计算索引并迁移元素：遍历旧数组中的每个元素，根据新的容量重新计算每个元素的索引位置，并将它们迁移到新的数组中。

以下是扩容过程中的关键步骤：

• 重新计算索引：由于数组的容量增加，索引的计算方式也随之改变。对于每个键值对，它的索引位置要么保持不变（如果它的哈希码与旧容量相与的结果仍然为0），要么变为原索引 + 旧容量（如果它的哈希码与旧容量相与的结果不为0）。
• 迁移元素：对于每个桶中的链表或红黑树，需要重新遍历并插入到新数组中的正确位置。

下面是HashMap中扩容过程的简化伪代码：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    Entry[] newTable = new Entry[newCapacity];
    
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

在这个伪代码中，transfer方法负责将旧数组中的元素迁移到新数组中，并可能重新计算每个元素的哈希码（如果需要的话）。indexFor方法用于计算元素在新数组中的索引位置。

扩容是一个相对昂贵的操作，因为它涉及到重新计算所有元素的哈希码并将它们重新插入到新的数组中。因此，如果预先知道HashMap将存储大量元素，最好在创建HashMap时就指定一个足够大的初始容量，以减少扩容操作的次数。