I know how the HLA undergoes high degree of polymorphism (random genetic rearrangements), but I have not understood why it undergoes rearrangements. What is the advantage offered when HLA shows a high degree of polymorphism? What would have happen if all individuals had the same HLA?
There are multiple explanations for the enormous polymorphism in major histocompatibility complex (MHC -- the general term for the equivalent of HLA in all species) proteins. In general they reflect resistance to infectious disease, with the details being mildly debated, and usually not mutually exclusive -- multiple reasons probably apply.
The overall phenomenon is called balancing selection (Wikipedia link), and the most common explanations for the phenomenon in MHC are heterozygote advantage (which is not quite the same as overdominance), frequency-dependent selection, disease-specific selection, sexual selection, maternal-fetal interactions, and drift.
Simplistically, since MHC molecules are involved in protection against infectious disease, if there was only one MHC type then infectious agents that developed resistance to that type would be able to spread throughout the entire population readily. That means you as an individual are better off if your MHC is different from your neighbors', since you're likely to be more resistant to whatever pathogen is infecting them.
Many years ago I wrote a series of blog posts discussing the various evolutionary explanations in some detail, including dozens of references. The posts include: