Chapter 16, Problem 18PE

Program Plan Intro

Implementation of hash set

Program plan:

• In a file “HashSet.java”, import necessary package, and create a class “HashSet”,
  • Declare the array of “Node” 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 “contains()”,
    • Assign the hash code.
    • Check whether the value is less than “0”,
      • If it is true, assign the negative value.
    • Update the hash value.
    • Assign the current node value.
    • Execute loop till array becomes null,
      • Check the condition,
        • Return true.
        • • Assign the current value.
  • Define the method “add()” to add the element to the set,
    • Get the hash code.
    • Check whether the value is less than “0”,
      • If it is true, assign the negative value.
    • Update the hash code.
    • Assign the hash code value to the current node.
    • Execute a loop,
      • Check the condition,
        • Return false.
        • • Assign the next value to the value in the current node.
    • Create a new node.
    • Assign the value to new node value.
    • Assign the value to the next node.
    • Assign the new node value to the bucket.
    • Increment the size.
    • Compute the load factor.
    • Check whether the load factor is greater than “1.0”,
      • If it is true, call the method “growBuffer()”.
    • Return true.
  • Define the method “remove()” to remove the object from the set,
    • Get the hash code.
    • Check whether the value is less than “0”,
      • If it is true, assign the negative value.
    • Update the hash code.
    • Assign the hash code value to the current node.
    • Set null to the previous node.
    • Execute a loop,
      • Check the condition,
        • Check whether the previous node contains null value,
        • • If it is true, assign the next node value to the bucket.
        • Otherwise,
        • • Assign the next of the current node value to the next of the previous node value.
        • Decrement the size.
        • Compute the load factor.
        • Check whether the load factor is less than “0.5”,
        • • If it is true, call the method “shrinkBuffer()”.
        • Return true.
        • • • Assign the current node value to the previous node value.
            • Assign the next of the current node value to the current node.
    • Return false.
  • Define the method “growBuffer()”,
    • Create an array and get the current data.
    • Initialize the value.
    • Create an iterator.
    • Execute a loop,
      • Assign the next element.
      • Increment the size.
    • Initialize the current size to “0”.
    • Add the data into the new array.
    • Create a loop,
      • Call the method “add()”.
  • Define the method “shrinkBuffer()”,
    • Create an array and get the current data.
    • Initialize the value.
    • Create an iterator.
    • Execute a loop,
      • Assign the next element.
      • Increment the size.
    • Initialize the current size to “0”.
    • Add the data into the new array of half size.
    • Create a loop,
      • Call the method “add()”.
  • 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 of the set.
  • Create a class “Node”,
    • Declare the object for “Object”.
    • Declare the object of “Node”.
  • Create a class “HashSetIterator”,
    • Declare the necessary variables.
    • Define the constructor to create a hash set that point to the first element of the hash set.
    • Define the method “hasNext()”,
      • Check whether the current node and the next of the current node is not null,
        • If it is true, returns true.
      • Execute a loop,
        • Check whether the bucket contains not null value,
          • If it is true, returns true.
      • Returns false.
    • Define the method “next()”,
      • Check the condition,
        • Assign the next node value to the current node value.
      • Otherwise,
        • Execute the following statement,
          • Increment the index.
          • Check the condition,
            • Throw an exception “NoSuchElementException”.
          • Assign the value.
        • Check the condition.
      • Return the current node value.
• Define the method “remove()”,
  • Throw an exception “UnsupportedOperationException”.
• In a file “HashSetTest.java”, import necessary package, and create a class “HashSetTest”,
  • Define the “main()” method,
    • Create an object fro “HashSet”.
    • Add the element “David” to the set.
    • Add the element “Jerry” to the set.
    • Add the element “Cassendra” to the set.
    • Add the element “Jim” to the set.
    • Add the element “Jack” to the set.
    • Print the actual and expected output.
    • Add the element “Nick” to the set.
    • Print the actual and expected output.
    • Add the element “Johny” to the set.
    • Add the element “Andrew” to the set.
    • Add the element “Francis” to the set.
    • Add the element “Jackson” to the set.
    • Print the actual and expected output.
    • Add the element “Jimmy” to the set.
    • Print the actual and expected output.
    • Remove the element “Jackson” from the set.
    • Print the actual and expected output.
    • Remove the element “Jerry” from the set.
    • Print the actual and expected output.
    • Remove the element “Johny” from the set.
    • Remove the element “Jimmy” from the set.
    • Remove the element “Francis” from the set.
    • Remove the element “Nick” from the set.
    • Print the actual and expected output.
    • Remove the element “David” from the set.
    • Print the actual and expected output.