对hash思想的理解以及hash表的实现

新的问题总是导致了新的理论和新技术的诞生，其中在计算机领域的有一件事情却不得不提出来让我们讨论一下，那边是java编程语言中的一种数据结构hash集合。java中hash集合最常用的有三种，分别是：hashSet,hashMap及其hashTable。
---中国大姨夫



一：哈希算法诞生的背景


   在十九世纪后半叶，计算机技术飞速发展，为了适应不断提高的高指标运行环境，计算机语言也是层出不穷，其中著名的有c/c++、java、jScript以及后来的c#等等。这些高级计算机语言成为了广大程序员手中的强有力的开发利器。然而在最早的时候，并没有出现像今天如此方便的计算机语言给我们自由发挥，但是随着信息时代的步步紧逼，新的问题就产生了。

       由于信息量过大，使用传统的数据存储方法显然已经满足不了人们需求。因为那时在计算机中数据的存储结构的根本方法只有两种：数组和链表。这两种存储方法各有各自的优点和劣势。例如数组的优势在于数组的长度是固定的，它的每一个下标都指向着唯一的一个值，所以我们知道这样一来的话要在数组中找到一个元素就非常方便了，只需要知道该元素在数组的索引就行了。但是长度固定同时又成了他的缺点，当我们用一个数组来存储一些数据时，需要指定他的长度，但是我们又不知道我们的数据是否就可以被该数组全部装下，一旦超出了数组的长度就会出错。同时如果我们定义一个长度足够长的数组的话又没有必要，因为这样会占用很大一部分的内存，造成计算机的资源浪费。而且当我们要删除不必要的元素时，该索引位置的内存空间是不能被释放的。链表的优势的就在于存储数据时我们只需要将数据不断地接在节点上就行了，这也就意味着链表的长度的没有限制的，所以我们可以很方便的对链表中的数据进行插入，删除等操作。但是由于链表的每一个数据都是环环相扣的，所以当我们需要查询某一个元素时就不得不遍历所有的节点。这时效率就大打折扣了。

      所以我们是否能够找到一个综合了数组和链表各自的优点的一种数据存储方式呢？答案就是哈希算法。哈希算法是由hash这个人发明的，哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。

　　哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。

   关于equals()方法和hashCode()方法的区别和联系大家可以花多点时间去关注一下。

         二：哈希算法中的关键点

  [size=x-small;] 说到hash[/size]算法的成功实现其实关键归功于hashCode的应用。当然这是我个人的理解。[size=medium;]初学者可以这样理解，hashCode[/size]方法实际上返回的就是对象存储的物理地址（实际可能并不是）。    这样一来，当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址。所以这里存在一个冲突解决的问题。这样一来实际调用equals方法的次数就大大降低了，几乎只需要一两次。

[size=medium;] [/size]

        三：实现hash表的基本思路

    由于hash表其实是一个数组+链表的结合体，所以要实现它必须结合数组和链表的知识构建。下面是本人对构建hash表的基本思路。

    1.我们需要指定一个具有初始容量的数组，这个数组的每一个元素实际上是一个链表。例如我们可以这样构建：

  

[code="java"]private int max=0 ;//实际存储数据的最大容量  max = init_capacity*load_factor;
private Entry[] entry;//用来存储数据的数组  此时相当于一张hash表
/**
* 构造函数  这里由于只以测试为目的就直接使用默认的构造器了
*/
public MapMain(){
max = (int) (init_capacity*load_factor);//将最大容量确定下来
entry = new Entry[init_capacity];//实例化这个数组容器
}
 

   在构造函数中就创建数组，并且指定最大数据容量。

2.我们还需要一个节点类，因为我们是自己做一张hash表，所以我们可以将该类封装成一个内部类：


[code="java"]/**
* 定义一个泛型类
* 创建一个内部类   这里不直接实现系统的Map.Entry接口
*/
class Entry {
//将当前节点的父节点和子节点封装起来
Entry lastCode;
Entry nextCode; 
K key; 
V value;  
int hash;
// 构造方法  
Entry(K k, V v, int hash) {  
this.key = k;  
this.value = v;  
this.hash = hash;  

}  
}


   其中K,V就是我们最熟悉的键值对，所以用过hashMap的人们都知道。


       3.接下来就是最关键的步骤了，即map中添加元素的方法。该方法决定了数据在map表中的存储方法。

其实思路也很简单，我们可以用用一张图表很直观的看到：

[img]http://dl.iteye.com/upload/attachment/0065/9574/a1b700dc-588a-3df1-8ed0-8893dc189f30.jpg" alt="[/img]



其中的双向箭头表示里面的每一个链表都是双向链表，这样的话可以方便后面的操作。


4.重建hashMap。这一步是很重要的一步，它是hash表的一个显著特点，因为关乎hash表的效率问题。这里首先要有一个控制量，这个控制量就是hashMap的加载因子。jdk类库里面使用的0.75f,当然这个可以随自己的需要而定。当这个hash表中的数据量超过了我们所设定的限度的时候，比如说我们设定为maxSize  = init_Capacity*0.75f,当size>maxSize时我们就reSetHash。


四： 下面是我自己的一个hashMap的实现代码

  

[code="java"]package 哈希Map;
/**
* 基本思路是用一个泛型类作为节点  然后将该节点作为一个数组的元素
* 所有的数据将存储在这个数组中    即通常所说的挂链式存储方法
* @author nanxia
* @param
* @param
*/

public class MapMain {
public static int init_capacity = 32 ;//初始容量
public static float load_factor = 0.75f;//加载因子
private int size=0;//集合中的容量
private int max=0 ;//实际存储数据的最大容量  max = init_capacity*load_factor;
private Entry[] entry;//用来存储数据的数组  此时相当于一张hash表
/**
* 构造函数  这里由于只以测试为目的就直接使用默认的构造器了
*/
public MapMain(){
max = (int) (init_capacity*load_factor);//将最大容量确定下来
entry = new Entry[init_capacity];//实例化这个数组容器
}
/**
* 定义hash函数   使用简单&位运算符
* 当然我们还可以尝试其他的方法  比如取余%运算等
*/
public int hashFuction(int hashCode,Entry[] entry){
int i = hashCode&(entry.length-1);
return i;
}
/**
* put方法   添加元素进去
*/
public boolean put(K key, V value){
int hash = key.hashCode();//获取键的哈希码
Entry entryCode = new Entry(key,value,hash);//创建数组的一个节点
//先判断是否需要重建
if(size>=max){
reSet(entry.length*5);
}
//添加元素  并且使数据量加一
if(add(entryCode,entry)){
size++;
return true;
}
return false;

}
/**
* 在封装一个方法去添加元素
*/
public boolean add(Entry code,Entry[] entry){

int hash = code.hash;//获取键的哈希码
int index = hashFuction(hash,entry);//通过哈希函数获取到数组的索引位置
//System.out.println("哈希码："+hash+"索引位置："+index);
if(entry[index]==null){
entry[index]=code;//如果该索引位置上没有元素
}else{
Entry next = entry[index].nextCode;
while(next!=null){
//如果添加的元素是重复的
if(next.hash==hash&&next.key.equals(code.key)) return false;
next = next.nextCode;
}
//将链表头储存起来
Entry headCode =entry[index];
//执行到这一步可以知道没有重复的元素  将要添加的元素添加到数组索引位置 即链表头位置
entry[index]=code;
//将链表连接上来
code.nextCode=headCode;
headCode.lastCode=code;
}
return true;

}
/**
* 定义reSet方法   即当容量超过上限时   重建hashMap
*/
public void reSet(int reSize){
//System.out.println("hello");
max = (int) (reSize*load_factor);
Entry[] newEntry = new Entry[reSize];//创建一个容量大于初始容量的新数组
//只需要通过for循环和while循环将每一个数据取出再重新加入到新数组就行
for(int i=0;i headCode = entry[i];
if(headCode!=null){
//********千万要注意这里从原数组中取出的节点不能直接调用add()方法
//因为原数组中的节点包含了对父、子节点的索引   所以直接加的话会出现死循环的错误
//所以必须创建新节点再调用add()方法添加
//这个花了本人很多时间去调试的
//根据原数组中的k、V、hash创建新节点  对父、子节点的引用就不用了
Entry newCode = new Entry(headCode.key,headCode.value,headCode.hash);
add(newCode,newEntry);
Entry next = headCode.nextCode;
while(next!=null){
//同样创建新节点
Entry newNext = new Entry(next.key,next.value,next.hash);
System.out.println(next.key+"死循环！！！");
add(newNext,newEntry);
next = next.nextCode;

}
}else continue;

}
entry = newEntry;//有数组指向新数组
}
/**
* 定义get方法  从map中去的元素
*/
public V getValue(K key){
int hash = key.hashCode();
int index = hashFuction(hash,entry);//获取要搜索的索引
if(entry[index].key.equals(key)){
return entry[index].value;
}else{
Entry next = entry[index].nextCode;
while(next!=null){
if(next.key.equals(key)) return next.value;//遍历该条子链表
next = next.nextCode;
}
}
return null;
}
/**
* remove方法  从map中移除一个元素
*/
public boolean remove(K key){
int hash = key.hashCode();
int index = hashFuction(hash,entry);//获取要搜索的索引
//如果哈希码一样的话则进入下一部   否则hash集合中就没有要找的元素
if(entry[index].key.equals(key)){
entry[index]=null;//如果要删除的元素是链表头
return true;
}else{
Entry next = entry[index].nextCode;//获得下一个节点
while(next!=null){//遍历该条子链表
if(next.key.equals(key)){
Entry next2 = next.nextCode;
//如果next不是最后一个节点
if(next2!=null){
//那么被删除的节点的父节点的子节点应该指向其子节点
next.lastCode.nextCode=next2;
return true;
}else{//如果next是最后一个节点
next.lastCode.nextCode=null;
}
}
next = next.nextCode;
}
}
return false;

}
/**
* 定义一个泛型类
* 创建一个内部类   这里不直接实现系统的Map.Entry接口
*/
class Entry {
//将当前节点的父节点和子节点封装起来
Entry lastCode;
Entry nextCode; 
K key; 
V value;  
int hash;
// 构造方法  
Entry(K k, V v, int hash) {  
this.key = k;  
this.value = v;  
this.hash = hash;  

}  
}
}


   这是我自己根据hash表的原理做的一个map，该表仅实现了put、get、remove等基本方法。仅供参考！


   下面是对上述map的一个测试类


[code="java"]package 哈希Map;

import java.util.HashMap;

public class TestMap {
/**
* 主类
* @param args
*/
public static void main(String[] args) {
//*****自己写的map
MapMain map = new MapMain();
int start = (int) System.currentTimeMillis();
for(int i=0;i hash = new HashMap();
int start2 = (int) System.currentTimeMillis();
for(int i=0;i这个接口可能有优越的性能，我的代码中没有直接实现这个接口。