Hash Table(Hash Map): O(n) to O(1)

I been working in iOS project for a while, in which I had to built couple of screens those are completely driven by JSON returned from API. Every view and the nested hierarchy of views are driven by JSON. That seems interesting and this is what I got from the API.

Heres the sample JSON,

Heres the simple explanation,

viewType : Enum represents a different UI elements, like UIView , UIButton .. so on.

viewID : This is straight forward an unique identifier for each element

children : The child element that goes inside the view

This JSON will be parsed into to an object DynamicUIElement

Im not going to explain how I transform the JSON to UI, this article is not about that. This is about a specific case, and here it is,

We have built this view and the complete hierarchy. Now when the user interacts with the views, we need to find out which JSON object this view belongs. There you go! Thats what we are trying to solve here.

Lets list out what we have,

• UIView that user selected
• viewID of that view, which is same as DynamicUIElement.viewID
• Hierarchy of views
• Hierarchy of `DynamicUIElement`

Now, this was my first implementation.

It works, we merged the PR. Then later when I read the same code couple of months back, I felt we could improve this logic. Two things I noticed,

• There interface could be better.
• This logic seems brute force.

I started by improving the interface. I have updated the above logic to this,

I ran a measurement test for the above algorithm, now here’s result for that,

self.measure {
    _ = viewModel.viewForID(22651)
}

[0.002777, 0.000361, 0.000356, 0.000356, 0.000357, 0.000356, 0.000356, 0.000356, 0.000356, 0.000356]

Now I felt like I have accomplished something really good. Then I share this with my friend. He said, “Well, the interface looks good, but your algorithm is still O(n) which is good but now great algorithm, because we are still recursively iterating the children and its children and its children… and so on”, we could do better. The search performance is still not good. Then we discussed more and we came up with a better solution by taking advantage of HashTable(Hash Map) data structure.

What if we create a Hash Table to index the memory address of the DynamicUIElement objects?.

Hash Table’s time complexity is O(1).

So I decided to take that route. This is how the Hash Table looks like,

This hash table will stores the memory address of the a DynamicUIElement object against it's viewID, irrespective of the object’s depth in the hierarchy. Basically the index table is flat. With this table in our hand, we could avoid writing a search algorithm and find the object we are looking in a constant time O(1).

All we have to do now, is to make sure we add the memory address of any newly created DynamicUIElement object to the index table while parsing the data.

Now send back the IndexTable along with the parsed model to the caller.

I ran the same measurement test again, but this time the performance of the algorithm is far better,

[0.000046, 0.000008, 0.000004, 0.000004, 0.000004, 0.000004, 0.000003, 0.000003, 0.000003, 0.000003]

The results were impressive. We reduced the execution time from 0.000356 to 0.000003.

In HashTable approach, that I took, increases the space complexity, since we need to allocate extra memory for the IndexTable, but space wasn’t my worry, my goal was to improve the asymptotic time complexity of my algorithm.

Note that, there could be better algorithms that do well in both Time and Space such problems, if you find one please let me know in the comments.