首页 > Java开发 > HashTable的数组和连接两种实现方法（Java版本）

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

孤风一剑 10月 21, 2014 214 0

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 = {18, 75, 60, 43, 54, 90, 46, 31, 58, 73, 15, 34};  
  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. }  

标签

相关推荐

标签

.NET (32) ActiveMQ (34) AJAX (29) android (463) android开发 (34) ASP.NET (58) C# (153) CSS (21) eclipse (50) Hadoop (23) Hibernate (51) HTML (30) html5 (29) IOS (48) JAVA (378) JavaScript (87) JQuery (85) js (53) json (26) jsp (28) Linux (70) ListView (28) mvc (28) myeclipse (25) MySQL (151) oracle (181) PHP (158) spring (84) SQL (62) SQL Server (28) string (20) Struts2 (39) Tomcat (39) Ubuntu (20) WEB (28) webservice (29) Windows (27) XML (36) 多线程 (21) 存储过程 (22) 实例 (24) 数据库 (89) 服务器 (31) 算法 (34) 设计模式 (23)

文章归档