Maps/Operations and Performance: Difference between revisions
From charlesreid1
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java | Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java | ||
According to OpenJDK source code, TreeMap should take O(log N) time. | According to OpenJDK source code, TreeMap should take O(log N) time. However, the TreeMap is apparently O(1). | ||
https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java | It seems that you have to get to very large TreeMaps to get actual O(N) performance. (Meaning, it probably utilizes a large initial hash map size, incurring less overhead for access and maintenance but higher cost in storage/memory.) | ||
Here is a link to the TreeMap class: https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java | |||
=Flags= | =Flags= | ||
Revision as of 02:20, 29 June 2017
Notes
Link on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/hash/timing/TimingMap.java
According to OpenJDK source code, TreeMap should take O(log N) time. However, the TreeMap is apparently O(1).
It seems that you have to get to very large TreeMaps to get actual O(N) performance. (Meaning, it probably utilizes a large initial hash map size, incurring less overhead for access and maintenance but higher cost in storage/memory.)
Here is a link to the TreeMap class: https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/TreeMap.java
Flags
 |
Maps and Dictionaries Part of Computer Science Notes
Series on Data Structures
Maps/Dictionaries Maps · Maps/ADT · Maps in Java · Maps/OOP · Maps/Operations and Performance Map implementations: Maps/AbstractMap · Maps/UnsortedArrayMap · Maps/SortedArrayMap Dictionary implementations: Dictionaries/LinkedDict · Dictionaries/ArrayDict
Hashes Hash Maps/OOP · Hash Maps/Operations and Performance Hash Maps/Dynamic Resizing · Hash Maps/Collision Handling with Chaining Hash functions: Hash Functions · Hash Functions/Cyclic Permutation Hash map implementations: Hash Maps/AbstractHashMap · Hash Maps/ChainedHashMap
Skip Lists · Java/ConcurrentSkipList · Java implementations: SkipList
Sets Sets · Sets/ADT · Sets in Java · Sets/OOP · Multisets
|