HashMap和HashSet深度解析

package container;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;

/**
 * @author [e-mail]
 *  
 *  测试HashSet中，通过equals方法检测到重复之后会发生什么。
 *  以及测试hashCode函数生成的散列码相同之后，会不会被去掉。
 *
 */
class TestObject{
	int x;
	int y;
	public TestObject(int x, int y){
		this.x = x;
		this.y = y;
	}
	
	/* 一般重写equals方法的同时也会重写hasCode方法，为什么? */
	public int hashCode(){
		return x;
	}
	
	/* 注意参数是Object类型，否则就不是覆盖了 */
	public boolean equals(Object obj) {
		TestObject oo = (TestObject)obj;
		return (this.x == oo.x)?true:false;
	}
}

public class HashSetTest {

	public static void main(String args[]){
		/**
		 * 重写了Object的equals方法，只要两个对象x字段相等，
		 * 那么两个对象就相等。(默认的equals方法是比较引用==)
		 * （注意： 引用仍然不同，即不是指向同一个对象）
		 */
		TestObject o1 = new TestObject(1,3);
		TestObject o2 = new TestObject(3,3);
		System.out.println(o1.equals(o2));
		System.out.println(o1 == o2);
		
		/**
		 *  HashMap，采用数组散列存储，散列值有hashCode返回，
		 *  同一个hashCode的对象，采用链接法解决冲突。通过equals判断是否冲突。
		 *  下面是HashMap内部的put方法的实现。
		 * 	public V put(K key, V value) {
		        if (key == null)
		            return putForNullKey(value);
		        int hash = hash(key.hashCode()); 		//生成hash值
		        int i = indexFor(hash, table.length);	//找到该hash值在数组中位置索引
		       
		        //循环该hash槽的所有对象
		        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
		            Object k;
		            //如果equals()方法返回true,发现“重复”
		            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
		                V oldValue = e.value;
		                e.value = value; 	//将新的值替换原来的值，键不动
		                e.recordAccess(this);
		                return oldValue;
		            }
		        }

		        modCount++;
		        addEntry(hash, key, value, i);
		        return null;
    		}
		 * */	
		HashMap<TestObject,String> map = new HashMap<TestObject,String>();
		//键hashCode相同，且equals返回true，故替换值，可以看到键没有变化
		map.put(new TestObject(1,0), "XXX");	
		map.put(new TestObject(1,2), "YYY");
		System.out.println("MAP SIZE:"+map.size());
		for(Entry<TestObject,String> e: map.entrySet()){
			System.out.println(e.getKey().x+","+e.getKey().y+","+e.getValue());
		}
		
		/**
		 *  HashSet通过HashMap实现，键就是插入的对象，而值统一是一个static的Object
		 *  下面是add方法的实现。
		 * 	public boolean add(E e) {
				return map.put(e, PRESENT)==null;
    		}
		 * */
		HashSet<TestObject> set = new HashSet<TestObject>();
		set.add(new TestObject(1,2));
		//hashCode方法和equals方法都返回相同值,所以替换值，但是它的值部分只是一个static的Object
		set.add(new TestObject(1,1));
		set.add(new TestObject(3,1));
		set.add(new TestObject(3,4));
		
		System.out.println("SET SIZE:"+set.size());
		for(TestObject o: set){
			System.out.println(o.x+","+o.y);
		}
		
		/*
		 * 注意，HashCode返回的值决定了你的存在散列表中的Entry对象应该在哪个槽位
		 * 设想如果你的equals方法重写了，认为两个对象相等，但是hashCode返回的两个对象
		 * 的值却不一样，那么他们都不可能在一个槽位，所以equals方法就没意义。
		 * 
		 * 所以我们重写键对象的equals方法的时候，一般同时重写hashCode方法。
		 * 尽量保证： 
		 * (1)当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()必须为true
		 * (2)当obj1.hashCode() == obj2.hashCode()为false时，obj1.equals(obj2)必须为false
		 */
		
		/**
		 * 拓展： 如果吧TestObject的equals方法改成return (this.y == oo.y)?true:false;
		 * 那么	set.add(new TestObject(1,2));
				set.add(new TestObject(1,1));
				set.add(new TestObject(3,1));
				会发生什么？输出set大小是多少？答案是3
		 * 	因为前两个对象虽然hashCode相同，但是equals返回false，故不是冲突的对象
		 *  后两个虽然equals返回了true，但是不是存在同一个槽位的对象，故也不是冲突对象。
		 * */
	}
}

输出：

false
false
MAP SIZE:1
1,0,YYY
SET SIZE:2
1,2
3,1