20.HashMap添加，查找，删除，迭代练习

package com.example.test4;import java.util.ArrayList;import java.util.Iterator;/** *  * HashMap添加，查找，删除，迭代练习 *  * 存在问题： *  * 1.entryList()函数中，将表中元素转为添加到list集合变量i应该<table.length(桶的总个数) *   而不是size(已使用桶的个数) *    * 2.在扩容函数中，计算当前节点在新的HashMap中桶对应的Id应该是： *   int newBucketId = node.getKey().hashCode() % newCapacity; *   而不是： *   int newBucketId = node.hashCode() % newCapacity; */interface Map<K, V>{		interface Entry<K, V>{		K getKey();		V getValue();	}		V put(K key, V value);	V get(K key);	ArrayList<Map.Entry<K, V>> entryList();	int getBucket();	void remove(K key);	}class HashMap<K, V> implements Map<K, V>{		static class Entry<K, V> implements Map.Entry<K, V>{				K key;		V value;		Entry<K, V> next;				public Entry(K key, V value){			this.key = key;			this.value = value;			this.next = null;		}		@Override		public K getKey() {			// TODO Auto-generated method stub			return this.key;		}		@Override		public V getValue() {			// TODO Auto-generated method stub			return this.value;		}			}		Entry<K, V>[] table;	int size;			/**	 * 	 * @param initCapacity  	 * 	 * HashMap的初始容量，表示桶的个数	 * 	 * size表示已使用桶的个数	 */	public HashMap(int initCapacity){		if (initCapacity < 0){			throw new IllegalArgumentException("Illegal initial capacity: " + initCapacity);		}				table = new Entry[initCapacity];		size = 0;	}		/**	 * 	 * 向HashMap中添加元素	 * 	 * 1.key的哈希码对桶的长度求模，得到桶的Id	 * 	 * 2.若该位置桶的引用为空，直接将元素添到该位置，并通过桶的总个数以及已经使用桶的个数	 *   之比是否大于0.75来判断该HashMap是否需要扩容	 *   	 * 3.引用不为空时，判断是否key相同的元素，若存在，直接替换value至当前value，并返回oldValue	 *   不存在，使用头插法将新元素以链表的形式插入该桶的后面	 */	@Override	public V put(K key, V value) {		// TODO Auto-generated method stub		int bucketId = key.hashCode() % table.length;				if (table[bucketId] == null){			table[bucketId] = new Entry<K, V>(key, value);			size++;			if (((double)size)/table.length > 0.75){				resize(2 * table.length);			}		}		else{			Entry<K, V> node = table[bucketId];						for (; node != null; node = node.next){				if (node.getKey().equals(key)){					V oldValue = node.getValue();					node.value = value;					return oldValue;				}			}						node = new Entry<K, V>(key, value);			node.next = table[bucketId].next;			table[bucketId] = node;		}		return null;	}	/**	 * 	 * 从HashMap中得到对应key的value	 * 	 * 1.使用key的哈希码对桶的长度长度求模，得到对应Id号的桶	 * 2.该桶为空，直接返回	 * 3.若不为空，按照链表的形式从table[bucketId]位置开始遍历	 */	@Override	public V get(K key) {		// TODO Auto-generated method stub		int bucketId = key.hashCode() % table.length;				if (table[bucketId] == null){			return null;		}				Entry<K, V> node = table[bucketId];				for (; node != null; node = node.next){			if (node.getKey().equals(key)){				return node.getValue();			}		}		return null;	}	/**	 * 将HashMap中的元素添加到List集合当中便于迭代，遍历	 */	@Override	public ArrayList<com.example.test4.Map.Entry<K, V>> entryList() {		// TODO Auto-generated method stub				ArrayList<com.example.test4.Map.Entry<K, V>> list = 				new ArrayList<com.example.test4.Map.Entry<K, V>>();				for (int i = 0; i < table.length; i++){			Entry<K, V> node = table[i];			for (; node != null; node = node.next){				list.add(node);			}		}				return list;	}	@Override	public int getBucket() {		// TODO Auto-generated method stub		return table.length;	}	/**	 * 从HashMap中删除关键字为key的元素	 */	@Override	public void remove(K key) {		// TODO Auto-generated method stub		int bucketId = key.hashCode() % table.length;				if (table[bucketId] == null){			return;		}		if (table[bucketId].getKey().equals(key)){			table[bucketId] = table[bucketId].next;			return;		}				Entry<K, V> PRev = table[bucketId];		Entry<K, V> cur = table[bucketId].next;				for (; cur != null; cur = cur.next){			if (cur.key.equals(key)){				prev.next = cur.next;				return;			}			prev = cur;		}	}		/**	 * 	 * @param newCapacity  对HashMap扩容时桶的新的个数	 * 	 * 对每一个id对应链表进行遍历是因为之前元素对应桶的Id在新表中桶的Id会有所改变	 */	public void resize(int newCapacity){				//应用扩容前的Entry数组		Entry<K, V>[] oldTable = table;				//初始化一个容量为之前2倍的Entry数组		Entry<K, V>[] newTable = new Entry[newCapacity];				for (int i = 0; i < oldTable.length; i++){			Entry<K, V> node = oldTable[i];						if (node != null){								//释放之前Entry数组的引用				oldTable[i] = null;								do{					Entry<K, V> nextNode = node.next;										//得到该元素在扩容之后的HashMap中桶的Id值					int newBucketId = node.getKey().hashCode() % newCapacity;										//使用头插法将该元素插入到桶Id为newBucketId位置的链表上					if (newTable[newBucketId] == null){						newTable[newBucketId] = node;					}					else{						node.next = newTable[newBucketId].next;						newTable[newBucketId].next = node;					}										node = nextNode;								}while(node != null);			}		}				table = newTable;	}	}public class TestDemo {	public static void main(String[] args) {		// TODO Auto-generated method stub		Map<Integer, String> map = new HashMap<Integer, String>(10);				System.out.println("桶的数量：" + map.getBucket());		map.put(1, "aaa");		map.put(2, "bbb");		map.put(3, "ccc");		map.put(4, "ddd");		map.put(5, "eee");		map.put(6, "fff");		map.put(7, "ggg");		map.put(8, "hhh");		map.put(9, "iii");		map.put(10, "jjj");		map.put(11, "kkk");				Iterator<Map.Entry<Integer, String>> it = map.entryList().iterator();		while (it.hasNext()){			Map.Entry<Integer, String> entry = it.next();			System.out.println(entry.getKey() + ":" + entry.getValue());		}				System.out.println("桶的数量：" + map.getBucket());	}}