G2A Many GEOs
SHARE
TWEET

Untitled

a guest Apr 2nd, 2020 2,381 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.Iterator;
  3. import java.util.List;
  4.  
  5. /**
  6.  * The MyHashSet API is similar to the Java Set interface. This
  7.  * collection is backed by a hash table.
  8.  */
  9. public class MyHashSet<E> implements Iterable<E> {
  10.  
  11.     /**
  12.      * Unless otherwise specified, the table will start as
  13.      * an array (ArrayList) of this size.
  14.      */
  15.     private final static int DEFAULT_INITIAL_CAPACITY = 4;
  16.  
  17.     /**
  18.      * When the ratio of size/capacity exceeds this
  19.      * value, the table will be expanded.
  20.      */
  21.     private final static double MAX_LOAD_FACTOR = 0.75;
  22.  
  23.     /* STUDENTS: LEAVE THIS AS PUBLIC */
  24.     public ArrayList<Node<E>> hashTable;
  25.  
  26.     private int size;  // number of elements in the table
  27.  
  28.  
  29.     // STUDENTS: DO NOT ADD ANY OTHER INSTANCE VARIABLES OR STATIC
  30.     // VARIABLES TO THIS CLASS!
  31.  
  32.  
  33.     /* STUDENTS: LEAVE THIS PUBLIC, and do not modify the Node class. */
  34.     public static class Node<T> {
  35.         private T data;
  36.         public Node<T> next;  // STUDENTS: Leave this public, too!
  37.  
  38.         private Node(T data) {
  39.             this.data = data;
  40.             next = null;
  41.         }
  42.  
  43.     }
  44.  
  45.     /**
  46.      * Initializes an empty table with the specified capacity.
  47.      *
  48.      * @param initialCapacity initial capacity (length) of the
  49.      *                        underlying table
  50.      */
  51.     // STUDENTS: Calling the ArrayList constructor that takes
  52.     // an int argument doesn't do what we want here.
  53.     // You need to make an empty ArrayList, and then add a bunch
  54.     // of null values to it until the size reaches the
  55.     // initialCapacity requested.
  56.     public MyHashSet(int initialCapacity) {
  57.         hashTable = new ArrayList<Node<E>>();
  58.         for (int i = 0; i < initialCapacity; i++) {
  59.             hashTable.add(null);
  60.         }
  61.     }
  62.  
  63.  
  64.     /**
  65.      * Initializes an empty table of length equal to
  66.      * DEFAULT_INITIAL_CAPACITY
  67.      */
  68.     // STUDENTS:  This constructor should just call the other
  69.     // constructor
  70.     public MyHashSet() {
  71.         this(DEFAULT_INITIAL_CAPACITY);
  72.     }
  73.  
  74.     /**
  75.      * Returns the number of elements stored in the table.
  76.      *
  77.      * @return number of elements in the table
  78.      */
  79.     public int size() {
  80.         return size;
  81.     }
  82.  
  83.     /**
  84.      * Returns the length of the table (the number of buckets).
  85.      *
  86.      * @return length of the table (capacity)
  87.      */
  88.     public int getCapacity() {
  89.         return hashTable.size();
  90.     }
  91.  
  92.     /**
  93.      * Looks for the specified element in the table.
  94.      *
  95.      * @param element to be found
  96.      * @return true if the element is in the table, false otherwise
  97.      */
  98.     public boolean contains(Object element) {
  99.         int index = Math.abs(element.hashCode() % hashTable.size());
  100.         Node<E> indexNode = hashTable.get(index);
  101.  
  102.         if (indexNode != null && indexNode.data.equals(element)) return true;
  103.  
  104.         Iterator<E> iterator = iterator();
  105.         while (iterator.hasNext()) {
  106.               Object o = iterator.next();
  107.               if (o instanceof Node) {
  108.                   Node<E> n = (Node<E>) o;
  109.                   while (n.next != null){
  110.                       if (n.data.equals(element)) return true;
  111.                   }
  112.               }
  113.         }
  114.  
  115.         return false;
  116.     }
  117.  
  118.     /**
  119.      * Adds the specified element to the collection, if it is not
  120.      * already present.  If the element is already in the collection,
  121.      * then this method does nothing.
  122.      *
  123.      * @param element the element to be added to the collection
  124.      */
  125.     // STUDENTS:  After adding the element to the table, consider
  126.     // the load factor. If it is greater than MAX_LOAD_FACTOR then
  127.     // you must double the size of the table. [Create a new table
  128.     // that is twice as big as the current one and then re-hash
  129.     // of all of the data from the old table into the new one.
  130.     // Hint: It's OK to iterate over the original table.]
  131.     public void add(E element) {
  132.         if (contains(element)) return;
  133.  
  134.         rehash();
  135.  
  136.         int index = getHash(element) % hashTable.size();
  137.  
  138.         Node<E> n = hashTable.get(index);
  139.  
  140.         Node<E> newNode = new Node<>(element);
  141.  
  142.         if (n == null) {
  143.             hashTable.set(index, newNode);
  144.             size++;
  145.             return;
  146.         }
  147.  
  148.         while (n.next != null) {
  149.             if (n.data.equals(element)) {
  150.                 return;
  151.             }
  152.             n = n.next;
  153.         }
  154.  
  155.         // add only if last element doesn't have the value being added
  156.         if (!n.data.equals(element)) {
  157.             n.next = newNode;
  158.             size++;
  159.         }
  160.     }
  161.  
  162.     private void rehash() {
  163.         if (size == 0.75 * getCapacity()) {
  164.             // rehash
  165.             ArrayList<Node<E>> gList = new ArrayList<>();
  166.             for (int i = 0; i < getCapacity() * 2; i++) {
  167.                 gList.add(null);
  168.             }
  169.             hashTable = gList;
  170.  
  171.             for (Node<E> bucket : hashTable) {
  172.                 while (bucket != null) {
  173.                     hashTable.add(bucket);
  174.                     bucket = bucket.next;
  175.                 }
  176.             }
  177.         }
  178.     }
  179.  
  180.     /**
  181.      * Removes the specified element from the collection.  If the
  182.      * element is not present then this method should do nothing.
  183.      *
  184.      * @param element the element to be removed
  185.      */
  186.     public boolean remove(E element) {
  187.         // mapping hash code to the index
  188.         int index = getHash(element) % hashTable.size();
  189.  
  190.         Node<E> indexNode = hashTable.get(index);
  191.  
  192.         if (indexNode == null) return false;
  193.  
  194.         if (indexNode.data.equals(element)) {
  195.             hashTable.set(index, indexNode.next); // if there is such an element, "removing" it by replacing with the following
  196.             size--;
  197.             return true;
  198.         }
  199.  
  200.         Node<E> previous = indexNode;
  201.  
  202.         while (indexNode != null) {
  203.             if (indexNode.data.equals(element)) {
  204.                 previous.next = indexNode.next;
  205.                 size--;
  206.                 return true;
  207.             }
  208.             previous = indexNode;
  209.             indexNode = previous.next;
  210.         }
  211.  
  212.         return true;
  213.     }
  214.  
  215.     private int getHash(Object o){
  216.         return Math.abs(o.hashCode());
  217.     }
  218.  
  219.     /**
  220.      * Returns an Iterator that can be used to iterate over
  221.      * all of the elements in the collection.
  222.      * <p>
  223.      * The order of the elements is unspecified.
  224.      */
  225.     // STUDENTS: You may NOT copy the data from the hash table
  226.     // into a different structure.  You must write an iterator
  227.     // that iterates over your hash table directly, without
  228.     // copying the data anywhere.
  229.     @Override
  230.     public Iterator<E> iterator() {
  231.         return new Iterator<E>() {
  232.             int index = 0;
  233.  
  234.             @Override
  235.             public boolean hasNext() {
  236.                 return (hashTable.size() > index) && hashTable.get(index) != null;
  237.             }
  238.  
  239.             @Override
  240.             public E next() {
  241.                 Node<E> node = hashTable.get(index++);
  242.                 return node == null ? null : node.data;
  243.             }
  244.         };
  245.     }
  246. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top