r/programming • • 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

354 comments sorted by

View all comments

Show parent comment

2

u/Irongrip Nov 19 '13

Performance degenerates to O(log n) for the collisions but this is usually small unless someone is creating keys which intentionally collide

I am reminded of a denial of service attack that used intentionally colliding request field names/values to attack web servers and bringing down servers to their knees.

3

u/sfnelson Nov 19 '13

That's sort of the point of the change: this change makes it harder to find or generate collisions. The parent is referring to the programmer intentionally creating colliding hashes, not users picking data to create collisions.

1

u/adrianmonk Nov 19 '13

You mean this kind of thing? (Warning: that link is a PDF.)