Reading material

pages 284-287 and 313-319.

Additional material

Implementation of a dictionary with a hash table in PostScript and PDF
Implementation of a set with an array in PostScript and PDF

HashTableDictionary.java

Worst-case running time of the array-based implementation of a set where the elements in the array are ordered (unordered) and where the array contains (no) duplicates:
ord. unord. ord. unord.
no dupl. dupl. dupl. no dupl.
size O(1) O(1) O(1) O(1)
isEmpty O(1) O(1) O(1) O(1)
isMember O(log(n)) O(N) O(log(N)) O(n)
elements O(n) O(N2) O(N) O(n)
insertElement O(n) O(1) O(N) O(n)
union O(n+m) O(N*M) O(N*M) O(n*m)
where n is the size of the set, m is the size of the set to be added, N is the number of elements stored in the array implementing the set and M is the number of elements stored in the array implementing the set to be added.

Note: elements for an unordered array with duplicates takes O(N2) as we have to remove the duplicates.
Note: union for an array with duplicates takes O(N*M) because we have to recompute the size of the set.