I definitely use so much DownValues structure for some many applications like to replace some common structures in a some way. It seems that DownValues is so fast for access, and set. My question is about complexity under DownValues usages.
For take to consideration: Suppose that, I can store in a DownValues Data relations between names of persons (short and long text_String) and Choices of whatever (List) such that I could have $n = 10000000$ of these relations and I want to search for names, and likely other operations like add choices for a specific person.
I've reading and It seems like DownValues structure has a pattern matching algorithm based on rules to access correctly to values. So I should say that:
- Searching or accessing to specific key is O(n).
- Create a new register, relations is O(1).
- Modify register to set will be O(1)
But, I really concern about that, I used DownValues with a lot of data, and definitely it seems, that above statements are wrong. But, I don't find in the documentation comments about it. I'm thinking that in a low-level, DownValues use some king of hashing functions to indexing, in the example case, strings, because it's seems to access be in O(1)(?) or some BST to execute a search with pattern? I don't know.
So, I share my doubts about it, and maybe help to others beginners to pay attention a this absolute useful data structure, DownValues