Liang Chapter 27 Modified HASHing Source Code
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(); | |
} | |
} |
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; | |
} | |
} |
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 + "]"; | |
} | |
} | |
} |
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); | |
} | |
} |
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); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment