Edit Question - KnowledgeHub

Title Body

Which data structure is best in terms of computational complexity to implement a dictionary of (key,val) items, which must support only following commands: Insert(key) - appends an item (key,val) with val=1 Increment(key) - increments val of existed (key,val) Find(key) - returns a val of (key,val) Select(part_of_key) - returns a list of all items (key,val) if strstr(key,part_of_key)!=NULL in the form of a new dictionary of the same type (without allocating new memory if possible); for example if dictionary is {(red,3), (blue,4), (green,1)}, then Select(re)={(red,3), (green,1)} Max(i) - returns an item which has the i-th maximal value among all items; for example if dictionary is {(red,3), (blue,4), (green,1)}, then Max(1)=blue, Max(2)=red, Max(3)=green The keys are strings and the values are positive integers. The number of items in the dictionary is expected to be very large. I think it must be a synthesis of two different data structures. But should it be a hash table + a binary tree or a trie + sorted array or something else?

Tags (comma-separated) Cancel