Getting number of random timestamps throughout a day in Java

What would be a good way to go about this? I wish to show a message 5 times at random times throughout a day. I currently use the following method to generate timestamps:

List<Long> timestamps = new ArrayList<Long>();

long currentTimestamp = (long) (System.currentTimeMillis() / 1000L);
long endTimestamp = addHoursToTimestamp(8, currentTimestamp);

int n_timestamps = 5;
for (int i = 0; i < n_timestamps; i++) {
    Long randomTime = currentTimestamp + Math.abs(new Random().nextLong()) % (endTimestamp-currentTimestamp);
    timestamps.add(randomTime);
}

Sometimes this works good and I get nicely spread out timestamps. Of course as you can imagine, sometimes the timestamps are really close to one another, like in this example where there are 3 timestamps at the 11th hour (in a timespan of 11:00-19:00):

1435483835  Sun Jun 28 11:30:35 CEST 2015
1435501808  Sun Jun 28 16:30:08 CEST 2015
1435484646  Sun Jun 28 11:44:06 CEST 2015
1435495886  Sun Jun 28 14:51:26 CEST 2015
1435483799  Sun Jun 28 11:29:59 CEST 2015

This is not ideal, since I want the timestamps to be spread out a bit. To fix this I created a function that loops over all timestamps already added to the array, and check if the generated timestamp is at least an hour later or earlier than each of those.

However, I don't know if this is the preferred way to go about it. Seems pretty heavy in computation.