HashMap类的实现

package Hash;

import java.util.ConcurrentModificationException;
import java.util.NoSuchElementException;

import MyInterface.Iterator;
import MyInterface.Map;
import MyInterface.Set;

/**
 * HashMap的实现
 */
public class HashMap<K, V> implements Map<K, V> {

	// ----------------------------------------------------------------
	// 结点类
	private static class Entry<K, V> implements Map.Entry<K, V> {
		K key;
		V value;
		int hashValue;
		Entry<K, V> next;

		public Entry(K key, V value, int hashValue, Entry<K, V> next) {
			this.key = key;
			this.value = value;
			this.hashValue = hashValue;
			this.next = next;
		}

		public K getKey() {
			return key;
		}

		public V getValue() {
			return value;
		}

		public Entry<K, V> getNext() {
			return next;
		}

		public V setValue(V value) {
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		public String toString() {
			return key + "=" + value;
		}

	}

	// ----------------------------------------------------------------

	private Entry[] table;
	private int hashMapSize;
	private final double MAX_LOAD_FACTOR = 0.75;
	private int tableThreshold;
	private int modCount = 0;

	// HashMap类构造函数
	public HashMap() {
		table = new Entry[17];
		hashMapSize = 0;
		tableThreshold = (int) (table.length * MAX_LOAD_FACTOR);
	}

	public V put(K key, V value) {
		int hashValue = key.hashCode() & Integer.MAX_VALUE, index = hashValue
				% table.length;
		Entry<K, V> entry;
		entry = table[index];
		while (entry != null) {
			if (entry.key.equals(key))
				return entry.setValue(value);
			entry = entry.next;
		}
		modCount++;
		entry = new Entry<K, V>(key, value, hashValue,
				(Entry<K, V>) table[index]);
		table[index] = entry;
		hashMapSize++;
		if (hashMapSize >= tableThreshold)
			rehash(2 * table.length + 1);
		return null;
	}

	private void rehash(int newTableSize) {
		Entry[] newTable = new Entry[newTableSize], oldTable = table;
		Entry<K, V> entry, nextEntry;
		int index, len = table.length;

		for (int i = 0; i < len; i++) {
			entry = table[i];
			if (entry != null) {
				table[i] = null;
				do {
					nextEntry = entry.next;
					index = entry.hashValue % newTableSize;
					entry.next = newTable[index];
					newTable[index] = entry;
					entry = nextEntry;
				} while (entry != null);
			}
		}
		table = newTable;
		tableThreshold = (int) (table.length * MAX_LOAD_FACTOR);
		oldTable = null;
	}

	public V get(Object key) {
		Entry<K, V> p = this.getEntry(key);
		if (p == null)
			return null;
		return p.value;
	}

	public Entry<K, V> getEntry(Object key) {
		int index = (key.hashCode() & Integer.MAX_VALUE) % table.length;
		Entry<K, V> entry;

		entry = table[index];

		while (entry != null) {
			if (entry.key.equals(key))
				return entry;
			entry = entry.next;
		}
		return null;
	}

	public void clear() {
		for (int i = 0; i < table.length; i++)
			table[i] = null;
		modCount++;
		hashMapSize = 0;
	}

	public boolean containsKey(Object key) {
		return getEntry(key) != null;
	}

	public boolean isEmpty() {
		return hashMapSize == 0;
	}

	public V remove(Object key) {
		int index = (key.hashCode() & Integer.MAX_VALUE) % table.length;
		Entry<K, V> curr, prev;

		curr = table[index];
		prev = null;
		while (curr != null) {
			if (curr.key.equals(key)) {
				modCount++;
				if (prev != null)
					prev.next = curr.next;
				else
					table[index] = curr.next;
				hashMapSize--;
				return curr.value;
			} else {
				prev = curr;
				curr = curr.next;
			}
		}
		return null;
	}

	public int size() {
		return hashMapSize;
	}

	public String toString() {
		int max = hashMapSize - 1;
	      StringBuffer buf = new StringBuffer();
	      Iterator<Map.Entry<K,V>> iter = entrySet().iterator();

	      buf.append("{");
	      for (int j = 0; j <= max; j++) {
	         Map.Entry<K,V> e = iter.next();
	         buf.append(e.getKey() + "=" + e.getValue());
	         if (j < max)
	            buf.append(", ");
	      }
	      buf.append("}");

	      return buf.toString();
	}
	
	// ----------------------------------------------------------------
	// 视图
	
	private Set<K> keySet = null;
	private Set<Map.Entry<K,V>> entrySet = null;
	
	public Set<K> keySet() {
		if(keySet == null) {
			keySet = new Set<K>() {

				public boolean add(K item) {
					throw new UnsupportedOperationException();
				}

				public void clear() {
					HashMap.this.clear();
				}

				public boolean contains(Object item) {
					return containsKey(item);
				}

				public boolean isEmpty() {
					return HashMap.this.size() == 0;
				}

				public Iterator<K> iterator() {
					return new KeyIterator();
				}

				public boolean remove(Object item) {
					int oldSize = size();
					HashMap.this.remove(item);
		            return size() != oldSize;
				}

				public int size() {
					return HashMap.this.size();
				}

				public Object[] toArray() {
					Object[] arr = new Object[size()];
					Iterator<K> iter = iterator();
					int len = arr.length;
					for (int i=0;i < len;i++)
						arr[i] = iter.next();
					return arr;
				}
				
				public String toString() {
					int max = size() - 1;
					StringBuffer buf = new StringBuffer();
					Iterator<K> iter = iterator();
					buf.append("[");
					while (iter.hasNext())
					{
						buf.append(iter.next());
						if (iter.hasNext())
							buf.append(", ");
					}
					buf.append("]");
					return buf.toString();
				}
				
			};
		}
		return keySet;
	}
	
	public Set<Map.Entry<K, V>> entrySet() {
		if(entrySet == null) {
			entrySet = new Set<Map.Entry<K, V>>() {

				public boolean add(Map.Entry<K, V> item) {
					throw new UnsupportedOperationException();
				}

				public void clear() {
					HashMap.this.clear();
				}

				public boolean contains(Object item) {
					if (!(item instanceof Map.Entry))
						return false;

					Entry<K,V> entry = (Entry<K,V>)item;
					V value = entry.value;
					Entry<K,V> p = getEntry(entry.key);

					return p != null && p.getValue().equals(value);
				}

				public boolean isEmpty() {
					return size() == 0;
				}

				public Iterator<Map.Entry<K, V>> iterator() {
					return new EntryIterator();
				}

				public boolean remove(Object item) {
					 Entry<K,V> entry = (Entry<K,V>)item;
		             K key = entry.key;
		             return HashMap.this.remove(key) != null;
				}

				public int size() {
					return HashMap.this.size();
				}

				public Object[] toArray() {
					Object[] arr = new Object[size()];
					Iterator<Map.Entry<K,V>> iter = iterator();
					int len = arr.length;
					for (int i=0;i < len;i++)
						arr[i] = iter.next();
					return arr;
				}
				
				public String toString() {
					return HashMap.this.toString();
				}
				
			};
		}
		return entrySet;
	}

	// ----------------------------------------------------------------
	// 跌代器
	private class IteratorImpl<T> implements Iterator<T> {
		Entry<K, V> next;
		int expectedModCount;
		int index;
		Entry<K, V> lastReturned;

		IteratorImpl() {
			int i = 0;
			Entry<K, V> n = null;
			expectedModCount = modCount;

			if (hashMapSize != 0)
				while (i < table.length && ((n = table[i]) == null))
					i++;
			next = n;
			index = i;
			lastReturned = null;
		}

		final Entry<K, V> nextEntry() {
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();

			Entry<K, V> entry = next;

			if (entry == null)
				throw new NoSuchElementException();
			lastReturned = entry;
			Entry<K, V> n = entry.next;
			int i = index;

			if (n == null) {
				// we are at the end of a bucket. search for the
				// next non-empty bucket
				i++;
				while (i < table.length && (n = table[i]) == null)
					i++;
			}

			index = i;
			next = n;

			return lastReturned;
		}

		public boolean hasNext() {
			return next != null;
		}

		public T next() {
			return null;
		}

		public void remove() {
			// check for a missing call to next() or previous()
			if (lastReturned == null)
				throw new IllegalStateException("Iterator call to next() "
						+ "required before calling remove()");
			if (modCount != expectedModCount)
				throw new ConcurrentModificationException();

			// remove lastReturned by calling remove() in Hash.
			// this call will increment modCount
			HashMap.this.remove(lastReturned.key);
			expectedModCount = modCount;
			lastReturned = null;
		}

	}

	private class KeyIterator extends IteratorImpl<K> {
		public K next() {
			return nextEntry().key;
		}
	}

	private class EntryIterator extends IteratorImpl<Map.Entry<K, V>> {
		public Map.Entry<K, V> next() {
			return nextEntry();
		}
	}

}

测试类

package Hash;

import MyInterface.Iterator;
import MyInterface.Set;
import MyInterface.Map;
import MyInterface.Map.Entry;

public class TestHashMap {

	public static void main(String[] args) {
		HashMap<String, Integer> hm = new HashMap<String, Integer>();
		hm.put("Agg", new Integer(50));
		hm.put("Bf", new Integer(60));
		hm.put("Cf", new Integer(10));
		System.out.println(hm); 	// {Cf=10, Agg=50, Bf=60}
		
		// test keySet
		Set<String> kS = hm.keySet();
		Iterator<String> iter = kS.iterator();
		while(iter.hasNext())
			System.out.println(iter.next());
		System.out.println(kS);
		
		// test entrySet
		Set<Map.Entry<String, Integer>> eS = hm.entrySet();
		Iterator<Entry<String, Integer>> it = eS.iterator();
		Entry<String, Integer> e = null;
		while(it.hasNext()) {
			e = it.next();
			System.out.println(e.getValue() + "=" + e.getKey());
		}
		System.out.println(eS);
		
		// test remove
		hm.remove("Bf");
		System.out.println(hm); // {Cf=10, Agg=50}
		
		System.out.println(hm.size()); // 2
		System.out.println(hm.containsKey("Bf")); // false
		hm.clear();
		System.out.println(hm.isEmpty()); // true
	}

}