java 散列与散列码探讨 ,简单HashMap实现散列映射表执行各种操作示列

package org.rui.collection2.maps;
/**
 * 散列与散列码
 * 将土拔鼠对象与预报对象联系起来，
 * @author lenovo
 *
 */
//土拨鼠
public class Groundhog {
	protected int number;
	public Groundhog(int n)
	{
		number=n;
	}
	@Override
	public String toString() {
		return "Groundhog #" + number;
	}
}

package org.rui.collection2.maps;

import java.util.Random;

//预测
public class Prediction {
	private static Random rand=new Random(47);
	private boolean shadow=rand.nextDouble()>0.5;
	
	@Override
	public String toString() {
		if(shadow)
			return "六周后是冬天";//六个周的冬天six more weeks of winter
		else
			return "早春";//早春Early spring!
	}
}

package org.rui.collection2.maps;

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.HashMap;
import java.util.Map;
/**
 * 散列与散列码
 * 将土拔鼠对象与预报对象联系起来，
 * 每个Groundhog被 予一个标识 数字，于是可以在hasmmap中这样查找Prediction：
 * 给我与Groundhog #3相关的prediction
 * prediction类包含一个boolean 和toString 
 * 布尔 值用random来初始化；而Tostring方法则解释结果。 
 * detecSpring方法使用反射机制来实例化例用Groundhog类或任何从GroundHog派生出来的类.
 * 
 * @author lenovo
 *
 */
public class SpringDetector {
	//发现
	public static <T extends Groundhog> void detectSpring(Class<T> type) throws Exception
	{
		Constructor<T> ghog=type.getConstructor(int.class);
		Map<Groundhog, Prediction> map=new HashMap<Groundhog, Prediction>();
		
		//初始化map
		for(int i=0;i<10;i++)
		{
			map.put(ghog.newInstance(i), new Prediction());
		}
		System.out.println("map:="+map);
		
		//生成一个number=3的士拔鼠
		Groundhog gh=ghog.newInstance(3);
		//查找预测
		System.out.println("looking up prediction for:"+gh);
		
		//在初始化中的map中查找 
		if(map.containsKey(gh))
			System.out.println(map.get(gh));
		else
			System.out.println("key not found "+gh);
		//看起来很简单，但是他不工作，无法找到  需要实现hacode 和equals 下章讲解
	}

	public static void main(String[] args) throws Exception {
		detectSpring(Groundhog.class);
	}
}
/**output:
map:={Groundhog #5=早春, Groundhog #7=早春, Groundhog #8=六周后是冬天, Groundhog #0=六周后是冬天, Groundhog #9=六周后是冬天, Groundhog #2=早春, Groundhog #1=六周后是冬天, Groundhog #4=六周后是冬天, Groundhog #3=早春, Groundhog #6=早春}
looking up prediction for:Groundhog #3
key not found Groundhog #3
*/

package org.rui.collection2.maps;
/**
 * 如果要使用自已的类作为HashMap的健，必须同时重载hashCode和equlas
 * 示列
 * @author lenovo
 *
 */
//土拨鼠2
public class Groundhog2 extends Groundhog{
	//public int number;
	public Groundhog2(int n){ super(n);	}
	@Override
	public int hashCode() {
		return number;
	}
	@Override
	public boolean equals(Object obj) {
	 return obj instanceof Groundhog2 && 
			 (number==((Groundhog2)obj).number);
	}

	

}

package org.rui.collection2.maps;
/**
 * Groundhog2.hashCode返回Groundhog的标识数字（编号）作为散列码。
 * 在此例中，程序员负责确保不同的groundhog具有不同的编号。hashCode并不需要总是能够返回唯一的标识 码
 * 但equals必须严格判断对象是否相同
 * @author lenovo
 *
 */		
public class SpringDetector2 {
	public static void main(String[] args) throws Exception {
		SpringDetector.detectSpring(Groundhog2.class);
	}

}
/**
map:={Groundhog #0=六周后是冬天, Groundhog #1=六周后是冬天, Groundhog #2=早春, Groundhog #3=早春, Groundhog #4=六周后是冬天, Groundhog #5=早春, Groundhog #6=早春, Groundhog #7=早春, Groundhog #8=六周后是冬天, Groundhog #9=六周后是冬天}
looking up prediction for:Groundhog #3
早春
*/

package org.rui.collection2.maps;

import java.util.*;

/**
 * 理解hashCode 
 * 使用散列的目地在于 :你要使用一个对象来查找另一个对象.
 *  不过使用TreeMap或者你自已实现的Map也可以达到此目地 下面的示例用
 * 一对ArrayList实现了一个Map
 * 
 * @author lenovo
 * 
 */
public class SlowMap<K, V> extends AbstractMap<K, V> {
	private List<K> keys = new ArrayList<K>();
	private List<V> values = new ArrayList<V>();

	public V put(K key, V value) {
		V oldValue = http://www.mamicode.com/get(key);>
package org.rui.collection2.maps;

import java.util.Map;

/**
 * 想要创建自已的map类型，就必须同时定义Map.Entry的实现
 * 
 * @author lenovo
 * 
 */
public class MapEntry<K, V> implements Map.Entry<K, V> {

	private K key;
	private V value;

	public MapEntry(K key, V value) {
		this.key = key;
		this.value = http://www.mamicode.com/value;>
package org.rui.collection2.maps;

import java.util.AbstractMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

/**
 * 为速度而散列
 * 
 * 散列的价值在于速度，解决方案之一就是保持健的排序状态，然后使用Collections.binarySearch()查询
 * 数组并不保存健本身。而是通过健对象生成一个数字，将其作为数组的下标。这个数字就是散列码，
 * 注意：这个 实现并不意味着对性能进行了调化，它只是想要展示散列映射表执行的各种操作，
 * @author lenovo
 *
 */
public class SimpleHashMap<K,V> extends AbstractMap<K, V> {

	
	static final int SIZE=997;
	//你不可能拥有一个物理geerics数组
	//you can't have a physical array of geerics
	//but you can upcast to one 但是你可以向上抛
	LinkedList<MapEntry<K,V>>[] buckets=new LinkedList[SIZE];//bucket桶  位
	/***
	 * 对于put方法 hasCode将针对健而被调用，并且其结果被强制转换为正数。
	 * 为了使产生的数字适合bucket数组的大小  取模操作符将按照该数组的尺寸取模，
	 * 如果数组的某个位置是null,这表示还没有元素被散列至此，所以，为了保存刚散列到该定位的对象
	 * 需要创建一个新的LinkedList
	 * 
	 */
	public V put(K key,V value)
	{
		V oldValue=http://www.mamicode.com/null;>