使用数组和链表实现hash表存储信息

1、HashTable的原理:

   通过节点的关键码确定节点的存储位置,即给定节点的关键码k,通过一定的函数关系H(散列函数),得到函数值H(k),将此值解释为该节点的存储地址.

<!--EndFragment-->

 简而言之, 哈希表之所以能够实现根据关键字来获取记录,  是因为它在内部建立了记录存储位置 - 即内部数组中的索引号和关键字的一套对应关系H, 因而在查找时, 只需根据这个映射关系H 找到给定键值 K 对应的数H(K)就可直接从数组中取得目的数据，而不必对数组进行遍历和比较. 这个对应关系H我们称为哈希函数.

哈希函数 H的两个重要特点:   
  1>、哈希函数可以自定义, 只要使得整数 H(K) 的范围不超出哈希表内部存储数组的上下界即可。以下代码即使用了键值index=K%table.length的方法。
    2>、K 的取法有任意种, 但 H(K) 只能固定在一个范围, 因此不同的关键字可能对应了相同的哈希值, 形成了冲突.

<!--EndFragment-->2、

 

3、冲突及解决方案

     需要注意的是哈希函数的运算和冲突的处理都需要系统开销，尤其是后者代价不菲。因此产生了两个关键问题: 如何设计函数 H的算法, 以及如何处理冲突, 才能使得哈希表更加高效。

  冲突解决技术可以分为两类：开散列方法（也称单练方法或者挂链方法）和闭散列方法（也称开地址法）。这两种方法不同之处与冲突记录的存储有关系。开散列方法将冲突记录在表外，即在表外挂上链表，闭散列方法这把冲突记录存储在表中另一个槽（数组）中。<!--EndFragment-->

   开散列方法(挂链法)的一种简单形式把散列表中的每个槽（数组的每个存储地址）定义为一个链表的表头，散列到一个槽的所有记录（即hash索引值相同时）都放在该槽的链表中。以下代码即以这种方式解决了冲突。

   闭散列冲突解决方法以及其他改进的冲突解决方案，这里就不详述了，一般的数据结构书上都有介绍。 

 

4、HashTable综合了数组的高效查询和链表的高效增删改,以下是以数组和链表为基础实现的hash表代码。

个人信息类：Accout_info.java

public class Account_info { 
    private String name; 
    private String password; 
    private String city; 

   public Account_info(String name,String password,String city){ 
        this.name=name; 
        this.password=password; 
        this.city=city; 
    } 

    public String toString(){ 
        return name+" "+password+" "+city; 
    } 
    //get和set函数省略 
}

 

 

信息节点类：Account_node.java

public class Account_Node { 
     public Account_Node(int q_num,Account_info info){ 
        keyQQ=q_num; 
        acc_info=info; 
    } 

    public Account_Node next; 
    public int keyQQ; 
    public Account_info acc_info; 
    public String toString(){ 
         return keyQQ+" "+acc_info.toString(); 
   } 
}

  

Hash表类：HashTable.java

public class HashTable { 
    //基数组，hash表 
    private Account_Node[] table=new Account_Node[50]; 
    //阈值 hash表存储的数据达到阈值，则rehash 
    private float threshold=0.75F; 
    //hash表中数据总数  
    private long len=0; 

    //将账号信息放入hash表中 
    public void put(int q_num,Account_info acc_info){ 
        //通过自定义hash函数获取索引值 
        int index=hashQ_num(q_num); 
       /* 
        * 判断是否超过阈值 
        * 如果超过,则reHash一次,capacity扩大 
        * 然后再放! 
      */ 
       if(isThreshold()){ 
            int oldCapacity=table.length; 
            Account_Node[] oldTab=table; 
            int newCapacity=oldCapacity*2+1;//数组扩容 
            table=new Account_Node[newCapacity]; 
            for(int i=0;i<oldCapacity;i++){ 
               Account_Node node=oldTab[i]; 
               while(node!=null){ 
                     int newIndex=hashQ_num(node.keyQQ); 
                     table[newIndex]=node; 
                     node=node.next; 
               } 
            } 
        } 


        //1、如果hash表中索引值对应的首个地址为空，即不存在冲突 
        if(table[index]==null){ 
            table[index]=new Account_Node(q_num,acc_info); 
        } 
        //2、存在冲突，则将数据节点放入挂链中的最后一个节点后 
        else{ 
            Account_Node node=table[index]; 
           //找到链表node的最后一个节点 
           while(node.next!=null){ 
                node=node.next; 
           } 
          //将账户信息节点插入存在index冲突的链表中的最后一个节点 
           node.next=new Account_Node(q_num,acc_info); 
        } 
        len++; 
    } 

      //从hash表中取出账号信息 
    public Account_Node get(int Q_num){ 
        int index=hashQ_num(Q_num); 
        Account_Node acc_Node=table[index]; 

        //看是否有下了个节点,如有,则是冲突的,就要一个一个比较 
       if(table[index]==null) 
       return null; 
        while(acc_Node.next!=null){ 
           if(acc_Node.keyQQ==Q_num){ 
           return acc_Node; 
           }else{ 
                 acc_Node=acc_Node.next; 
           } 
       } 
        if(acc_Node.keyQQ!=Q_num) 
             return null; 
        return acc_Node; 
    } 

    //显示hash表 
    public void showTable(){ 
        for(int index=0;index<table.length;index++){ 
            System.out.print(index+"\t"); 
            Account_Node node=table[index]; 
            while(node!=null){ 
                System.out.print(node.acc_info.getName()+"\t"); 
                node=node.next; 
           } 
           System.out.println(""); 
        } 
   } 

    //通过账号号码计算账号的has索引值,自定义hash函数 
    private int hashQ_num(int q_num){ 
        int index=(int) (q_num%table.length); 
        return index; 
   } 

   //判断hash表是否达到阈值 
   //己放信息节点的个数和table的长度比 
    private boolean isThreshold(){ 
        if(len/table.length>=threshold) 
        return true ; 
        return false; 
    } 

    //获取存入hash表中信息的数量 
    public long TableLen(){ 
         return this.len;  
    } 
}

  

测试函数：Test.java

public class Test { 

/**测试函数 
* @param args 
*/ 
    public static void main(String[] args) { 
        HashTable hsT=new HashTable(); 
        Account_info acc; 
        for(int i=0;i<200;i++){ 
           String name="Name"+i; 
           String pwd="Pwd"+i; 
           acc=new Account_info(name,pwd,"长沙"); 
           hsT.put(i, acc); 
       } 
       acc=new Account_info("wxy","123","长沙"); 
       hsT.put(108, acc); 
       hsT.showTable(); 
       Account_Node node=hsT.get(50); 
       System.out.println(node); 
       node=hsT.get(120); 
       System.out.println(node); 
   } 
}

 

 

   疏漏偏颇之处还请高手指教！

评论

4 楼 alafqq 2016-11-07  

很好的一篇启蒙hashmap的文章；
HASHTABLE的93行写错了；
我想应该是
if(len>table.length*threshold){

3 楼 lujian19861986 2012-08-14  

还是用c写hashTable省空间

2 楼 lujian19861986 2012-08-14  

不错

1 楼 javafound 2010-11-19  

代码不行,排版可以整些 .