I was recently asked to provide proof of why using a ViewHolder would be faster than just using findViewById() when populating the item views of each item in a ListView. A fair question since empirically stating “it seems faster” is hardly proof and my results may have been from other factors I had not thought of at the time. So, I delved into the Android source code and pulled a bit of research together to present proof of why using a ViewHolder mechanism instead of findViewById() inside a ListView.getView() is more efficient and faster. I will be using Big O notation here, so if you need a refresher on it’s definition and meaning, I highly recommend skimming the definition over at Wiki as well as reading a fairly clear explanation of the meaning of using Big O notation from William Shields.

First, some assumptions need to be made. The list contains m number of items. Each item contains a ViewGroup, such as a LinearLayout or RelativeLayout, consisting of n number of views needing to be found and populated. Small numbers of either list items or views will not show a significant difference, but once you start using more than a handful of either, the difference become noticeable.

findViewById() is O(n!)

The findViewById() Android API method requires an algorithm to search your view hierarchy every time you call it by traversing the entire structure looking for the ID of your view. Traversing the hierarchy to find all n Views will result in the algorithm having O(n!) efficiency at best. A very simple example would be a LinearLayout with 5 views and no subchild views to search through. The first findViewById() would find the first view on the first child; the second find will read the first view and then the second; the third find would read the first, second, and then return the third view; and so on. You can verify my take on this algorithm by researching the Android source code yourself. To help get you started, I will point you to the ViewGroup’s method that actually performs the find (in Android 2.3.4 r1).

ViewHolder is O(1)

The ViewHolder mechanism stores the results returned by findViewById() in a HashMap and subsequent calls search the HashMap for the view instead of using findViewById(). In general, a hash algorithm is fast because it “hashes” the key and turns it directly into the location of the bin where the value is stored, making it an O(1) operation. Since we are using an int for our key and we are using Java’s HashMap, we have an O(1) efficiency (some discussion about this can be found here).

O(m) is better than O(m n!)

Comparing the two methods, ViewHolder is the best case scenario with O(1) and findViewById() comes in second with O(n!), but the distinction becomes even more apparent when you factor in the fact that these methods are done for each item in your list. O(m) is noticeably more efficient than O(m n!) — depending on the values of m and n, this can sometimes be better or worse than O(m²), but it will always be worse than O(m) for lists with more than 1 item.