(Compare MyHashSet and MyArrayList) MyArrayList is defined in Listing 24.3. Write a program that generates 1000000 random double values between 0 and 999999 and stores them in a MyArrayList and in a MyHashSet

/*********************************************************************************
* (Compare MyHashSet and MyArrayList) MyArrayList is defined in Listing 24.3.    *
* Write a program that generates 1000000 random double values between 0 and      *
* 999999 and stores them in a MyArrayList and in a MyHashSet. Generate a list of *
* 1000000 random double values between 0 and 999999. For each number in the     *
* list, test if it is in the array list and in the hash set. Run your program to *
* display the total test time for the array list and for the hash set.           *
*********************************************************************************/
public class Exercise_27_10 {
	static final int VALUES = 1000000;

	public static void main(String[] args) {
		MySet<Double> set = new MyHashSet<>(); // Create a MyHashSet
		MyList<Double> arrayList = new MyArrayList<>(); // Create a MyArrayList

		// Generate 1000000 random double values between 0 and 999999
		for (int i = 0; i < VALUES; i++) {
			double randomDouble = Math.random() * VALUES;
			set.add(randomDouble);
			arrayList.add(randomDouble);
		}
		
		// Create a list
		double[] list = new double[VALUES];
		for (int i = 0; i < list.length; i++) {
			list[i] = Math.random() * VALUES;
		}

		System.out.println("Total time for the hash set: " +
			testTimeSet(list, set) + " milliseconds");

		System.out.println("Total time for the array list: " +
			testTimeArray(list, arrayList) + " milliseconds");
	}

	/** Return total test time for the hash set */
	public static long testTimeSet(double[] list, MySet<Double> set) {
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < VALUES; i++) {
			set.contains(list[i]);
		}
		return System.currentTimeMillis() - startTime;
	}

	/** Return total test time for the array list */
	public static long testTimeArray(double[] list, MyList<Double> array) {
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < VALUES; i++) {
			array.contains(list[i]);
		}
		return System.currentTimeMillis() - startTime;
	}
}

MyAbstractList.java

public abstract class MyAbstractList<E> implements MyList<E> {
	protected int size = 0; // The size of the list

	/** Create a default list */
	protected MyAbstractList() {
	}

	/** Create a list from an array of objects */
	protected MyAbstractList(E[] objects) {
		for (int i = 0; i < objects.length; i++) 
			add(objects[i]);
	}

	@Override /** Add a new element at the end of this list */
	public void add(E e) {
		add(size, e);
	}

	@Override /** Return true if this list doen't contain any elements */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** Return the number of elements in this list */
	public int size() {
		return size;
	}

	@Override /** Remove the first occurence of the element e
		* from this list. Shift any subsequent elements to the left.
		* Return true if the element is removed. */
	public boolean remove(E e) {
		if (indexOf(e) >= 0) {
			remove(indexOf(e));
			return true;
		}
		else
			return false;
	}
}

MyArrayList.java

public class MyArrayList<E> extends MyAbstractList<E> {
	public static final int INITIAL_CAPACITY = 16;
	private E[] data = (E[]) new Object[INITIAL_CAPACITY];

	/** Create a default list */
	public MyArrayList() {
	}

	/** Create a list from an array of objects */
	public MyArrayList(E[] objects) {
		for (int i = 0; i < objects.length; i++)
			add(objects[i]);
	}

	@Override /** Add a new element at the specified index */
	public void add(int index, E e) {
		ensureCapacity();

		// Move the elements to the right after the speciied index
		for (int i = size - 1; i >= index; i--)
			data[i + 1] = data[i];

		// Insert new element to data[index]
		data[index] = e;

		// Increase size by 1
		size++;
	}

	/** Create a new larger array, double the current size + 1 */
	private void ensureCapacity() {
		if (size >= data.length) {
			E[] newData = (E[])(new Object[size * 2 + 1]);
			System.arraycopy(data, 0, newData, 0, size);
			data = newData;
		}
	}

	@Override /** Clear the list */
	public void clear() {
		data = (E[])new Object[INITIAL_CAPACITY];
		size = 0;
	}

	@Override /** Return true if this list contains the element */
	public boolean contains(E e) {
		for (int i = 0; i < size; i++)
			if (e.equals(data[i])) return true;

		return false;
	}

	@Override /** Return the element at the specified index */
	public E get(int index) {
		checkIndex(index);
		return data[index];
	}

	private void checkIndex(int index) {
		if (index < 0 || index >= size)
			throw new IndexOutOfBoundsException("index" + index + " out of bounds");
	}

	@Override /** Return the index of the first matching element
				  *	in this list. Return -1 if no match. */
	public int indexOf(E e) {
		for (int i = 0; i < size; i++)
			if (e.equals(data[i])) return i;

		return -1;
	}

	@Override /** Return the index of the last matching element
	 *	in this list. Return -1 if no match. */
	public int lastIndexOf(E e) {
		for (int i = size - 1; i >= 0; i--)
			if (e.equals(data[i])) return i;

		return -1;
	}

	@Override /** Remove the element at the specified position
		*	in this list. Shift any subsequent elements to the left.
		*	Return the element that was removed from the list. */
	public E remove(int index) {
		checkIndex(index);

		E e = data[index];

		// Shift data to the left
		for (int j = index; j < size - 1; j++)
			data[j] = data[j + 1];

		data[size - 1] = null; // This element is now null

		// Decrement size
		size--;

		return e;
	}

	@Override /** Replace the element at the specified position
		*	in this list with the specified element. */
	public E set(int index, E e) {
		checkIndex(index);
		E old = data[index];
		data[index] = e;
		return old;
	}

	@Override 
	public String toString() {
		StringBuilder result = new StringBuilder("[");

		for (int i = 0; i < size; i++) {
			result.append(data[i]);
			if (i < size - 1) result.append(", ");
		}

		return result.toString() + "]";
	}

	/** Trims the capacity to current size */
	public void trimToSize() {
		if (size != data.length) {
			E[] newData = (E[])(new Object[size]);
			System.arraycopy(data, 0, newData, 0, size);
			data = newData;
		} // If size == capacity, no need to trim
	}

	@Override /** Override iterator() defined in Iterable */
	public java.util.Iterator<E> iterator() {
		return new ArrayListIterator();
	}

	private class ArrayListIterator
			implements java.util.Iterator<E> {
		private int current = 0; // Current index

		@Override
		public boolean hasNext() {
			return (current < size);
		}

		@Override
		public E next() {
			return data[current++];
		}

		@Override
		public void remove() {
			MyArrayList.this.remove(current);
		}
	}
}

MyHashSet.java 

import java.util.LinkedList;

public class MyHashSet<E> implements MySet<E> {
	// Define the default hash-table size. Must be power of 2
	private static int DEFAULT_INITIAL_CAPACITY = 4;

	// Define the maximum hash-table size. 1 << 30 is same as 2^30
	private static int MAXIMUM_CAPACITY = 1 << 30;

	// Current hash-table capacity. Capacity is a power of 2
	private int capacity;

	// Define default load factor
	private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;

	// Specify a load-factor threshold used in the hash table
	private float loadFactorThreshold; 

	// The number of elements in the set
	private int size = 0;

	// Hash table is an array with each cell being a linked list
	private LinkedList<E>[] table;

	/** Construct a set with the default capacity and load factor */
	public MyHashSet() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
	}

	/** Construct a set with the specified initial capacity and 
	 * default load factor */
	public MyHashSet(int initialCapacity) {
		this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
	}

	/** Construct a set with the specified initial capacity
	 * and load factor */
	public MyHashSet(int initialCapacity, float loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY) 
			this.capacity = MAXIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

		this.loadFactorThreshold = loadFactorThreshold;
		table = new LinkedList[capacity];
	}

	/** Remove all elements from this set */
	public void clear() {
		size = 0;
		removeEntries();
	}

	/** Return true if the element is in the set */
	public boolean contains(E e) {
		int bucketIndex = hash(e.hashCode());
		if (table[bucketIndex] != null) {
			LinkedList<E> bucket = table[bucketIndex];
			for (E element : bucket) 
				if (element.equals(e)) 
					return true;
		}

		return false;
	}

	/** Add an element to the set */
	public boolean add(E e) {
		if (contains(e)) // Duplicate element not sotred
			return false;

		if (size + 1 > capacity * loadFactorThreshold) {
			if (capacity >= MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");

			rehash();
		}

		int bucketIndex = hash(e.hashCode());

		// Create a linked list for the bucket if not already created
		if (table[bucketIndex] == null) {
			table[bucketIndex] = new LinkedList<E>();
		}

		// Add e to hashTable[index]
		table[bucketIndex].add(e);

		size++; // Increase size

		return true;
	}

	@Override /** Remove the element from the set */
	public boolean remove(E e) {
		if (!contains(e))
			return false;

		int bucketIndex = hash(e.hashCode());

		// Create a linked list for the bucket if not alredy created
		if (table[bucketIndex] != null) {
			LinkedList<E> bucket = table[bucketIndex];
			for (E element : bucket) {
				if (element.equals(e)) {
					bucket.remove(e);
					break;
				}
			}
		}

		size--; // Decrease size
		return true;
	}

	/** Return true if the set doesn't contain any elements */
	public boolean isEmpty() {
		return size == 0;
	}

	/** Return the number of elements in the set */
	public int size() {
		return size;
	}

	@Override /** Return an iterator for the elements in this set */
	public java.util.Iterator<E> iterator() {
		return new MyHashSetIterator(this);
	}

	/** Inner class for iterator */
	public class MyHashSetIterator implements java.util.Iterator<E> {
		// Store the elements in a list
		private java.util.ArrayList<E> list;
		private int current = 0; // Point to the current element in list
		private MyHashSet<E> set;

		/** Create a list from the set*/
		public MyHashSetIterator(MyHashSet<E> set) {
			this.set = set;
			list = setToList();
		}

		@Override /** Next element for traversing? */
		public boolean hasNext() {
			if (current < list.size())
				return true;

			return false;
		}

		@Override /** Get current element and move cursor to the next */
		public E next() {
			return list.get(current++);
		}

		/** Remove the current element and refresh the list */
		public void remove() {
			// Delete the current element from the hash set
			set.remove(list.get(current));
			list.remove(current); // Remove current element from the list
		}
	}

	/** Hash function */
	private int hash(int hashCode) {
		return supplementalHash(hashCode) & (capacity - 1);
	}

	/** Ensure the hashing is evenly distributed */
	private int supplementalHash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1; // Same as capacity *= 2. <= is more efficient 
		}

		return capacity;
	}

	/** Remove all e from each bucket */
	private void removeEntries() {
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				table[i].clear();
			}
		}
	}

	/** Rehash the set */
	private void rehash() {
		java.util.ArrayList<E> list = setToList(); // Copy to a list;
		capacity <<= 1; // Same as capacity *= 2. <= is more efficient
		table = new LinkedList[capacity]; // Create a new hash table
		size = 0;

		for (E element: list) {
			add(element); // Add from the old table to the new table
		}
	}

	/** Copy elements in the hash set to an arry list */
	private java.util.ArrayList<E> setToList() {
		java.util.ArrayList<E> list = new java.util.ArrayList<>();

		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				for (E e : table[i]) {
					list.add(e);
				}
			}
		}

		return list;
	}

	/** Return a string representation for this set */
	public String toString() {
		java.util.ArrayList<E> list = setToList();
		StringBuilder builder = new StringBuilder("[");

		// Add the elements except the last one to the string builder
		for (int i = 0; i < list.size() - 1; i++) {
			builder.append(list.get(i) + ", ");
		}

		// Add the last element in the list to the string builder
		if (list.size() == 0) 
			builder.append("]");
		else
			builder.append(list.get(list.size() - 1) + "]");

		return builder.toString();
	}
}

MyList.java 

public interface MyList<E> extends java.lang.Iterable<E> {
	/** Add a new element at the end of this list */
	public void add(E e);

	/** Add a new element at the specified index in this list */
	public void add(int index, E e);

	/** Clear the list */
	public void clear();

	/** Return true if list contains the element */
	public boolean contains(E e);

	/** Return the element from the list at the specified index */
	public E get(int index);

	/** Return the index of the first matching element in this list.
	 *	 Return -1 if no match. */
	public int indexOf(E e);

	/** Return true if this list doesn't contain any elements */
	public boolean isEmpty();
	
	/** Return the index of the last matching element in this list
	 *  Return -1 if no match. */
	public int lastIndexOf(E e);

	/** Remove the first occurence of the element e from this list.
	 *  Shift any subsequent elements to the left.
	 *  Return true if the element is removed. */
	public boolean remove(E e);

	/** Remove the element at the specified position in this list.
	 *  Shift any subsequent elements to the left.
	 *  Return the element that was removed from the list. */
	public E remove(int index);

	/** Replace the element at the specified position in this list
	 *  with the specified element and return the old element. */
	public Object set(int index, E e);

	/** Return the number of elements in this list */
	public int size();
}

MySet.java

public interface MySet<E> extends java.lang.Iterable<E> {
	/** Remove all elements from this set */
	public void clear(); 

	/** Return true if the element is in the set */
	public boolean contains(E e);

	/** Add an element to the set */
	public boolean add(E e) ;

	/** Remove the element from the set*/
	public boolean remove(E e);

	/** Return true if the set doesn't contain any elements */
	public boolean isEmpty();

	/** Return the number of elements in the set */
	public int size();
}