31251 Lecture Notes - Lecture 8: Abstract Data Type, Associative Array, Quadratic Probing
30 Jun 2018
School
Department
Course
Professor
Simple hash-maps (linear and quadratic probing, division hash function)
Maps
Also called: associative array, symbol table, dictionary.
An abstract data type that stores pairs.
The key is unique (in theory at least).
The value can of course be more complex than a single value.
The key is the index for the entry value – so we can treat a map like an array.
Basic Map Operations
add(key,value) – insert a new element value into the map accessed by key.
get(key) – retrieve the element indexed by key.
remove(key,value) – delete the given pair from the map.
Implementation of Maps
Depending on the exact circumstances, a number of strategies may be useful:
If the key set is already small valued, positive integers, we could just use an array as
the implementation.
If there a small number of total entries, a linked list would be sufficient – O(n) to do
anything, but there’s not much there.
If the keys are totally ordered, we can extend binary search trees (or similar, more
sophisticated data structures).
We mostly want a more general approach – one method is to use hashing.
Hash Functions
At their most general, hash functions (or hashes) are functions that take input of arbitrary
length and produce an output of fixed length.
If the output length is k bits, we can interpret the output as an integer in [0, 2 k ).
So, we can use this as a way of turning our key set into normal array indices.
Thus, an associative array can be implemented as an array plus a hash function.
Division Hash Function
Array of size N.
h(K) = K mod N.
If N = 20 and K = 36, then h(K) = 16
This would send the item with key 36 to array cell 16.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Simple hash-maps (linear and quadratic probing, division hash function) The key is unique (in theory at least). The value can of course be more complex than a single value. The key is the index for the entry value so we can treat a map like an array. Basic map operations add(key,value) insert a new element value into the map accessed by key. get(key) retrieve the element indexed by key. remove(key,value) delete the given pair from the map. Depending on the exact circumstances, a number of strategies may be useful: If the key set is already small valued, positive integers, we could just use an array as the implementation. If there a small number of total entries, a linked list would be sufficient o(n) to do anything, but there"s not much there. If the keys are totally ordered, we can extend binary search trees (or similar, more sophisticated data structures).
