Какую структуру данных выбрать для хранения данных в памяти?
А зачем непосредственно в приложении это делать? Возьмите, к примеру, redis.io, в нем и храните. Там не только sortedset, но и hash и и сounters и еще кучу всего реализовано. Работает быстро, лежит в памяти, кластеризуется и шардируется.
В вашем случае удобней было бы держать ваши атрибуты в sortedset, где имя коллекции = атрибут, а значениями - id пользователей.
Всех пользователей сразу нужно вывести? А может все-таки не стоит их столько хранить в памяти?Какая из уже имеющихся структур данных java лучше всего подойдет для этих целей? 
Лучше, чтобы это не Java была, а C/C++, для этого используйте JNI, иначе ОЗУ будет много занимать, да и быстродействие вряд ли получится на высоте.