2-2 Dictionaries.ppt2-2 Dictionaries.ppt

2-2 Dictionaries.ppt2-2 Dictionaries.ppt2-2 Dictionaries.ppt2-2 Dictionaries.ppt

1. Dictionaries
•A dictionary in
data structure is used to store the data in
the
form of key-value pair.
•The
dictionary in data structure has an attribute called
the key.

•The
key is the attribute that helps us locate the data or
value
in the memory.
•supports
a wide variety of operations using a wide
variety
of methods and functions.
•The
keys are always unique within a dictionary.
•The
values of the dictionary in the data structure may
or
may not be unique.
•We
can put heterogeneous type values inside the
dictionaries.

2. Key attribute
A
 
key 
attribute of the dictionary in data structure follows rules.
•The
 
key 
attribute of the dictionary data structure must be
unique and consist of a single element. The unique nature
helps us in faster and easy retrieval of the corresponding set
of values.
•As no duplicate keys are allowed in the dictionary data
structure, whenever a duplicate
 
key 
is found, the last
assigned value is treated as the final key-value pair. So, if we
insert duplicate keys then our original data is lost.
•The key attribute is case sensitive hence "KEY" is not the
same as "key".
•The
 
key 
attribute is immutable hence, we cannot have an
array or list as keys we can only have numbers, strings, etc,
as the
 
key.

3. Value attribute
•The
 
value 
part or attribute of the dictionary in data
structure is simpler to define with lesser rules
imposed on it.
• The
 
value 
part can be a single value or a collection
of values stored in any sequential data type like lists,
tuples, sets, etc.

4. Operations on Dictionaries
•Data Insertion: The data is only inserted into a dictionary
data structure when there is no such key-value pair already
existing in the dictionary. Now, if a key-value pair is already
inserted previously then the old key-value pair will be
overridden by the new key-value pair.
•Data updation: The value of any data element can be easily
updated. We first need to access the value using a key
attribute and then update the corresponding value(s).
•Data deletion or removal: We can also delete a key-value
pair in a dictionary by accessing the
 
key 
attribute. We should
know that if a key is not present in the dictionary and we are
trying to delete the key value then an error is shown.
•Data verification: We can also verify or check where a
particular key exists in the dictionary or not.
•Keys: 
Return a collection of all the keys in the dictionary.
•Values: 
Return a collection of all the values in the dictionary.

5. Types of Dictionaries
•Ordered dictionary.
•In an ordered dictionary, the relative order is
determined by comparison on keys.
•The order should be completely dependent on
the key.
•Unordered dictionary.
•In an unordered dictionary, no order relation is
assumed on keys.
•Only equality operation can be performed on the
keys.

6. Types of Dictionaries
•Ordered dictionary.
•In an ordered dictionary, the relative order is determined
by comparison on keys.
•The order should be completely dependent on the key.
•Unordered dictionary.
•In an unordered dictionary, no order relation is assumed
on keys.
•
Only equality operation can be performed on the keys.

7. Implementation of Dictionaries
•A dictionary can be implemented in several
ways, such as
•Fixed length array.
•Linked lists.
•Skip lists
•Hashing
•Trees (BST, Balancing BSTs, Splay trees, Tries
etc.)

8. Implementation of Dictionaries using Array
•One approach is to use two arrays, one for
the keys and one for the values, where the
key at index i in the key array corresponds to
the value at index i in the value array.
•Variables used to implement Map in C
•This implementation uses two
arrays,
 
keys 
and 
values, to store the key-value
pairs.
 
•The maximum number of elements in the map is
defined as
 
MAX_SIZE.
 
•The
 
size 
variable keeps track of the current
number of elements in the map.

9. Implementation of Dictionaries using Array contd…
•Functions used to implement Map in C
•The
 
getIndex 
function searches for a key in
the
 
keys 
array and returns its index if found, or -1
if not found.
 
•The
 
insert 
function inserts a key-value pair into
the map. If the key already exists, it updates the
value.
 
•The
 
get 
function returns the value of a key in the
map, or -1 if the key is not found.
 
•The
 
printMap 
function prints all the key-value
pairs in the map.

10. Advantages linear list representation of a dictionary
•Simplicity: 
A linear list is simple and easy to implement.
•Dynamic Size: 
The list can grow or shrink as key-value
pairs are added or removed.
Disadvantages linear list representation of a
dictionary
•Search Time: 
The search time is linear in the worst
case, which can be inefficient for large numbers of
entries.
•Insertion Time: 
Similar to search, if the list is being kept
in sorted order, then finding the correct place to insert a
new key can take linear time.
•Deletion Time: 
Removing an entry requires a search
followed by a deletion, both of which can be inefficient in
a large list.
•