欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-01-19 13:14:16
...

1、HashTable的原理:

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

<!--EndFragment-->

 简而言之哈希表之所以能够实现根据关键字来获取记录,  是因为它在内部建立了记录存储位置 即内部数组中的索引号和关键字的一套对应关系H因而在查找时只需根据这个映射关系H 找到给定键值 对应的数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); 
   } 
}

 

 

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

相关标签: 数据结构 算法