Dictionaries

1. definition
2.  Types of Dictionaries
     (a) Ordered Dictionary
     (b) Unordered  Dictionary
3. Examples
4. Operations  on   dictionary

5. ADT  for  Dictionary
6. Representation of Dictionaries:
     1. Linear  List  Representation
     2. Hash  Table  Representation
7. Static and Dynamic Hashing
8. QUESTIONS on Dictionaries

1. Definition:

Dictionaries   is  a  collection   of  pairs  of  KEY  and  VALUE     where  every  value  is  associated  with  the  corresponding  keys .The  abstract  data type “dictionary”  is  one  of  the  most  important  structures  in  computer science. Different   data  structures  have  been  proposed  for implementing  dictionaries  including  hash  table, skip list   and  balance  and  unbalanced   binary  search  trees   so  choosing  right  one  can  be  tricky. Depending   up on the applications, it is also a decision that can   be   significantly impact performance.

DICTIONARIES:

Ø  Dictionaries  contain data elements as  pair  of  the form(k, v)where  k  is key,

                                                                                                                  V is value.

Ø  The  field  key  must be unique  and is  used   to identify   the data elements   uniquely. No  two pairs  are allowed  to  have the same key.

A  dictionary  with duplicates is  a dictionary  which allows two or more (key,value)pairs  with  the same  key.To solve  the ambiguity while  performing  operations  on the  elements  with duplicate keys,dictionaries  should  frame  some  rules.

Example:

Ø  A    dictionary   that stores student records.

Ø  A    general  dictionary  of   words.

Ø  A    computer  dictionary   similar  to   dictionary   of  words.

Symbol   table  is  a    dictionary    with   duplicates   which   is  used   by  a  computer.

Hashing

Data Structures through c++