哈希表

1.什么是哈希表？

哈希表又程散列表，它通过把关键码值(key,value)映射到表中的某个位置来进行查找记录的。映射其实就是将关键码的值通过一个函数计算出索引的位置，这个函数就叫哈希函数，哈希函数可以自己定义，最常用的就是求模运算，好的哈希函数可以提高这个算法的效率。

2.为什么要使用哈希表？

哈希表具备数组和链表的优点，通过哈希函数可以得到索引位置，所以，哈希表的查找效率很高，又因为哈希表是动态生成的，所以，它的空间消耗量不是很大，只是再需要扩充的时候，在分配内存。动态生成时，需要考虑两个因素：1.初始容量，2.装载因子。当放入的数据与容量之比大于装载因子时，这个时候，就需要扩充哈希表，也就是重哈希。

3.哈希算法的实现思路：

   (1).初始化哈希表。

private int default_capacity=16;//哈希表的初始容量
	private float load_factor=0.8f;//哈希表的装载因子
	private Node[] table=new Node[default_capacity];//初始化哈希表
	private int count=0;//哈希表中已有的数据个数

  

    (2)给定哈希函数

 

public int index(int h,int length){ return (h&0x7FFFFFFF)%length; }

 

 h&0x7FFFFFFF是保证得到的hashcode的值为正数。如果直接拿hashcode的值%表长，可能得到的索引值为负数。

(3)向哈希表中放入关键码的值。

   (1)首先必须遍历整个哈希表，看是否存在相同的key值，因为map中是不能存放Key值相同的键值对。如果存在相同的Key值就需要用这个key所对应的value的值替代之前存在的key的值所对应的value的值。

   （2）将Key和value包装成你定义的类的结点类型。

   (3)在放入键值对之前，必须判断哈希表中已存在的数据与哈希表长的比值是否超过装载因子。

      如果超过的话，就需要扩充哈希表。为什么需要用装载因子来衡量呢？因为如果装载因子很大，说明：装入的数据已经很多，那么经哈希函数运算之后得到的索引值相同的概率就越大，那么在这个索引位置的链表就越多。那整个哈希表就有点类型链表结构了，那如果装载因子很小说明：空闲的内存单元就越多，就会浪费空间。装载因子是影响该算法的一个很重要的因素。

      如果没有超过装载因子，先要判断该索引位置有没有键值对已经存在，如果该索引位置的值为空，就直接将这个结点类型放入到该索引位置，如果不为空，就通过指针域后移，直到找到该索引位置的最后一个结点，然后将待插入的键值对直接挂到这个结点的后面。

/**
	 * 向哈希表中放入键值对数据
	 * @param key：键值对中key的值
	 * @param value：键值对中value的值
	 */
	public V put(K key,V value){
		int i=index(key.hashCode(),table.length);//计算得到索引位置的值
		//判断哈希表中是否有重复的Key的值,如果有重复的key值出现，则用新的value的值替代先前的value的值
		for(Node<K,V> node=table[i];node!=null;node=node.next){
			if(node.key.equals(key)){
				V oldValue=node.value;
				node.value=value;
				return oldValue;
			}
		}
		Node<K,V> newNode=new Node<K,V>(key,value);//包装成新的结点
		if(count++>=default_capacity*load_factor){//如果装入的数据的个数与表长之比大于装载因子
			resize(2*default_capacity);//将容量扩充
		}
		if(table[i]==null){//如果该索引位置没有结点
			table[i]=newNode;//直接挂在这个结点上
		}
		else{//如果该索引位置已经存在结点了
			while(table[i].next!=null){//找到这个索引位置的的最后一个结点
				table[i]=table[i].next;
			}
			table[i].next=newNode;//将新的结点挂在最后一个结点的后面
		}
		return null;
	}

  

   (4).rehash的过程。

 这个过程是建立在已放入的数据与表长的值已经超出了装载因子的基础上的，首先就是将容量扩充，然后从原来的哈希表中取得数据，再重新经过哈希函数运算，得到新的索引位置。这个哈希函数没有变化，只是参数(哈希表的长度)变了而已.

/**
	 * 将哈希表的容量进行扩充
	 */
	public void resize(int newCapacity){
		default_capacity=newCapacity;//将新容量赋给defalut_capacity
		Node[] newTable=new Node[newCapacity];//得到一个新的哈希表,容量是以前的两倍
		transfer(newTable);
		table=newTable;
	}

 

/**
	 * 将扩充前哈希表的值重新经过哈希运算得到它在新哈希表中的索引位置
	 * @param newTable：新的哈希表
	 */
	public void transfer(Node[] newTable){
		Node[] oldTable=table;//得到扩充前的哈希表
		for(int i=0;i<oldTable.length;i++){
			Node node=oldTable[i];//得到一个结点对象
			if(node!=null){//如果该结点中有值存在
				oldTable[i]=null;//释放资源
				do{//如果在同一位置还有其他结点
					Node next=node.next;
					int j=index(node.hashCode(),newTable.length);//重新计算索引的值
					node.next=newTable[j];//标记这个位置
					newTable[j]=node;//将最初的第一个在i位置的结点放到新哈希表的j的位置
					node=next;//指针后移，移到下个结点
					}while(node!=null);
				
			}
		}
		
	}

  

 4.hashcode的问题：

不同对象的hashcode值一定不同吗？

我们首先看个示例吧！

ArrayList list=new ArrayList();
		int numberExit=0;
		//hashcode的值不是内存地址，不同对象的hashcode的值可能会相等
		for(int i=0;i<10000;i++){
			Object o=new Object();
			if(list.contains(o.toString())){
				numberExit++;
			}
			else{
				list.add(o.toString());
			}
		}
		System.out.println("已经存在的个数是："+numberExit);
		System.out.println("队列中的个数是："+list.size());

 还需要重写toString()方法。

public String toString ()
	{    return this.getClass().getName() + "@" + Integer.toHexString(this.hashCode());}
	

 我们看下打印结果：

已经存在的个数是：2
队列中的个数是：9998

 从这个例子很明显看到：不同的对象它们的hashcode的值可能相同。像10000个对象中就有2个对象的hashcode的值相同。

那么，这10000个对象的内存地址会相同吗？

		numberExit=0;
		list.clear();
		//内存地址不相同
		for(int i=0;i<10000;i++){
			Object obj=new Object();
			if(list.contains(obj)){
				numberExit++;
			}
			else{
				list.add(obj);
			}
		}
		System.out.println("重复的个数是："+numberExit);
		System.out.println("队列中的个数是："+list.size());

 

重复的个数是：0
队列中的个数是：10000

 由此可以看出：内存地址是不相同的。

所以，hashcode的值不是内存地址，不同对象的hashcode值可能相同，hashcode的值相等，只是说明两个对象在哈希表中的同一条哈希链上。