大家好,又见面了,我是全栈君。
1.散列表的接口类
package cn.usst.hashtable; /** * 散列表的接口类 * @author G-Xia * */ public interface HashTable { //向散列表中插入一个keyword为theKey的元素obj,若成功返回真否则返回假 boolean insert(Object theKey, Object obj); //向散列表中查找并返回给定keywordtheKey相应的元素,若查找失败返回空 Object search(Object theKey); //从散列表中删除keyword为theKey的元素,若删除成功返回真否则返回假 boolean delete(Object theKey); //返回散列表中已存在的元素个数 int size(); //返回散列表的容量,即散列表的空间大小m的值 int capacity(); //推断散列表是否为空,若为空则返回真 否则返回假 boolean isEmpty(); //清楚散列表的全部元素。使之变成一个空表 void clear(); //输出散列表中保存的全部keyword和相应的元素 void output(); }
2.採用开放地址法处理冲突的数组存储类
package cn.usst.hashtable.seqhashtable; import cn.usst.hashtable.HashTable; /** * 採用线性探測法处理冲突进行散列存储 * @author G-Xia * */ public class SeqHashTable implements HashTable { private int m; //保存散列表的容量 private Object[] key; //定义保存元素keyword的数组 private Object[] ht; //定义保存散列表的数组 private int n; //散列表中已有的元素个数 private Object tag; //元素内容被删除后的keyword删除标记 //散列函数,採用除 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; //置keyword删除标记为參加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){ //找到插入位置,插入新的keyword和元素并返回真 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]; // 从单链表中顺序查找keyword为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] + "为keyword的元素没有找到!"); } }}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116390.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...