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. So my questions would be

• what are the difference and relation between abstract data structures and concrete data structures?

• what examples are for each of them (abstract and concrete data structures)? The more the better.

• Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

Thanks!

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.

My questions would be

• What is the difference and relation between abstract data structures and concrete data structures?

• What examples are for each of them (abstract and concrete data structures)? The more the better.

• Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

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. So my questions would be

• what are the difference and relation between abstract data structures and concrete data structures?

• what examples are for each of them (abstract and concrete data structures)? The more the better.

• Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

Thanks!

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. So my questions would be

• what are the difference and relation between abstract data structures and concrete data structures?

• what examples are for each of them (abstract and concrete data structures)? The more the better.

• Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

Thanks!