Java Java Data Structures Efficiency! Custom Serialization

Patrick Y.
Patrick Y.
3,052 Points

Trying to understand the Code Challenge : Changing Course

I have a hard time understanding why we need to create a map first.

So in the upcoming code challenge, it asks us to create a map with video names as key, and the actual video as the value, and then use it to find a video and change its name.

Why cant we just go thru the course videos one by one to find the video with the desired title, and then change its name? Making a map seems like an extra step.

Appreciate any explanations. Thank you.

Simon Coates
Simon Coates
28,663 Points

If the key values for the map is contained by the value for any key-value pair, then you can use an arraylist and loop over until you find a value. But a map is built for looking stuff up, and i'd expect it has some smarts that offer performance improvements (i'm sure there are some ludicrously complicated technical details behind it).

Kristian Gausel
Kristian Gausel
14,645 Points

The details are quite simple, but you need a technical background to understand it. Taking a course in algorithms and datastructures should do it.

1 Answer

Kristian Gausel
Kristian Gausel
14,645 Points

So, this question is all about datastructures. The reason is that the lookup time in a hashmap is O(1) (big-o-notation: https://en.wikipedia.org/wiki/Big_O_notation) and looping through an array and checking the name one by one is O(n). This results in a much worse performance for large collections. Note that the lookup time for hashmaps is only good if you actually know the "key" for the item you want.

To understand this properly you need to take a course in datastructures, or maybe treehouse has some courses covering this topic (?)

Colby Wise
Colby Wise
3,165 Points

MIT's open course 6.006 (Introduction to Algorithms) is pretty good for covering Big-O notation / run-time complexity and the idea's behind this. Link to youtube lectures below. I think the first few videos give decent understanding/intro to Big-O w/ examples via recitations. Lecture 8 is [hashing] ...but a bit more depth than is needed to get some clarity on the original question

https://www.youtube.com/watch?v=0M_kIqhwbFo&list=PLSX2U_ZE4Huk19DPn34oZlygPbsig380X&index=14