Dictionaries and Hash tables
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Dictionary – ADT
•The dictionary ADT models a searchable collection of key-element items
•Dictionary ADT methods:
•findElement(k): if the dictionary has an item with key k, returns its element, else, returns the
special element NO_SUCH_KEY
•insertItem(k, o): inserts item (k, o) into the dictionary
•removeElement(k): if the dictionary has an item with key k, removes it from the dictionary and
returns its element, else returns the special element NO_SUCH_KEY
•size(), isEmpty()
•keys(), Elements()
•Applications:
•address book, credit card authorization, mapping host names (e.g., cs16.net) to internet addresses
(e.g., 128.148.34.101)

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Log File
•A log file is a dictionary implemented by means of an unsorted sequence
•We store the items of the dictionary in a sequence (based on a doubly-linked lists or a circular
array), in arbitrary order
•insertItem takes O(1)
•findElement and removeElement take O(n)
•The log file is effective only for dictionaries of small size or for dictionaries on which
insertions are the most common operations, while searches and removals are rarely performed (e.g.,
historical record of logins to a workstation)

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Binary Search
•Binary search performs operation findElement(k) on a dictionary implemented by means of an
array-based sequence, sorted by key
•similar to the high-low game
•at each step, the number of candidate items is halved
•terminates after a logarithmic number of steps
•
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
1
3
4
5
7
8
9
11
14
16
18
19
0
0
0
0
m
l
h
m
l
h
m
l
h
l=m =h

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Lookup Table
•A lookup table is a dictionary implemented by means of a sorted sequence
•We store the items of the dictionary in an array-based sequence, sorted by key
•We use an external comparator for the keys
•findElement() O(logn)
•insertItem(k, o), removeElement O(n)
•The lookup table is effective only for dictionaries of small size or for dictionaries on which
searches are the most common operations, while insertions and removals are rarely performed (e.g.,
credit card authorizations)

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Binary Search Tree
•A binary search tree is a binary tree storing keys (or key-element pairs) at its internal nodes
and satisfying the following property:
•Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right
subtree of v. We have
key(u) £ key(v) £ key(w)
•External nodes do not store items
•An inorder traversal of a binary search
•trees visits the keys in increasing order
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Hash table
•A hash function h maps keys of a given type to integers in a fixed interval [0, N - 1]
•Example:
h(x) = x mod Nh(x) – hodnota hashe
•The goal of a hash function is to uniformly disperse keys in the range [0, N - 1]
•A hash table for a given key type consists of
•Hash function h
•Array (called table) of size N
•A collision occurs when two keys in the dictionary have the same hash value
•Collision handing schemes: Chaining, Open addressing
•