HashTable的数组和连接两种实现方法(Java版本)

1.散列表的接口类

[java]

  1. package cn.usst.hashtable;  
  2.   
  3. /** 
  4.  * 散列表的接口类 
  5.  * @author G-Xia 
  6.  * 
  7.  */  
  8. public interface HashTable {  
  9.     //向散列表中插入一个关键字为theKey的元素obj,若成功返回真否则返回假  
  10.     boolean insert(Object theKey, Object obj);  
  11.       
  12.     //向散列表中查找并返回给定关键字theKey对应的元素,若查找失败返回空  
  13.     Object search(Object theKey);  
  14.       
  15.     //从散列表中删除关键字为theKey的元素,若删除成功返回真否则返回假  
  16.     boolean delete(Object theKey);  
  17.       
  18.     //返回散列表中已存在的元素个数  
  19.     int size();  
  20.       
  21.     //返回散列表的容量,即散列表的空间大小m的值  
  22.     int capacity();  
  23.       
  24.     //判断散列表是否为空,若为空则返回真  否则返回假  
  25.     boolean isEmpty();  
  26.       
  27.     //清楚散列表的所有元素,使之变成一个空表  
  28.     void clear();  
  29.       
  30.     //输出散列表中保存的所有关键字和对应的元素  
  31.     void output();  
  32.       
  33. }  

 

2.采用开放地址法处理冲突的数组存储类

[java]

  1. package cn.usst.hashtable.seqhashtable;  
  2.   
  3. import cn.usst.hashtable.HashTable;  
  4. /** 
  5.  * 采用线性探测法处理冲突进行散列存储 
  6.  * @author G-Xia 
  7.  * 
  8.  */  
  9. public class SeqHashTable implements HashTable {  
  10.       
  11.     private int m;              //保存散列表的容量  
  12.     private Object[] key;       //定义保存元素关键字的数组  
  13.     private Object[] ht;        //定义保存散列表的数组  
  14.     private int n;              //散列表中已有的元素个数  
  15.     private Object tag;         //元素内容被删除后的关键字删除标记  
  16.       
  17.     //散列函数,采用除  
  18.     private int h(Object theKey){  
  19.         //留余数发,若参数不是整数,应设法转换成整数  
  20.         return (Integer)theKey%m;  
  21.     }  
  22.       
  23.     public SeqHashTable(int mm, Object tag){  
  24.         //假定散列表的容量至少为13  
  25.         if(mm < 13){  
  26.             m = 13;  
  27.         }else{  
  28.             m = mm;  
  29.         }  
  30.         n=0;  
  31.         key = new Object[m];  
  32.         ht = new Object[m];  
  33.         this.tag = tag;         //置关键字删除标记为参加tag的值  
  34.     }  
  35.       
  36.     @Override  
  37.     public boolean insert(Object theKey, Object obj) {  
  38.         int d = h(theKey);  
  39.         int temp = d;  
  40.         while(key[d] != null && key[d].equals(tag) != true){  
  41.             //用线性探测法处理冲突,寻找插入位置  
  42.             if(key[d].equals(theKey) == true)  
  43.                 break;              //元素已经存在,则退出循环  
  44.             d = (d+1) % m;  
  45.             if(d == temp){          //查找一周后扔无位置,应重组散列表或退出运行  
  46.                 System.out.println(“散列表无空间,退出运行”);  
  47.                 System.exit(1);  
  48.             }  
  49.         }  
  50.         if(key[d] == null || key[d].equals(tag)==true){  
  51.             //找到插入位置,插入新的关键字和元素并返回真  
  52.             key[d] = theKey;  
  53.             ht[d] = obj;  
  54.             n++;  
  55.             return true;  
  56.         }else{              //用新元素obj修改已存在的元素并返回假  
  57.             ht[d] = obj;  
  58.             return false;  
  59.         }  
  60.     }  
  61.   
  62.     @Override  
  63.     public Object search(Object theKey) {  
  64.         int d= h(theKey);  
  65.         int temp = d;  
  66.         while(key[d] != null){  
  67.             if(key[d].equals(theKey)){  
  68.                 return ht[d];  
  69.             }else{  
  70.                 d = (d+1) % m;  
  71.             }  
  72.             if(d == temp)  
  73.                 return null;  
  74.         }  
  75.           
  76.         return null;  
  77.     }  
  78.   
  79.     @Override  
  80.     public boolean delete(Object theKey) {  
  81.         int d = h(theKey);  
  82.         int temp = d;  
  83.         while(key[d] != null){  
  84.             if(key[d].equals(theKey)){  
  85.                 key[d] = tag;  
  86.                 ht[d] = null;  
  87.                 n–;  
  88.                 return true;  
  89.             }else{  
  90.                 d = (d+1)%m;  
  91.             }  
  92.             if(d==temp){  
  93.                 return false;  
  94.             }  
  95.         }  
  96.         return false;  
  97.     }  
  98.   
  99.     @Override  
  100.     public int size() {  
  101.         return n;  
  102.     }  
  103.   
  104.     @Override  
  105.     public int capacity() {  
  106.         return m;  
  107.     }  
  108.   
  109.     @Override  
  110.     public boolean isEmpty() {  
  111.         return n==0;  
  112.     }  
  113.   
  114.     @Override  
  115.     public void clear() {  
  116.         for(int i=0; i<m; i++){  
  117.             key[i] = null;  
  118.             ht[i] = null;  
  119.         }  
  120.         n=0;  
  121.     }  
  122.   
  123.     @Override  
  124.     public void output() {  
  125.         for(int i=0; i<m; i++){  
  126.             if(key[i]==null || key[i].equals(tag))  
  127.                 continue;  
  128.             System.out.println(“(“ + key[i] + ” “ + ht[i] + “),”);  
  129.         }  
  130.         System.out.println();  
  131.     }  
  132.   
  133. }  


3.使用链接法处理冲突的连接存储类

节点类型

[java]

  1. package cn.usst.hashtable.linkhashtable;  
  2.   
  3. /** 
  4.  * 采用链接发处理冲突的散列表中节点的类型 
  5.  * @author G-Xia 
  6.  * 
  7.  */  
  8. public class HashNode {  
  9.     Object key;  
  10.     Object element;  
  11.     HashNode next;  
  12.     public HashNode(Object theKey, Object obj){  
  13.         key = theKey;  
  14.         element = obj;  
  15.         next = null;  
  16.     }  
  17. }  

 

实现方法

[java]

  1. package cn.usst.hashtable.linkhashtable;  
  2.   
  3. import cn.usst.hashtable.HashTable;  
  4.   
  5. public class LinkHashTable implements HashTable {  
  6.       
  7.     private int m;          //保存散列表的容量  
  8.     private HashNode[] ht;  //定义保存散列表的数组  
  9.     private int n;          //散列表中已有的元素个数  
  10.       
  11.     //散列函数  
  12.     private int h(Object theKey){  
  13.         return (Integer)theKey % m;  
  14.     }  
  15.   
  16.     public LinkHashTable(int mm){  
  17.         if(mm < 13){  
  18.             m = 13;  
  19.         }else{  
  20.             m = mm;  
  21.         }  
  22.         n = 0;   
  23.         ht = new HashNode[m];  
  24.     }  
  25.       
  26.     @Override  
  27.     public boolean insert(Object theKey, Object obj) {  
  28.         int d = h(theKey);  
  29.         HashNode p = ht[d];  
  30.         // 从单链表中顺序查找关键字为theKey的节点  
  31.         while(p != null){  
  32.             if(p.key.equals(theKey) == true)  
  33.                 break;  
  34.             else  
  35.                 p = p.next;  
  36.         }  
  37.           
  38.         if(p != null){          //用新元素obj修改已有节点的元素值并返回假  
  39.             p.element = obj;  
  40.             return false;  
  41.         }else{  
  42.             p = new HashNode(theKey, obj);  
  43.             p.next = ht[d];  
  44.             ht[d] = p;  
  45.             n++;  
  46.             return true;  
  47.         }  
  48.     }  
  49.   
  50.     @Override  
  51.     public Object search(Object theKey) {  
  52.         int d = h(theKey);  
  53.         HashNode p = ht[d];  
  54.         while(p!=null){  
  55.             if(p.key.equals(theKey))  
  56.                 return p.element;  
  57.             else  
  58.                 p = p.next;  
  59.         }  
  60.         return null;  
  61.     }  
  62.   
  63.     @Override  
  64.     public boolean delete(Object theKey) {  
  65.         int d = h(theKey);  
  66.         HashNode p = ht[d], q = null;   //p指向表头节点,q指向前驱节点,初始为空  
  67.         while(p != null){  
  68.             if(p.key.equals(theKey))  
  69.                 break;  
  70.             else{  
  71.                 q = p;   
  72.                 p = p.next;  
  73.             }  
  74.         }  
  75.         if(p == null)       //没有删除的元素,返回false  
  76.             return false;  
  77.         else if(q == null)  //删除的是表头节点  
  78.             ht[d] = p.next;  
  79.         else                //删除的是非表头节点  
  80.             q.next = p.next;  
  81.         n–;  
  82.           
  83.         return true;  
  84.     }  
  85.   
  86.     @Override  
  87.     public int size() {  
  88.         return n;  
  89.     }  
  90.   
  91.     @Override  
  92.     public int capacity() {  
  93.         return m;  
  94.     }  
  95.   
  96.     @Override  
  97.     public boolean isEmpty() {  
  98.         return n==0;  
  99.     }  
  100.   
  101.     @Override  
  102.     public void clear() {  
  103.         for(int i=0; i<m; i++){  
  104.             ht[i] = null;  
  105.         }  
  106.         n=0;  
  107.     }  
  108.   
  109.     @Override  
  110.     public void output() {  
  111.         for(int i=0; i<m; i++){  
  112.             HashNode p = ht[i];  
  113.             while(p != null){  
  114.                 System.out.println(“(“ + p.key + ” “ + p.element + “),”);  
  115.                 p = p.next;  
  116.             }  
  117.         }  
  118.         System.out.println();  
  119.     }  
  120.   
  121. }  


4.测试方法

[java]

  1. public class SeqHashTableTest {  
  2.     @Test  
  3.     public void seqHashTableTest(){  
  4.         int[] a = {187560435490463158731534};  
  5.         String[] b = {“180”“750”“600”“420”“540”“900”“460”,   
  6.                     “310”“580”“730”“150”“340”};  
  7.         HashTable tb = new SeqHashTable(17, –1);  
  8.         //HashTable tb = new LinkHashTable(17);  
  9.         for(int i=0; i<a.length; i++){  
  10.             tb.insert(a[i], b[i]);  
  11.         }  
  12.         System.out.println(“输出散列表中的所有元素:”);  
  13.         tb.output();  
  14.         System.out.println(“散列表的容量:” + tb.capacity());  
  15.         System.out.println(“散列表中元素的个数:” + tb.size());  
  16.         for(int i=0; i<a.length; i+=3){  
  17.             tb.delete(a[i]);  
  18.         }  
  19.         tb.insert(88“880”);  
  20.         tb.insert(75“7500”);  
  21.         System.out.println(“经插入、删除、修改后,散列表为:”);  
  22.         tb.output();  
  23.         System.out.println(“散列表的容量:” + tb.capacity());  
  24.         System.out.println(“散列表中元素的个数:” + tb.size());  
  25.           
  26.         for(int i=0; i<4; i++){  
  27.             String x = (String)(tb.search(a[i]));  
  28.             if(x != null)  
  29.                 System.out.println(a[i] + ” “ + x);  
  30.             else  
  31.                 System.out.println(a[i] + “为关键字的元素没有找到!”);  
  32.         }  
  33.     }  
  34. }  

标签