Chapter 18, Problem 9PE

Program Plan Intro

HashSet

Program plan:

Filename: “HashSet.java”

This code snippet creates a class “HashSet”. In the code,

• Import the required packages.
• Define a class “HashSet”.
  • Declare an array list “buckets”.
  • Define an integer “size”.
  • Define the constructor “HashSet()”.
    • Define the array list “buckets”.
    • Iterate a “for” loop,
      • Add “null” to the “bucket”.
    • Set “size” equal to “0”.
  • Define a method “contains”.
    • Define a variable “h” by calling “hashCode()” using “x”.
    • If the value of “h” is less than 0,
      • Set “h” equal to “-h”.
    • Find the reminder of “h” and size of the “buckets”.
    • Create a node “current” by getting element from “bucket”.
    • Iterate a “while” loop,
      • If the “data” part of node “current” is not equal to “x”.
        • Return “true”.
        • • Set “current” equal to link of “current”.
    • Return the value “false”.
  • Define the method “add()”.
    • Define a variable “h” by calling “hashCode()” using “x”.
    • If the value of “h” is less than 0,
      • Set “h” equal to “-h”.
    • Find the reminder of “h” and size of the “buckets”.
    • Create a node “current” by getting element from “bucket”.
    • Iterate a “while” loop,
      • If the “data” part of node “current” is not equal to “x”.
        • Return “true”.
        • • Set “current” equal to link of “current”.
    • Return the value “false”.
    • Create a new node “newNode”.
    • Set “data” of “newNode” equal to “x”.
    • Set “next” of “newNode” equal to element at “h” of “bucket”.
    • Set “newNode” at position “h” of the bucket.
    • Increment the “size” by 1.
    • Return “true”.
  • Define the method “remove()”.
    • Define a variable “h” by calling “hashCode()” using “x”.
    • If the value of “h” is less than 0,
      • Set “h” equal to “-h”.
    • Find the reminder of “h” and size of the “buckets”.
    • Create a node “previous”.
    • Create a node “current” by getting element from “bucket”.
    • Iterate a “while” loop,
      • If the “data” part of node “current” is not equal to “x”.
        • If “previous” equal to “null”,
        • • Set “next” of “current” to “h”.
        • Else,
        • • Set the “next” of “current” to “next” of “previous”.
        • Decrement “size” by 1.
        • Return “true”.
        • • • Set “previous” equal to “current”.
            • Set “current.next” to “current”.
    • Return “false”.
  • Define the method “Iterator”.
    • Create new “HashSetIterator” and return the value.
  • Define the method “size()”.
    • Return “size”.
  • Define a class “Node”.
    • Create a variable “data” of type “E”.
    • Create a variable “next”.
  • Define a class “HashSetIterator”.
    • Declare the class members.
    • Define the constructor “HashSetIterator()”.
      • Set the values of class members.
    • Define a method “hasNext()”.
      • If “current” and “current.next” are not equal to null,
        • Return true.
        • • • Iterate a “for” loop,
              • If element at “b” of “buckets” is not equal to “null”,
                • Return “true”.
            • Return “false”.
    • Define a method “next()” with return type “E”.
      • Set “previous” equal to “current”.
      • Set “previousBucket” equal to “bucket”.
      • If “current” and “current.next” are not equal to null,
        • Increment “bucket” by 1.
        • Iterate a “while” loop,
        • • Increment “bucket” by 1.
            • • If “bucket” less than size of the “bucket”.
                • Set the value of “current”.
              • Else,
                • Throw an exception
            • Else,
              • Set “current” equal to “current.next”.
            • Return “data” of “current”.
    • Define a method “remove()”.
      • If “previous” and “previous.next” are not equal to null,
        • Set “previous.next” equal to “current.next”.
        • • • If “previousBucket” is less than “bucket”,
              • Set “bucket” equal to “current.next”.
            • Else,
              • Throw an exception.
            • Set “current” equal to “previous”.
            • Set “bucket” equal to “previousBucket”.

Filename: “HashSetDemo.java”

This code snippet creates a class “HashSetDemo”. In the code,

• Import the required packages.
• Define a class “HashSetDemo”.
  • Define the “main” method.
  • Define a “HashSet” “names”.
  • Add values to “names” using “add()”.
  • Create an “Iterator” named “iter”.
  • Iterate a “while” loop,
    • Print values of “names”.