  We do a systematic search of supergravity solutions that, via the
AdS$_5$/CFT$_4$ correspondence, are dual to thermal states in $\mathcal{N}=4$
SYM at finite chemical potential. These solutions dominate the microcanonical
ensemble and are required to ultimately reproduce the microscopic entropy of
AdS black holes. Using a mix of analytical and numerical methods, we construct
and study static charged hairy solitonic and black hole solutions with global
AdS$_5$ asymptotics. They are constructed in two distinct consistent
truncations of five dimensional gauged supergravity (and can thus be uplifted
to asymptotically AdS$_5\times$S$^5$ solutions of type IIB supergravity). In
the "single charge" truncation which consists of one charged scalar field,
hairy black holes exist above a critical charge and merge with the known
Cvetic-L\"u-Pope (CLP) black holes along a curve determined by the onset of
superradiance in the latter family. The lowest mass hairy black hole is a
singular zero entropy soliton. In the "two charge" truncation which consists of
a two equal charged scalar fields, hairy black holes exist for all charges and
merge with the known CLP black holes along their superradiant onset curve. The
lowest mass hairy black hole is a smooth supersymmetric zero entropy soliton.
Together with the known phases of the truncation with three equal charges, our
findings permit a good understanding of the full phase space of SYM thermal
states with three arbitrary chemical potentials.
