java，

java，

我之前在java程序中常常会用到Hashmap,但却不知道其原理为何，因为一直抱着吃鸡蛋的人不必知道鸡蛋她妈是谁的心态。当真正去了解其原理时才发现其中有诸多玄妙之处。。。。现在就来分析一下hashmap

 

1：hashmap的数据结构  
Hashmap实际上是一个数组和链表的结合体（在数据结构中，一般称之为“链表散列“），每个数组元素都存在对下一个元素的引用，这就形成了链表结构。这种结构中和了数组和链表的优点，符合中庸之道。。。数组的存在便于查找元素，而链表则使增删改操作便于执行。

 

2：hash函数<br>hash函数的作用是：依key值确定元素在数组中的索引位置。一个好的hash函数可以减少hash冲突的发生。数组中的元素分布越均匀则冲突也会越少。所以数组的创建也是很有讲究的。

常用的hash算法有：

a:直接定址法 ：地址集合 和 关键字集合大小相同

b:数字分析法 ：根据需要hash的 关键字的特点选择合适hash算法，尽量寻找每个关键字的 不同点

c:平方取中法：取关键字平方之后的中间极为作为哈希地址，一个数平方之后中间几位数字与数的每一位都相关，取得位数由表长决定。比如：表长为512,=2^9,可以取平方之后中间9位二进制数作为哈希地址。

d:折叠法：关键字位数很多，而且关键字中每一位上的数字分布大致均匀的时候，可以采用折叠法得到哈希地址，

e:除留取余法除P取余，可以选P为质数，或者不含有小于20的质因子的合数

f:随机数法：通常关键字不等的时候采用此法构造哈希函数较恰当。

 

3：hash冲突  
通过hash算法确定元素位置时通常会有元素分布在同一个位置的情况，这就是hash冲突。解决冲突的办法有很多，如开放地址法，链地址法...我们通常用再哈希法。使用再哈希法时需要明白其中涉及的几个概念。一个是最大容积（Max_<br>Capacibility）,这个是自己定义的，另一个是装载因子，装载因子就好比一个比例系数，用来衡量数组中所有元素的总量所最大容积量的比例。再哈希法就是在数组元素总量最大容积量的比例超过装载因子时使用的。其原理是，扩大最大容积量和数组的大小，实现动态数组。当数组的大小增大时，元素在同一个位置的比例就会减少，这样就可以减少冲突了。

 

package Hash_11_24;
//学生的信息
public class StudentInfo {
	private int ID;  //学号
	private String name;//姓名
	private char score;  //成绩等级
	//构造函数
	StudentInfo(int ID ,String name,char score){
		this.ID=ID;
		this.name=name;
		this.score=score;
	}

	public char getScore() {
		return score;
	}

	public void setScore(char score) {
		this.score = score;
	}

	public int getID() {
		return ID;
	}
	public void setID(int iD) {
		ID = iD;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	}

package Hash_11_24;
//数据存储结构，即含有两个域的数组，一个是数据，一个是对下一个数据的引用
public class LinkedArray<K,V> {
private K key; 
private V value;
private int index;//数据在数组中的位置
private LinkedArray<K,V> next;//对下一个数据的引用，这样就形成了链表
private int id;    //识别号
/*
 * 构造函数
 */
LinkedArray(K key,V value,int index,LinkedArray<K,V> next){
	this.key=key;
	this.value=value;
	this.index=index;
	this.next=next;
}
public K getKey() {
	return key;
}

public int getId() {
	return id;
}
public void setId(int id) {
	this.id = id;
}
public void setKey(K key) {
	this.key = key;
}

public V getValue() {
	return value;
}

public void setValue(V value) {
	this.value = value;
}

public int getIndex() {
	return index;
}

public void setIndex(int index) {
	this.index = index;
}

public LinkedArray<K, V> getNext() {
	return next;
}

public void setNext(LinkedArray<K, V> next) {
	this.next = next;
}



}

package Hash_11_24;

//自己定义的map类，类似HashMap
public class Defmap<K ,V> {
private int arraysize;  //数组的长度
private LinkedArray[] table;  //数组
private int maxsize;
private int currentsize=0;//数组中当前存在的数据的数量
private double loadfactor=0.75;//装载因子
private int Capacity;

/*
 * 构造函数，用来初始化数组
 */
 Defmap(int arraysize,int maxsize){
	this.arraysize=arraysize;
	this.maxsize=maxsize;
	table=new LinkedArray[arraysize];  //初始化数组
	Capacity=(int) (maxsize*loadfactor);
}

/*
 * 计算数据存储在数组中的位置
 */
private int position(int ID){
	int index =ID%arraysize;
	return index;
} 

/*
 * 将数据加入到数组的方法
 */
void put(K key,V value,int id)
{
	int index=position(id);  //所在数组的位置
	//1:如果所加入的键为空
		if(key==null)
			throw new NullPointerException();
	//2：循环指定数组位置中的链表，如果该数组存在所要加入的数据
	for(LinkedArray<K,V> e=table[index];e!=null;e=e.getNext() ){
		Object k=e.getKey();
		if(e.getIndex()==index && (k==key ||k.equals(key)) ){
			System.out.println("该数据已存在，添加失败！");
			return;
		}
	}
	//3:添加数据
	add( key, value, id);
	//System.out.println("添加成功");
}

/*
 * 添加数据，并考虑是否要扩大数组的大小
 */
private void add(K key,V value,int id)
{
	if(++currentsize>Capacity)//如果当前的数组元素总量超过规定的大小时，则扩大数组的大小
	{
		int newCapacity=2*Capacity;
		arraysize=arraysize*2;   //将数组扩大为原来的两倍
		LinkedArray[] newtable=new LinkedArray[arraysize];
		resize(newCapacity , newtable);
	    table=newtable;        //将扩增后的数组赋给原数组
	}
	int index=position(id);
	LinkedArray<K,V> e=table[index];
	table[index]=new LinkedArray ( key, value,index,e); //将该数据存储到链表的头部
	table[index].setId(id);            //将ID设置为识别
}
/*
 * 扩大数组的大小，即重新hash的方法
 */
private void  resize(int newCapacity ,LinkedArray[] newtable){
	Capacity=(int) (newCapacity*loadfactor);
	LinkedArray[] entry=table;
	for(int i=0;i<table.length;i++)
	{
		LinkedArray<K,V> e=entry[i];
		if(e!=null)
			entry[i]=null;
		int index=position(e.getId());
		if(newtable[index]==null)//如果该位置不含元素，则直接将该数据赋给数组链表的头结点
			newtable[index]=e;
		else
			newtable[index].setNext(e);//否则将头结点的指针指向该元素
		do {   
			LinkedArray<K,V> next = e.getNext();  
			if(next==null)
				return;
			int index2=position(next.getId());
			
			if(index==index2)  //如果重置后位置仍相同，则将链表的下一个指针指向该元素
				e.setNext(next);
				
			else if(newtable[index2]==null){//如果不相等且该位置为空，则将该数据设置为该位置链表的头结点
				newtable[index2]=next;
			}
			else 
				newtable[index2].setNext(next);//否则将该数据添加进这个位置的链表中
			e=e.getNext();	
        } while (e != null);  
		
	}
}
/*
 * 得到数据的方法
 */
public V get(K key,int id){
	int index=position(id);
	for(LinkedArray<K,V> e=table[index];e!=null;e=e.getNext() ){
		Object k=e.getKey();
		if(e.getIndex()==index && (k==key ||k.equals(key)) ){
		     return (V) e.getValue();
			
		}
	}
	return null;
}
}

package Hash_11_24;

import java.util.HashMap;
//测试自己写的Defmap与hashmap的添加数据的快慢
public class TestHashmap {
	public static void main(String[] args) {
		Defmap map=new Defmap(100,100000);
		int	count=0;
		Long BeginTime=System.currentTimeMillis();//记录BeginTime 
		for(int  i=0;i<70000;i++)
		{
			StudentInfo info=new StudentInfo (i,"name"+i,(char)(i+65));
			map.put(info.getName(),info.getScore(),info.getID());
		count++;
		}
		System.out.println("count:"+count);
		Long EndTime=System.currentTimeMillis();//记录EndTime  
		System.out.println("insert time-->"+(EndTime - BeginTime));  
		
		//系统所花时间
		HashMap systemmap=new HashMap();
		Long BeginTime_1=System.currentTimeMillis();//记录BeginTime 
		for(int  i=0;i<70000;i++)
		{
			StudentInfo info=new StudentInfo (i,"name"+i,(char)(i+65));
			systemmap.put(info.getName(), info.getScore());
		count++;
		}
		System.out.println("count:"+count);
		Long EndTime_1=System.currentTimeMillis();//记录EndTime  
		System.out.println("insert time-->"+(EndTime_1 - BeginTime_1));  
	}

}