Chapter 16, Problem 15PP

Program Plan Intro

To implement a hash table with quadratic probing

Program plan:

• In a file “HashSet.java”, import necessary package, and create a class “HashSet”,
  • Declare the array of “Object” type.
  • Declare the necessary variable.
  • Define the constructor to create a hash table.
    • Create an array and set the current size to “0”.
  • Define the method “toString()” that returns the string representation of array.
  • Define the method “contains()”,
    • Assign the hash code.
    • Check the condition,
      • If it is true, returns true.
        • Create a loop,
        • • Compute the probe.
          • Check the condition,
            • If it is true, returns true.
          • Check whether the bucket value contains null,
            • If it is true, returns false.
        • Returns false.
  • Define the method “getHashCode()”,
    • Assign the hash code.
    • Check whether the value is less than “0”,
      • If it is true, assign the negative value.
        • Update the hash value.
        • Return the hash code.
  • Define the method “add()”
    • Check whether there is a room before probing,
      • If it is true, call the method “resizeTable()()”.
        • Assign the hash code returned from the method “getHashCode()”.
        • Check whether the has value is a null,
        • • If it is true, assign the object properties.
        • Otherwise, execute a loop,
        • • Compute the quadratic probe.
          • Check whether the bucket contains null value,
            • If it is true, assign the object properties.
            • Use break statement.
          • Otherwise, Check the condition,
            • Returns false.
        • Increment the current size.
        • Returns true.
  • Define the method “remove()” to remove the object from the set,
    • Get the hash code.
    • Set the position to “-1”.
    • Check the condition,
      • If it is true, assign the hash code to position.
        • Create a loop,
        • • Compute the probe.
          • Check the condition, set the new position.
        • Check whether the position value is “-1”,
        • • If it is true, returns false.
        • If the item found, find the last item in the rest of the probing sequence.
        • Create a loop,
        • • Compute the probe.
          • Check whether the current bucket value contains null,
            • If it is true, use break.
          • Otherwise, check the condition,
            • If it is true, assign the current value to as last index.
        • Check whether the last sequence is “-1”,
        • • If it is true, assign the null value and decrement the size.
        • Otherwise, assign the last index value to the current position.
        • Assign null value to last index.
        • Create a loop to rehash the table,
        • • Check the condition,
            • Continue to skip nulls.
          • Assign the current bucket value to object.
          • Assign null value to bucket.
          • Decrement current size.
          • Call the method “add()”.
        • Returns true.
  • Create a class “HashSetIterator”,
    • Declare the variable to denote bucket index.
    • Define the constructor that create a hash set iterator that points to the first element of the hash set.
    • Define the method “hasNext ()”,
      • Create a loop,
        • Check the condition,
        • • Returns true.
      • Returns false.
  • Define the method “size()” to return the size.
  • Define the method “next ()”,
    • Execute the statement without checking the condition,
      • Increment the index.
      • Check the condition,
        • If it is true, create an object for “NoSuchElementException”.
    • Check whether the current bucket value contains null,
    • Return the value.
  • Define the method “remove()”,
    • Throw an exception “UnsupportedOperationException”.
• In a file “HashSetTest.java”, create a class “HashSetTest”,
  • Define the method “main()”,
    • Create an object for “HashSet”.
    • Add the name “James” into the set.
    • Add the name “David” into the set.
    • Add the name “John” into the set.
    • Add the name “Kean” into the set.
    • Add the name “Juliet” into the set.
    • Add the name “Lilly” into the set.
    • Print the object properties.
    • Print the expected output.
    • Initialize the array.
    • Iterate over the names,
      • Print the actual and expected output.
    • Remove the name “John” from the set.
    • Print the set and expected output.