- Can a PPL be a safety pilot?
- Is 'cost sharing' different between jet and prop powered aircraft?
- Do I need 35 hours of ground school for knowledge test for PPL?
- Loud audio recording microphone
- Adaptive subdivision with Volume scatter
- Loading obj file, loosing texture
- Trouble importing my model materials to unity
- Get specific pixel from texture in material node
- Objects gray when rendered
- Political candidate's stances on specific issues?
- Data on minimum wage by country?
- Web8.5 CMS Connection Error: Attempt by security transparent method
- Having known vs Knowing
- “Your bonus will be prorated for your first year.” - Incorrect use of prorated?
- Happy to hear that!/ Great to hear that!/ Glad to hear that!
- While framing a sentence using a team,
- They had lost all hope. OR They lost all hope
- Is there a difference between “with time” and “over time”?
- Is there a word/phrase that means “first nature”?
- Magento 2 Echo level 3 category using Rest Api
What is the difference between abstract and concrete data structures?
I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that
For dictionaries with very small numbers of bindings, it may make
sense to implement the dictionary using an association list, a linked
list of bindings. ...
The most frequently used general purpose implementation of an
associative array is with a hash table: an array of bindings, together
with a hash function that maps each possible key into an array index.
Dictionaries may also be stored in binary search trees or in data
structures specialized to a particular type of keys such as radix
trees, tries, Judy arrays, or van Emde Boas trees. ...
So, I think, my problem lies in that I don't know that associative array (i.e. map, or dictionary) is an abstract data type and hashing table is a concrete data structure, and different concrete data structures can be used to implement the same abstract data type.
The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations described by the ADT (possibly with some probability of success in the case of randomized structures), but each concrete structure may make different guarantees of the running times of each operation. The choice of which concrete data structure to implement for a given ADT usually depends on the priorities of efficiency of each operation (including initializing the structure) and the complexity of implementing and maintaining the various data types. Some concrete data structures have excellent theoretical guarantees, but the overhead is such that a slightly less theoretically optimal data structure may be a better choice in practice.2018-03-13 17:53:35
Abstract data type describes what operations are available and what laws they obey. E.g. a dictionary allows you to store a value under a given key and to retrieve a value for a key, and promises that if you first store a value and then retrieve it with the same key, you will get the value you stored back. A stack has push and pop operations.
Concrete data type says how these operations are actually implemented.2018-03-13 18:46:10