Chapter 16, Problem 14PP

Program Plan Intro

To implement a hash table with open addressing

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 method “getBucketsSize()” to get the length of the bucket.
  • 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,
        • • Check the condition,
            • If it is true, returns true.
          • Check whether the bucket value contains null,
            • If it is true, 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,
        • • 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,
        • • 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,
        • • Check whether the current bucket value contains null,
            • If it is true, assign the current value.
          • Otherwise, check the condition,
            • If it is true, assign the current value to last found.
        • Check whether the end sequence is “-1”,
        • • If it is true, use conditional operator to find the end sequence.
        • Check the whether the last found is “-1”,
        • • Assign the value to position.
          • Assign the null value to last found.
          • Decrement the current size.
          • Create a loop,
            • Check whether the bucket is not full,
              • Decrement the size.
              • Assign the value.
              • Assign the null value to the bucket.
              • Call the method “add()”.
        • Otherwise,
        • • Assign null value to current bucket position.
          • Decrement the size.
        • Returns true.
  • Define the method “iterator ()” to return an iterator that traverse the set elements,
    • Return the object of “HashSetIterator()”.
  • Define the method “size()” to return the size.
  • Define the method “resizeTable()”,
    • Create an object.
    • Make a copy of bucket.
    • Assign the temporary value.
    • Set the current size to “0”.
    • Create a loop,
      • Check the condition, and if it is true, call the method “add()”.
  • 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 “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 “Cassendra” into the set.
    • Print the set and expected output.
    • Remove the name “John” from the set.
    • Print the set and expected output.