I deem hash randomization and collision counting as a poor man's workaround for the actual issue. Perhaps we shouldn't try too hard to fix an unsuitable data type. Hash maps have a known worst case complexity of O(n). A O(log n) algorithm should be used to parses and malicious key/value pairs.

How about Python grows a additional btree implementation in its collections module? I know that it's not going to fix existing code. However in the long run it's the best safeguard against hash collision attacks. I'm thinking about a simple, self balancing btree like red-black-tree. A quick search on Wikipedia also revealed Scapegoat and Splay tree with interesting properties.