Q:

(Implement MyHashSet using MyHashMap) Implement MyHashSet using MyHashMap. Note that you can create entries with (key, key), rather than (key, value)

Asmaa
Save to bookmark
|
2022-07-01
|
  125 
0

(Implement MyHashSet using MyHashMap) Implement MyHashSet using MyHashMap. Note that you can create entries with (key, key), rather than (key, value).

Java programming, textbook solutions, Java programming textbook-solutions,
login and add your own answer to this question

All Answers

Asmaa
2022-07-01
need an explanation for this answer? contact us directly to get an explanation for this answer 

/*********************************************************************************
* (Implement MyHashSet using MyHashMap) Implement MyHashSet using MyHashMap.     *
* Note that you can create entries with (key, key), rather than (key, value).    *
*********************************************************************************/
public class Exercise_27_05 {
	public static void main(String[] args) {
		// Create a MyHashSet
		MySet<String> set = new MyHashSet<>();
		set.add("Smith");
		set.add("Anderson");
		set.add("Lewis");
		set.add("Cook");
		set.add("Smith");

		System.out.println("Elements in set: " + set);
		System.out.println("Number of elements in set: " + set.size());
		System.out.println("Is Smith in set? " + set.contains("Smith"));

		set.remove("Smith");
		System.out.println("Names in set in uppercase are ");
		for (String s: set)
			System.out.print(s.toUpperCase() + " ");
			
		set.clear();
		System.out.println("\nElements in set: " + set);
	}
}

MyHashMap.java

import java.util.LinkedList;

public class MyHashMap<K, V> implements MyMap<K, V> {
	// Define the default hash-table size. Must be a 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 used in the hash table
	private float loadFactorThreshold;

	// The number of entries in the map
	private int size = 0;

	// Hash table is an array with each cell being a linked list
	LinkedList<MyMap.Entry<K, V>>[] table;

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

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

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

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

	@Override /** Remove all of the entries from this map */
	public void clear() {
		size = 0;
		removeEntries();
	}

	@Override /** Return true if the specified key is in the map */
	public boolean containsKey(K key) {
		if (get(key) != null) 
			return true;
		else
			return false;
	}

	@Override /** Return true if this map contains the value */
	public boolean containsValue(V value) {
		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				LinkedList<Entry<K, V>> bucket = table[i];
				for (Entry<K, V> entry : bucket)
					if (entry.getValue().equals(value))
						return true;
			}
		}

		return false;
	}

	@Override /** Return a set of entries in the map */
	public java.util.Set<MyMap.Entry<K, V>> entrySet() {
		java.util.Set<MyMap.Entry<K, V>> set = 
			new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				LinkedList<Entry<K, V>> bucket = table[i];
				for (Entry<K, V> entry: bucket)
					set.add(entry);
			}
		}

		return set;
	}

	@Override /** Return the value that matches the specified key */
	public V get(K key) {
		int bucketIndex = hash(key.hashCode());
		if (table[bucketIndex] != null) {
			LinkedList<Entry<K, V>> bucket = table[bucketIndex];
			for (Entry<K, V> entry: bucket)
				if (entry.getKey().equals(key))
					return entry.getValue();
		}

		return null;
	} 

	@Override /** Return true if this map contains no entries */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** Return a set consisting of the keys in this map */
	public java.util.Set<K> keySet() {
		java.util.Set<K> set = new java.util.HashSet<>();

		for (int i = 0; i < capacity; i++) {
			if (table[i] != null) {
				LinkedList<Entry<K, V>> bucket = table[i];
				for (Entry<K, V> entry : bucket) {
					set.add(entry.getKey());
				}
			}
		}

		return set;
	}

	@Override /** Add and entry (key, value) into the map */
	public V put(K key, V value) {
		if (get(key) != null) { // The key is already in the map
			int bucketIndex = hash(key.hashCode());
			LinkedList<Entry<K, V>> bucket = table[bucketIndex];
			for (Entry<K, V> entry: bucket)
				if (entry.getKey().equals(key)) {
					V oldValue = entry.getValue();
					// Replace old value with new value
					entry.value = value;
					// Return the old value for the key
					return oldValue;
				} 
		}

		// Check load factor
		if (size >= capacity * loadFactorThreshold) {
			if (capacity == MAXIMUM_CAPACITY)
				throw new RuntimeException("Exceeding maximum capacity");

			rehash();
		}

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

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

		// Add a new entry (key, value) to hashtable[index]
		table[bucketIndex].add(new MyMap.Entry<K, V>(key, value));

		size++; // Increase size

		return value;
 	}

 	@Override /** Remove the entries for the specifie key */
 	public void remove(K key) {
 		int bucketIndex = hash(key.hashCode());

 		// Remove the first entry that matches the key from a bucket
 		if (table[bucketIndex] != null) {
 			LinkedList<Entry<K, V>> bucket = table[bucketIndex];
 			for (Entry<K, V> entry: bucket)
 				if (entry.getKey().equals(key)) {
 					bucket.remove(entry);
 					size--; // Decrease size
 					break; // Remove just one entry that matches the key
 				}
 		}
 	}

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

 	@Override /** Return a set consisting of the values in this map */
 	public java.util.Set<V> values() {
 		java.util.Set<V> set = new java.util.HashSet<>();

 		for (int i = 0; i < capacity; i++) {
 			if (table[i] != null) {
 				LinkedList<Entry<K, V>> bucket = table[i];
 				for (Entry<K, V> entry : bucket) {
 					set.add(entry.getValue());
 				}
 			}
 		}

 		return set;
 	}

 	/** 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 entries from each bucket */
 	private void removeEntries() {
 		for (int i = 0; i < capacity; i++) {
 			if (table[i] != null) {
 				table[i].clear();
 			}
 		}
 	}

 	/** Rehash the map */
 	private void rehash() {
 		java.util.Set<MyMap.Entry<K, V>> set = entrySet(); // Get entries
 		capacity <<= 1; // Same as capacity *= 2. <= is more efficient
 		table = new LinkedList[capacity]; // Crate a new hash table
 		size = 0;

 		for (Entry<K, V> entry : set) {
 			put(entry.getKey(), entry.getValue()); // Store to new table
 		}
 	}

 	@Override /** Return a string representation for this map */
 	public String toString() {
 		StringBuilder builder = new StringBuilder("[");
 		for (int i = 0; i < capacity; i++) {
 			if (table[i] != null && table[i].size() > 0)
 				for (Entry<K, V> entry : table[i]) {
 					builder.append(entry);
 				}
 		}

 		builder.append("]");
 		return builder.toString();
 	}
}

MyHashSet.java

public class MyHashSet<E> implements MySet<E> {
	MyMap<E, E> map;

	public MyHashSet() {
		map = new MyHashMap<>();
	}

	public MyHashSet(int initialCapacity) {
		map = new MyHashMap(initialCapacity);
	}

	public MyHashSet(int initialCapacity, float loadFactorThreshold) {
		map = new MyHashMap(initialCapacity, loadFactorThreshold);
	}

	@Override /** Remove all elements in this set */
	public void clear() {
		map.clear();
	}

	@Override /** Return true if element is in set */
	public boolean contains(E e) {
		return map.containsKey(e) && map.containsValue(e);
	}

	@Override /** Add and element to the set */
	public E add(E e){
		E element = map.put(e, e);
		return element;
	}

	@Override /** Remove the element from the set */
	public boolean remove(E e) {
		if (!map.containsKey(e))
			return false;
		
		map.remove(e);
		return true;
	}

	@Override /** Return true if the set doesn't contain any elements */
	public boolean isEmpty() {
		return map.isEmpty();
	}

	@Override /** Return the number of elements in the set */
	public int size() {
		return map.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 */
	private 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 an 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 form the hash set
			set.remove(list.get(current));
			list.remove(current); // Remove current element from the list
		}
	}

	/** 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<>();
		java.util.Set<E> set = map.keySet();

		for (E e: set) {
			list.add(e);
		}

		return list;
	}

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

		for (int i = 0; i < list.size() - 1; i++) {
			builder.append(list.get(i) + ", ");
		}

		if (list.size() == 0)
			builder.append("]");
		else
			builder.append(list.get(list.size() - 1) + "]");
		return builder.toString();
	} 
}

MyMap.java

public interface MyMap<K, V> {
	/** Remove all of the entries from this map */
	public void clear();

	/** Return true if the specified key is in the map */
	public boolean containsKey(K key);

	/** Return true if this map contains the specified value */
	public boolean containsValue(V value);

	/** Return a set of entries in the map */
	public java.util.Set<Entry<K, V>> entrySet();

	/** Return the value that matches the specified key */
	public V get(K key);

	/** Return true if this map doesn't contain any entries */
	public boolean isEmpty();

	/** Return a set consisting of the keys in this map */
	public java.util.Set<K> keySet();

	/** Add an entry (key, value) into the map */
	public V put(K key, V value);

	/** Remove entry for the specified key */
	public void remove(K key);

	/** Return the number of mappings in the map */
	public int size();

	/** Return a set consisting of the values in this map */
	public java.util.Set<V> values();

	/** Define an inner class for Entry */
	public class Entry<K, V> {
		K key;
		V value;

		public Entry(K key, V value) {
			this.key = key;
			this.value = value;
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		@Override
		public String toString() {
			return "[" + key + ", " + value + "]";
		}
	}
}

MySet.java 

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

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

	/** Add an element to the set */
	public E 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();
}

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Similar questions

need a help?

find thousands of online teachers now