HashSet和散列码的研究

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
。

hashCode 散列码
    散列码是由对象导出的一个整数值。在Object中有一个hashCode方法来得到散列码。
    基本上，每一个对象都有一个默认的散列码，其值就是对象的内存地址。但也有一些对象的散列码不同，
    比如String对象，它的散列码是对内容的计算结果：    

//String对象的散列码计算   
  String str="hello";   
  int hash=0;   
  for(int i=0;i<length();i++)   
     hash=31*hash+charAt(i);  

 
     那么下面散列码的结果不同也就好解释了。s和t都还是String对象，散列码由内容获得，结果一样。
     sb和tb是StringBuffer对象，自身没有hashCode方法，只能继承Object的默认方法，散列码是对象地址，当然不一样了。
   

 String s=new String("OK");//散列码: 3030   
String t="Ok";  /散列码: 3030  
StringBuffer sb=new StringBuffer(s);  //散列码：20526976   
StringBuffer tb=new StringBuffer(t);  //散列码：20527144  

 

 HashSet 散列表的内部结构

      HashSet是个链表数组。每一个数组元素就是一个列表，我们称为散列表元 .

数组并不保存键本身。而是通过键对象生成一个数字，将其作为数组的下标。这个数字就是散列码。然后根据数组下标等于散列码找到对应的散列表元，然后在线性遍历该链表找到对应的键值。如果散列函数好的话，数组的每个位置就只有较少的值。因此，不是查询整个list而是快速的跳到数组的某个位置，只是对很少的元素进行比较。
      
      HashSet 如何add机制

        假如我们有一个数据(散列码76268)，而此时的HashSet有128个散列单元，那么这个数据将有可能插入到数组的第108个链表中(76268%128=108)。但这只是有可能，如果在第108号链表中发现有一个老数据与新数据equals()=true的话，这个新数据将被视为已经加入，而不再重复丢入链表。

       那么数据的散列码我知道，但HashSet的散列单元大小如何指定那?

       Java默认的散列单元大小全部都是2的幂，初始值为16（2的4次幂）。假如16条链表中的75%链接有数据的时候，则认为加载因子达到默认的0.75。HahSet开始重新散列，也就是将原来的散列结构全部抛弃，重新开辟一个散列单元大小为32（2的5次幂）的散列结果，并重新计算各个数据的存储位置。以此类推下去.....

  知道了HashSet的add机制后，查找的道理一样。直接根据数据的散列码和散列表的数组大小计算除余后，就得到了所在数组的位置，然后再查找链表中是否有这个数据即可。

      查找的代价也就是在链表中，但是真正一条链表中的数据很少，有的甚至没有。几乎没有什么迭代的代价可言了。所以散列表的查找效率建立在散列单元所指向的链表中的数据要少 。

总结：
 1、HashSet不能重复存储equals相同的数据 。原因就是equals相同，数据的散列码也就相同（hashCode必须和equals兼容）。大量相同的数据将存放在同一个散列单元所指向的链表中，造成严重的散列冲突，对查找效率是灾难性的。

      2、HashSet的存储是无序的 ，没有前后关系，他并不是线性结构的集合。

      3、hashCode必须和equals必须兼容， 这也是为了第1点。

package containers;
import java.util.*;
//一个简单的散列Map
public class SimpleHashMap <K,V> extends AbstractMap<K,V>{
	static final int size=997;
	LinkedList<MapEntry<K, V>>[] buckets=new LinkedList[size];
	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=buckets[index].listIterator();
		while(it.hasNext()){
			MapEntry<K,V> iPair=it.next();
			if(iPair.getKey().equals(key)){
				oldValue=iPair.getValue();
				it.set(pair);
				found=true;
				break;
			}
		}
		if(!found){
			buckets[index].add(pair);
		}
		return oldValue;
	}
	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 Set<java.util.Map.Entry<K, V>> entrySet() {
		Set<java.util.Map.Entry<K, V>> set=new HashSet<Entry<K,V>>() ;
		for(LinkedList<MapEntry<K,V>> bucket:buckets){
			if(bucket==null)
				continue;
			else
				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>();
		String[] str="A B C D E F G H J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! @ # $ %　^ & * ( ) - + _ = | \\ / . > < ,".split(" ");
		Map<String,String> map=new HashMap<String,String>();
		for(int i=1;i<=str.length;i++){
			map.put(Integer.toString(i), str[i-1]);
		}
		m.putAll(map);
		System.out.println(m);
		long startTime=System.nanoTime();
		System.out.println(m.get("9"));
		System.out.println(m.get("20"));
		System.out.println(m.get("30"));
		long estimatedTime=System.nanoTime()-startTime;
		System.out.println(estimatedTime);//165386

	}
	
}

一个未经过散列的Map

package containers;

import java.util.*;

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=get(key);
		if(!keys.contains(key)){
			keys.add(key);
			values.add(value);
		}else{
			values.set(keys.indexOf(key),value);
		}
		return oldValue;
	}
	public V get(Object key){
		if(keys.contains(key)){
			return values.get(keys.indexOf(key));
		}else{
			return null;
		}
	}
	
	public Set<java.util.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(ki.next(),vi.next()));
		}
		return set;
	}
	public static void main(String[] args) {
		SlowMap<String,String> m=new SlowMap<String,String>();
		String[] str="A B C D E F G H J K L M N O P Q R S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9 ! @ # $ %　^ & * ( ) - + _ = | \\ / . > < ,".split(" ");
		Map<String,String> map=new HashMap<String,String>();
		for(int i=1;i<=str.length;i++){
			map.put(Integer.toString(i), str[i-1]);
		}
		m.putAll(map);
		System.out.println(m);
		long startTime=System.nanoTime();
		System.out.println(m.get("9"));
		System.out.println(m.get("20"));
		System.out.println(m.get("30"));
		long estimatedTime=System.nanoTime()-startTime;
		System.out.println(estimatedTime);//187057
	}
	

}

MapEntry.java文件

package containers;

import java.util.Map.Entry;

public class MapEntry<K,V> implements Entry<K,V> {
	private K key;
	private V value;
	@Override
	public K getKey() {
		return key;
	}
	@Override
	public V getValue() {
		return value;
	}
	@Override
	public V setValue(V v) {
		V result=value;
		value=v;
		return result;
	}
	public int hashCode(){
		return (key==null?0:key.hashCode())^(value==null?0:value.hashCode());
	}
	public boolean equals(Object o){
		if(!(o instanceof MapEntry))
			return false;
		MapEntry me=(MapEntry)o;
		return (key==null?me.getKey()==null:key.equals(me.getKey()))&&
			(value==null?me.getValue()==null:value.equals(me.getValue()));
	}
	public String toString(){
		return key+"="+value;
	}
	public MapEntry(K k,V v){
		this.key=k;
		this.value=v;
	}
	

}