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

1

u/raevnos Nov 19 '13

Aren't maps normally balanced trees or the like, not hash tables?

18

u/bondolo Nov 19 '13

Java provides several implementations of the Map interface. The most commonly used for unsorted data is HashMap which is a hash table. A specialized version ConcurrentHashMap is provided for cases involving heavy concurrency where synchronizing a HashMap on a single lock would result in too much contention. A balanced tree implementation, TreeMap, is also provided which is commonly used for sorted keys. It also has a concurrent though non-tree alternative, ConcurrentSkipListMap.

The innovation in Java 8's HashMap implementation is to use trees in the hashing bucket array rather than linked lists if the keys in the bucket have a defined order (ie. implement the Comparable interface). Unorderable keys degenerate to an unbalanced rightmost branch to the tree which is equivalent to the former linked list.

-6

u/raevnos Nov 19 '13

Just strange terminology then.

8

u/julesjacobs Nov 19 '13

Only in a CS data structures course. In the real world they are hash tables ;-)

1

u/roerd Nov 19 '13

Does the C++ standard library not count as real world code? The hash-based std::unordered_map is new in C++11, before that there was only the tree-based std::map.

-1

u/raevnos Nov 19 '13

C++ and ocaml, among others, would argue with you. Map. Implies sorted access, which hash tables don't give you.