I have always been under impression that Pandas uses hashing when indexing the rows in a dataframe such that the operations like df.loc[some_label] is O(1).
However, I just realized today that this is not the case, at least for multi-indexed dataframe. As pointed out in the document, "Indexing will work even if the data are not sorted, but will be rather inefficient (and show a PerformanceWarning)". Some articles I found seem to suggest, for multiindex dataframe, Pandas is using binary-search based indexing if you have called sort_index() on the dataframe; otherwise, it just linearly scans the rows.
My question are
- Does single-indexed dataframe use hash-based indexing or not?
- If not for question 1, does it use binary-search when sort_index() has been called, and linear scan otherwise, like in the case of multi-indexed dataframe?
- If yes for question 1, why Pandas choose to not use hash-based indexing for multi-index as well?