Tutorial
COMP20007 Design of Algorithms
Week 10 Workshop Solutions
1. Separate chaining Here’s the hash table after inserting the keys according to the hash function h(k)=k modLwithL=2:
0 6→12→8
1 17→11→21→33→5→23→1→9
In terms of better data structures over a standard linked list, there are plenty of options to try.
• A move-to-front (MTF) list could adapt to access patterns to provide better average performance
• An array (possibly also with MTF) could save on space for all those next pointers, and could and also yield better cache performance*.
• A balanced search tree could ensure O(log n) lookups in the worse case even if the hash function distributes keys unevenly.
However, before reaching for more complicated data structures as a cure for poor hashing per- formance, it might be better to try increasing the table size and/or improving the hash function.
*Cache performance is related to how nicely your algorithm behaves in its memory access patterns. It’s a matter of practical concern as it has a real impact on algorithm performance. With a MTF linked list, memory accesses might be distant from one another as we follow pointers to wildly different parts of memory. In contrast, the elements of an array are contiguous, so subsequent accesses are likely to be in nearby areas of memory.
Cache performance is not really a concern in this subject, but it’s definitely something to be aware of. 2. Open addressing Here’s the hash table after inserting the keys according to the hash function
h(k)=k modLwithL=8:
01234567 17 33 11 12 18 9 7
If we repeat using i = 2, we can insert the first 6 keys without much trouble, but then we can’t find a place for 9:
01234567 17 18 11 12 33 7 9? 9? 9? 9?
The problem is that i = 2 and L = 8 have a common factor other than 1 (it’s 2), in maths terms, they are not coprime. So, it’s possible for the key 9 to fall into a loop of steps that doesn’t actually encounter every cell. As a result, we can’t insert 9, even though there are still empty buckets in the hash table.
We can avoid this problem if we make sure i and L have no common factors other than 1. Appropriate choicesinclude: Lapowerof2andiodd,orLprimeandi