In my opinion, hash randomization issue do not mean that you're guaranteed different keys order on different runs (but sometimes you will), it means something different.

algorithm complexity attack only means you'll not get hash slowness because all hash items felt into same bucket so extracting hash element will be O(N), instead of O(log(N))

However the moral is - you must not pretend that keys order is same between runs (so some programs probably stopped working when hash randomization was introduced)