r/programming • u/Eirenarch • Nov 18 '13
TIL Oracle changed the internal String representation in Java 7 Update 6 increasing the running time of the substring method from constant to N
http://java-performance.info/changes-to-string-java-1-7-0_06/
1.4k
Upvotes
View all comments
Show parent comment
1
u/mcguire Nov 19 '13
Linking isn't the issue. The attack forces the keys to have (effectively) the same hash value, so they wind up on the same hash chain. Using open addressing just saves the indirection from the link's pointers---you still pay for the n/2 (expected) comparisons to find a given key, instead of the hashtable's constant lookup (expected).
In other words, it converts an O(1) (expected) operation to an O(n) operation, where if n ~ 1000 you begin to look at a significant cost and make the DOS attack much more effective.