Liang Chapter 27 Modified HASHing Source Code

MyHashMap.java

package chapter27;

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 double DEFAULT_MAX_LOAD_FACTOR = 0.75;

	// Specify a load factor used in the hash table
	private double loadFactorThreshold;

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

	// Hash table is an array with each cell that is 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, double 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<K>();

		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 an 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 it is not 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 specified 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 static 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;
		}

		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<Entry<K, V>> set = entrySet(); // Get entries
		capacity <<= 1; // Double capacity
		table = new LinkedList[capacity]; // Create a new hash table
		size = 0; // Reset size to 0

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

	@Override
	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

package chapter27;

import java.util.*;

@SuppressWarnings("unchecked")
public class MyHashSet<E> implements Collection<E> {
	// 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 double DEFAULT_MAX_LOAD_FACTOR = 0.75;

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

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

	// Hash table is an array with each cell that is 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, double loadFactorThreshold) {
		if (initialCapacity > MAXIMUM_CAPACITY)
			this.capacity = MAXIMUM_CAPACITY;
		else
			this.capacity = trimToPowerOf2(initialCapacity);

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

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

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

	@Override /** Add an element to the set */
	public boolean add(E e) {
		if (contains(e)) // Duplicate element not stored
			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 it is not 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(Object e) {
		if (!contains(e))
			return false;

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

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

		size--; // Decrease size

		return true;
	}

	@Override /** Return true if the set contains no elements */
	public boolean isEmpty() {
		return size == 0;
	}

	@Override /** 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 */
	private class MyHashSetIterator implements Iterator<E> {
		// Store the elements in a list
		private ArrayList<E> list;
		private int current = 0; // Point to the current element in list

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

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

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

		@Override /** Remove the element returned by the last next() */
		public void remove() {
		}
	}

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

	/** Return a power of 2 for initialCapacity */
	private int trimToPowerOf2(int initialCapacity) {
		int capacity = 1;
		while (capacity < initialCapacity) {
			capacity <<= 1;
		}

		return capacity;
	}

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

	/** Rehash the set */
	private void rehash() {
		ArrayList<E> list = setToList(); // Copy to a list
		capacity <<= 1; // Double capacity
		table = new LinkedList[capacity]; // Create a new hash table
		size = 0; // Reset size

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

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

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

		return list;
	}

	@Override
	public String toString() {
		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();
	}

	@Override
	public boolean addAll(Collection<? extends E> arg0) {
		// Left as an exercise
		return false;
	}

	@Override
	public boolean containsAll(Collection<?> arg0) {
		// Left as an exercise
		return false;
	}

	@Override
	public boolean removeAll(Collection<?> arg0) {
		// Left as an exercise
		return false;
	}

	@Override
	public boolean retainAll(Collection<?> arg0) {
		// Left as an exercise
		return false;
	}

	@Override
	public Object[] toArray() {
		// Left as an exercise
		return null;
	}

	@Override
	public <T> T[] toArray(T[] arg0) {
		// Left as an exercise
		return null;
	}
}

MyMap.java

package chapter27;

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 first value that matches the specified key */
  public V get(K key);
  
  /** Return true if this map contains no 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 the entries for the specified key */
  public void remove(K key);

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

  /** Return a set consisting of the values in this map */
  public java.util.Set<V> values();
  
  /** Define inner class for Entry */
  public static 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 + "]";
    }
  }
}    

TestMyHashMap.java

package chapter27;

public class TestMyHashMap {
  public static void main(String[] args) {
    // Create a map
    MyMap<String, Integer> map = new MyHashMap<>();
    map.put("Smith", 30);
    map.put("Anderson", 31);
    map.put("Lewis", 29);
    map.put("Cook", 29);
    map.put("Smith", 65);

    System.out.println("Entries in map: " + map);

    System.out.println("The age for " + "Lewis is " +
      map.get("Lewis"));

    System.out.println("Is Smith in the map? " + 
      map.containsKey("Smith"));
    System.out.println("Is age 33 in the map? " + 
      map.containsValue(33));

    map.remove("Smith");
    System.out.println("Entries in map: " + map);

    map.clear();
    System.out.println("Entries in map: " + map);
  }
}

TestMyHashSet.java

package chapter27;

public class TestMyHashSet {
  public static void main(String[] args) {
    // Create a MyHashSet
    java.util.Collection<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.print("Names in set in uppercase are ");
    for (String s: set)
      System.out.print(s.toUpperCase() + " ");

    set.clear();
    System.out.println("\nElements in set: " + set);
  }
}