Are you saying that there will be 2^32 buckets will be available? If yes, we can print out the bucket id ( i know only in c++). I would take the pleasure of doing it and try to get back with results. Also, I didn't get this point of yours - "So while theoretically interesting, wouldn't it be safe in practise to consider O(1) complexity for 99.99% of cases?".