What is the fastest way of getting a random element from any native data structure in Java?

I am curious what the fastest way of getting a random element from a data structure is in Java. I don't care what type of data structure is used as long as it's native.

I want to know because I've created a "semi-random" name generator and I have a large HashSet of first names and another HashSet of last names and it takes awhile to iterate through them and find a random element from each.

I am using OpenJDK 11.