1NF - Use Components


We'll now normalize (simplify) the design in the usual way.

Provided Starting Point
Notes:
  • The buckets sub-component must have fast indexed access
  • Each bucket is a very small collection/list that does not need fast indexed access
  • The elements in each bucket are Association objects where each Association holds a key and value.

More details here...
HashTable
  |
  +------- buckets ------- an Array
  |
  +------- maxLoadRatio -- an integer
Sub-Component 'buckets'
The sub-component "buckets" is defined as a plain array.

Let's change that to a DynamicArray, which is easier to work with.
HashTable
  |
  +------- buckets ------- DynamicArray
  |
  +------- maxLoadRatio -- an integer


Bucket
A bucket is defined as:

  • Each bucket is a very small collection/list that does not need fast indexed access

This sounds like a LinkedList -- that way we won't need a new type "Bucket". A DynamicArray would also be acceptable.
Association
An Association type is designed for us.
HashTable Methods
The HashTable required instance methods are specified by the Dictionary ADT.

All the hash table methods perform with Big-O efficiency O(1) except the "keys" method.
Design
HashTable
  |
  +------- buckets ------- DynamicArray
  |
  +------- maxLoadRatio -- an integer
Notes:
  • Each bucket is LinkedList
  • The elements in each bucket are Association objects where each Association holds a key and value.
  • The HashTable required instance methods are specified by the Dictionary ADT


2NF - Generalize Components


All the component types (DynamicArray, LinkedList and Association) were selected for specific reasons.

Thus no changes needed for this step -- generalization is not needed.

3NF - Use Inheritance


The two new types HashTable and Association are very different types -- they do not have any common components or behaviors that should be moved to a super-type.

Thus no changes needed for this step -- inheritance is not needed.

Thus the design in 1NF above is normalized (simplified) as much as practical.