해시 및 해시 코드

Demo: 네가 생각하는 대로 우리는 Groudhog = ghog를 찾아낼 수 있을 거야.newInstance(3);이 키의 것은 찾지 못했다

package cn.partner4java.hashcode;

/**
 *   Groudhog         
 * @author partner4java
 *
 */
public class Groudhog {
	protected int number;
	public Groudhog(int number) {
		this.number = number;
	}
	@Override
	public String toString() {
		return "Groudhog #" + number;
	}
}


package cn.partner4java.hashcode;

import java.util.Random;

/**
 * Predition     boolean    toString  。
 * boolean java.util.randrom()    
 * @author partner4java
 *
 */
public class Prediction {
	private static Random random = new Random(47);
	private boolean shadow = random.nextDouble() > 0.5;
	@Override
	public String toString() {
		if(shadow){
			return "Six more weeks of Winter!";
		}else{
			return "Early Spring";
		}
	}
}


package cn.partner4java.hashcode;

import java.lang.reflect.Constructor;
import java.util.HashMap;
import java.util.Map;

/**
 * detectSpring               Groundhog     Groundhog     。
 * @author partner4java
 *
 */
public class SpringDetector {
	public static <T extends Groudhog> void detectSpring(Class<T> type) throws Exception{
		Constructor<T> ghog = type.getConstructor(int.class);
		Map<Groudhog, Prediction> map = new HashMap<Groudhog, Prediction>();
		for(int i=0;i<10;i++){
			map.put(ghog.newInstance(i), new Prediction());
		}
		System.out.println("map = " + map);
		Groudhog gh = ghog.newInstance(3);
		System.out.println("Looking up prediction for " + gh);
		if(map.containsKey(gh)){
			System.out.println(map.get(gh));
		}else{
			System.out.println("key not found: " + gh);
		}
	}
	
	public static void main(String[] args) throws Exception {
		detectSpring(Groudhog.class);
	}
}

문제는 Groundhog에서 자동으로 기본 Object를 계승하기 때문에, 여기서는 Object의hashCode 방법으로 산열 코드를 생성하는데, 기본적으로 대상의 주소로 산열 코드를 계산합니다.
따라서 두 Groundhog(3)의 해싱 코드가 다릅니다.
단,hashCode를 덮어쓰는 동시에 equals () 방법을 덮어써야 합니다. 그도 Object의 일부분입니다.
HashMap은 equals()를 사용하여 현재 키가 테이블에 있는 키와 같은지 여부를 판단합니다.
올바른 equals 방법은 다음 5가지 조건을 충족해야 합니다.
1. 자반성(reflexive): null이 아닌 인용값 x에 대해 x.equals(x)는true로 되돌아와야 한다.
만약 어긋난다면, 이 종류의 실례를 집합 (collection) 에 추가하면, 이 집합의contains는 당신이 방금 추가한 실례가 포함되지 않았다는 것을 알려 줍니다.
2. 대칭성(symmetric): null이 아닌 인용값 x와 y에 대해 y.equals(x)만true로 되돌아갈 때 x.equals(y)는true로 되돌아와야 한다.
하나의 실례 대비는 대소문자를 구분하지 못하지만, 반대로 대비는 구분되어 비대칭을 초래한다.
3. 전달성(transitive): null이 아닌 인용값 x, y와z에 대해 x.equals(y)가true로 되돌아오고 y.equals(z)도true로 되돌아오면 x.equals(z)도true로 되돌아와야 한다.
하위 클래스가 증가하는 정보는 equals의 비교 결과에 영향을 줄 수 있다.
4. 일치성(consistent): null이 아닌 인용값 x와 y에 대해 equals의 비교 작업이 대상에서 사용하는 정보가 수정되지 않으면 x.equals(y)를 여러 번 호출하면true로 일치하게 되돌아오거나false로 일치하게 되돌아온다.
equals 방법이 신뢰할 수 없는 자원에 의존하는 것은 아니다.
5, 비공식(Non-nullity): 모든 비null의 인용값 x에 대해 x.equals(null)는false를 되돌려야 한다.
기본 equals 방법은 메모리 주소를 비교하는 것입니다.
Groundhog에 hashCode 및 equals 추가 방법:

package cn.partner4java.hashcode;

/**
 *   Groudhog         
 * @author partner4java
 *
 */
public class Groudhog {
	protected int number;
	public Groudhog(int number) {
		this.number = number;
	}
	@Override
	public String toString() {
		return "Groudhog #" + number;
	}
	
	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + number;
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Groudhog other = (Groudhog) obj;
		if (number != other.number)
			return false;
		return true;
	}
	
	
}

지금 찾으실 수 있습니다.
참조:
http://blog.csdn.net/partner4java/article/details/7066349
http://blog.csdn.net/partner4java/article/details/7067919
------------------
hashCode 이해하기()
해싱을 사용하는 목적은 한 객체를 사용하여 다른 객체를 찾으려는 것입니다.그러나 TreeMap을 사용하거나 당신이 직접 Map을 사용해도 이 목적을 달성할 수 있다.
Demo:

package cn.partner4java.hashcode;

import java.util.Map.Entry;

/**
 * Map.entrySet()        Map.Entry<K, V>   。  ，Map.Entry     ，            ，            Map  。
 * @author partner4java
 *
 * @param <K>
 * @param <V>
 */
public class MapEntry<K, V> implements Entry<K, V> {
	private K key;
	private V value;
	
	public MapEntry(K key, V value) {
		super();
		this.key = key;
		this.value = value;
	}
	public K getKey() {
		return key;
	}
//	public void setKey(K key) {
//		this.key = key;
//	}
	public V getValue() {
		return value;
	}
	public V setValue(V v) {
		V result = value;
		value = v;
		return result;
	}
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((key == null) ? 0 : key.hashCode());
		result = prime * result + ((value == null) ? 0 : value.hashCode());
		return result;
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		MapEntry other = (MapEntry) obj;
		if (key == null) {
			if (other.key != null)
				return false;
		} else if (!key.equals(other.key))
			return false;
		if (value == null) {
			if (other.value != null)
				return false;
		} else if (!value.equals(other.value))
			return false;
		return true;
	}
	@Override
	public String toString() {
		return "MapEntry [key=" + key + ", value=" + value + "]";
	}
	
	
	
}



package cn.partner4java.hashcode;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import net.mindview.util.Countries;

/**
 *      ，   ArrayList     Map。
 * put()             ArrayList。   Map      ，        ，               null。
 *      ，           keys           ，               values       。
 * @author partner4java
 *
 * @param <K>
 * @param <V>
 */
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 get(Object key){
		if(!keys.contains(key)){
			return null;
		}
		return values.get(keys.indexOf(key));
	}
	
	public V put(K key,V value){
		V oldValue = get(key); //The old value or null
		if(!keys.contains(key)){
			keys.add(key);
			values.add(value);
		}else{
			values.set(keys.indexOf(key), value);
		}
		return oldValue;
	}
	
	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K,V>>();
		Iterator<K> ki = keys.iterator();
		Iterator<V> vi = values.iterator();
		while(ki.hasNext()){
			set.add(new MapEntry<K, V>(ki.next(),vi.next()));
		}
		return set;
	}

	public static void main(String[] args) {
		SlowMap<String, String> m = new SlowMap<String, String>();
		m.putAll(Countries.capitals(15));
		System.out.println(m);
		System.out.println(m.get("BENIN"));
		System.out.println(m.entrySet());
	}
}

----------------
속도에 대한 해시:
(전제 취지는 라인을 찾는 것보다 빠르기 때문에 수조를 사용하는 것이다)
산열의 가치는 속도에 있다. 산열은 검색을 신속하게 할 수 있다.병목은 키의 검색 속도에 있기 때문에 해결 방안 중 하나는 키의 정렬 상태를 유지하고 Collections를 사용하는 것이다.검색을 위해 binarySearch()를 사용합니다.
산열은 더욱 진일보했다. 그는 빨리 찾을 수 있도록 건강을 어딘가에 유지해야 한다고 말했다.그는 키를 사용하여 생성된 숫자를 유지하고 그것을 그룹의 하표로 삼았다.이 수조는 바로 산열 코드다.
수조 용량이 고정된 문제를 해결하기 위해 키마다 같은 하표가 생길 수 있다.
그래서 하나의 값을 조회하는 과정은 먼저 산열 코드를 계산한 다음에 산열 코드를 사용하여 수조를 조회하는 것이다.일반적으로, 산열 코드가 같으면 외부 링크로 처리됩니다. 수조는 직접 값을 유지하지 않고 값을 유지하는list입니다.그리고list의 값을 equals 방법으로 선형으로 조회합니다.이 부분의 조회는 비교적 느리지만, 산열 함수가 좋으면, 그룹의 모든 위치의 값이 매우 적을 것이다.따라서 전체 리스트를 찾는 것이 아니라, 그룹의 어느 위치로 바로 이동합니다.이것이 바로 HashMap이 비교적 빠를 수 있는 이유다.
Demo:

package cn.partner4java.hashcode;

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

import net.mindview.util.Countries;

public class SimpleHashMap<K, V> extends AbstractMap<K, V> {
	// Choose a prime number for the hash table
	// size,to achieve a uniform distribution
	static final int SIZE = 997;
	// You can't have a physical array of generics,
	// but you can upcast to one;
	@SuppressWarnings("unchecked")
	LinkedList<MapEntry<K, V>>[] buckets = new LinkedList[SIZE];

	@Override
	public V get(Object key) {
		int index = Math.abs(key.hashCode()) % SIZE;
		if (buckets[index] == null)
			return null;
		for (MapEntry<K, V> iPair : buckets[index]) {
			if (iPair.getKey().equals(key)) {
				return iPair.getValue();
			}
		}
		return null;
	}

	@Override
	public V put(K key, V value) {
		V oldValue = null;
		int index = Math.abs(key.hashCode()) % SIZE;
		if (buckets[index] == null)
			buckets[index] = new LinkedList<MapEntry<K, V>>();
		LinkedList<MapEntry<K, V>> bucket = buckets[index];
		MapEntry<K, V> pair = new MapEntry<K, V>(key, value);
		boolean found = false;
		ListIterator<MapEntry<K, V>> it = bucket.listIterator();
		while (it.hasNext()) {
			MapEntry<K, V> iPair = it.next();
			if (iPair.getKey().equals(key)) {
				oldValue = iPair.getValue();
				it.set(pair); // Replace old with new
				found = true;
				break;
			}
		}
		if (!found)
			buckets[index].add(pair);
		return oldValue;
	}

	@Override
	public Set<Map.Entry<K, V>> entrySet() {
		Set<Map.Entry<K, V>> set = new HashSet<Map.Entry<K, V>>();
		for (LinkedList<MapEntry<K, V>> bucket : buckets) {
			if (bucket == null)
				continue;
			for (MapEntry<K, V> mpair : bucket)
				set.add(mpair);
		}
		return set;
	}

	public static void main(String[] args) {
		SimpleHashMap<String, String> m = new SimpleHashMap<String, String>();
		m.putAll(Countries.capitals(25));
		System.out.println(m);
		System.out.println(m.get("ERITREA"));
		System.out.println(m.entrySet());
	}
}

-------------hashCode () equals 방법을 덮어쓰는 모든 클래스에서hashCode 방법을 덮어써야 합니다.그렇지 않으면 Object 위반입니다.hashCode의 일반적인 약속으로 인해 이 종류는 모든 산열 기반 집합과 결합하여 정상적으로 작동할 수 없습니다. 이런 집합은HashMap,HashSet,Hashtable을 포함합니다.인용 프로그램이 실행되는 동안 대상의 equals 방법의 비교 작업에 사용된 정보가 수정되지 않으면 같은 대상을 여러 번 호출하면hashCode 방법은 항상 같은 정수로 되돌아와야 한다.한 응용 프로그램의 여러 번 실행하는 과정에서 매번 실행할 때마다 되돌아오는 정수는 일치하지 않을 수 있다.만약 하나의 대상조차도 equals 방법을 근절하는 것이 같다면, 이 두 대상 중 임의의 대상을 호출하는hashCode 방법은 반드시 같은 정수 결과를 만들어야 한다.만약 두 대상이 equals 방법에 따라 비교가 같지 않다면, 이 두 대상 중 임의의 대상의hashCode 방법을 호출하면 반드시 다른 정수 결과가 나오지 않을 것이다.그러나 프로그래머는 서로 다른 대상에게 확연히 다른 정수 결과를 만들어 산목록(hash table)의 성능을 향상시킬 수 있다는 것을 알아야 한다.(예를 들어 하나의entity가 id에 따라 같은지 아닌지를 비교하지만 실례화되기 전에 id 수치가 없으면 기본 equals는false로 되돌아오지만hashCode가 되돌아오는 값은 같다.)