Chapter 16, Problem 21PE

Program Plan Intro

Implementation of hash set

Program plan:

• In a file “HashSet.java”, import necessary packages, and create a class “HashSet”,
  • Declare the array of “Node” type.
  • Declare the necessary variables.
  • Define the constructor to create a hash table.
    • Create an array and set the current size to “0”.
    • Compute the value for “p”.
    • Execute a loop,
      • Increment the value of “p”.
    • Set the value for “a”, and “b”.
  • Define the method “isPrime()” to test whether the value passed is prime or not.,
  • Define the method “contains()”,
    • Assign the hash code.
    • Check whether the value is less than “0”,
      • If it is true, compute the absolute value of hash code.
    • Update the hash value.
    • Assign the bucket value to the current node.
    • Execute loop till array becomes null,
      • Check the condition,
        • Return true.
        • • Assign the current value.
    • Returns false.
  • 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 bucket value at the hash code to the current node.
    • Check whether the current node is not null value,
      • If it is true,  set the collision value to “1”
    • Execute a loop,
      • Check the condition,
        • Returns “0”.
        • • Assign the next value to 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.
    • Return collision value.
  • 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.
        • 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 “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” that implements an interface “Iterator”,
    • 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,
            • Throws an exception “NoSuchElementException”.
          • Assign the value.
        • Check the condition at the end of the loop.
      • Return the current node value.
    • Define the method “remove()”,
      • Throw an exception “UnsupportedOperationException”.
• In a file “HashSetFromBook.java”, import necessary packages, and create a class “HashSetFromBook”,
  • Declare the array of “Node” type.
  • Declare the necessary variables.
  • Define the constructor to create a hash table.
    • Create an array and set the current size to “0”.
  • Define the method “isPrime()” to test whether the value passed is prime or not.,
  • 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 bucket value to the current node.
    • Execute loop till array becomes null,
      • Check the condition,
        • Return true.
        • • • Assign the current value.
    • Returns false.
  • Define the method “add()” to add the element to the set,
    • Declare and initialize the variable.
    • Get the hash code.
    • Check whether the value is less than “0”,
      • If it is true, compute the absolute value of hash code.
    • Update the hash code.
    • Assign the bucket value at the hash code to the current node.
    • Check whether the current node is not null value,
      • If it is true,  set the collision value to “1”
    • Execute a loop,
      • Check the condition whether the element is already in the set,
        • Returns “0”.
        • • • Assign the next value to 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.
    • Return collision value.
  • 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.
              • 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 “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” that implements an interface “Iterator”,
    • 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,
            • Throws an exception “NoSuchElementException”.
          • Assign the value.
        • Check the condition at the end of the loop.
      • Return the current node value.
    • Define the method “remove()”,
      • Throw an exception “UnsupportedOperationException”.
• In a file “HashSetTest.java”, import necessary packages, and create a class “HashSetTest”,
  • Define the “main()” method,
    • Declare and initialize the necessary variables.
    • Create an object for “HashSet”.
    • Create an object for “HashSetFromBook”.
    • Execute “try” statement,
      • Execute a loop,
        • Get the string.
        • Update the necessary values.
    • Catch if the exception occurs,
      • Print the message.
    • Print the output.

Explanation of Solution

“Yes”, the multiply-add-divide (MAD) method decreases the collisions.

Explanation:

• The hash function is defined as follows,

  $\text{Hash}\left(\text{x}\right)\text{ = }(\text{a * x + b}$