首页 > 代码库 > HashTable的数组和连接两种实现方法(Java版本)
HashTable的数组和连接两种实现方法(Java版本)
1.散列表的接口类
package cn.usst.hashtable; /** * 散列表的接口类 * @author G-Xia * */ public interface HashTable { //向散列表中插入一个关键字为theKey的元素obj,若成功返回真否则返回假 boolean insert(Object theKey, Object obj); //向散列表中查找并返回给定关键字theKey对应的元素,若查找失败返回空 Object search(Object theKey); //从散列表中删除关键字为theKey的元素,若删除成功返回真否则返回假 boolean delete(Object theKey); //返回散列表中已存在的元素个数 int size(); //返回散列表的容量,即散列表的空间大小m的值 int capacity(); //判断散列表是否为空,若为空则返回真 否则返回假 boolean isEmpty(); //清楚散列表的所有元素,使之变成一个空表 void clear(); //输出散列表中保存的所有关键字和对应的元素 void output(); }
package cn.usst.hashtable.seqhashtable; import cn.usst.hashtable.HashTable; /** * 采用线性探测法处理冲突进行散列存储 * @author G-Xia * */ public class SeqHashTable implements HashTable { private int m; //保存散列表的容量 private Object[] key; //定义保存元素关键字的数组 private Object[] ht; //定义保存散列表的数组 private int n; //散列表中已有的元素个数 private Object tag; //元素内容被删除后的关键字删除标记 //散列函数,采用除 private int h(Object theKey){ //留余数发,若参数不是整数,应设法转换成整数 return (Integer)theKey%m; } public SeqHashTable(int mm, Object tag){ //假定散列表的容量至少为13 if(mm < 13){ m = 13; }else{ m = mm; } n=0; key = new Object[m]; ht = new Object[m]; this.tag = tag; //置关键字删除标记为参加tag的值 } @Override public boolean insert(Object theKey, Object obj) { int d = h(theKey); int temp = d; while(key[d] != null && key[d].equals(tag) != true){ //用线性探测法处理冲突,寻找插入位置 if(key[d].equals(theKey) == true) break; //元素已经存在,则退出循环 d = (d+1) % m; if(d == temp){ //查找一周后扔无位置,应重组散列表或退出运行 System.out.println("散列表无空间,退出运行"); System.exit(1); } } if(key[d] == null || key[d].equals(tag)==true){ //找到插入位置,插入新的关键字和元素并返回真 key[d] = theKey; ht[d] = obj; n++; return true; }else{ //用新元素obj修改已存在的元素并返回假 ht[d] = obj; return false; } } @Override public Object search(Object theKey) { int d= h(theKey); int temp = d; while(key[d] != null){ if(key[d].equals(theKey)){ return ht[d]; }else{ d = (d+1) % m; } if(d == temp) return null; } return null; } @Override public boolean delete(Object theKey) { int d = h(theKey); int temp = d; while(key[d] != null){ if(key[d].equals(theKey)){ key[d] = tag; ht[d] = null; n--; return true; }else{ d = (d+1)%m; } if(d==temp){ return false; } } return false; } @Override public int size() { return n; } @Override public int capacity() { return m; } @Override public boolean isEmpty() { return n==0; } @Override public void clear() { for(int i=0; i<m; i++){ key[i] = null; ht[i] = null; } n=0; } @Override public void output() { for(int i=0; i<m; i++){ if(key[i]==null || key[i].equals(tag)) continue; System.out.println("(" + key[i] + " " + ht[i] + "),"); } System.out.println(); } }
3.使用链接法处理冲突的连接存储类
节点类型
package cn.usst.hashtable.linkhashtable; /** * 采用链接发处理冲突的散列表中节点的类型 * @author G-Xia * */ public class HashNode { Object key; Object element; HashNode next; public HashNode(Object theKey, Object obj){ key = theKey; element = obj; next = null; } }
package cn.usst.hashtable.linkhashtable; import cn.usst.hashtable.HashTable; public class LinkHashTable implements HashTable { private int m; //保存散列表的容量 private HashNode[] ht; //定义保存散列表的数组 private int n; //散列表中已有的元素个数 //散列函数 private int h(Object theKey){ return (Integer)theKey % m; } public LinkHashTable(int mm){ if(mm < 13){ m = 13; }else{ m = mm; } n = 0; ht = new HashNode[m]; } @Override public boolean insert(Object theKey, Object obj) { int d = h(theKey); HashNode p = ht[d]; // 从单链表中顺序查找关键字为theKey的节点 while(p != null){ if(p.key.equals(theKey) == true) break; else p = p.next; } if(p != null){ //用新元素obj修改已有节点的元素值并返回假 p.element = obj; return false; }else{ p = new HashNode(theKey, obj); p.next = ht[d]; ht[d] = p; n++; return true; } } @Override public Object search(Object theKey) { int d = h(theKey); HashNode p = ht[d]; while(p!=null){ if(p.key.equals(theKey)) return p.element; else p = p.next; } return null; } @Override public boolean delete(Object theKey) { int d = h(theKey); HashNode p = ht[d], q = null; //p指向表头节点,q指向前驱节点,初始为空 while(p != null){ if(p.key.equals(theKey)) break; else{ q = p; p = p.next; } } if(p == null) //没有删除的元素,返回false return false; else if(q == null) //删除的是表头节点 ht[d] = p.next; else //删除的是非表头节点 q.next = p.next; n--; return true; } @Override public int size() { return n; } @Override public int capacity() { return m; } @Override public boolean isEmpty() { return n==0; } @Override public void clear() { for(int i=0; i<m; i++){ ht[i] = null; } n=0; } @Override public void output() { for(int i=0; i<m; i++){ HashNode p = ht[i]; while(p != null){ System.out.println("(" + p.key + " " + p.element + "),"); p = p.next; } } System.out.println(); } }
4.测试方法
public class SeqHashTableTest { @Test public void seqHashTableTest(){ int[] a = {18, 75, 60, 43, 54, 90, 46, 31, 58, 73, 15, 34}; String[] b = {"180", "750", "600", "420", "540", "900", "460", "310", "580", "730", "150", "340"}; HashTable tb = new SeqHashTable(17, -1); //HashTable tb = new LinkHashTable(17); for(int i=0; i<a.length; i++){ tb.insert(a[i], b[i]); } System.out.println("输出散列表中的所有元素:"); tb.output(); System.out.println("散列表的容量:" + tb.capacity()); System.out.println("散列表中元素的个数:" + tb.size()); for(int i=0; i<a.length; i+=3){ tb.delete(a[i]); } tb.insert(88, "880"); tb.insert(75, "7500"); System.out.println("经插入、删除、修改后,散列表为:"); tb.output(); System.out.println("散列表的容量:" + tb.capacity()); System.out.println("散列表中元素的个数:" + tb.size()); for(int i=0; i<4; i++){ String x = (String)(tb.search(a[i])); if(x != null) System.out.println(a[i] + " " + x); else System.out.println(a[i] + "为关键字的元素没有找到!"); } } }
HashTable的数组和连接两种实现方法(Java版本)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。