There is no need to make the hash table size prime size, and it costs you because each lookup now requires a divide instead of a bit-wise and. If the bits of your hash function are truly random and you make each bucket a list, then there is no gain.