实验一:查找是否存在关键字
public boolean contains(T key)
实验二:输出散列表
public void printAll()
三、实验方法与步骤(需求分析、算法设计思路、流程图等)
(1)查找是否存在关键字
分析:利用单链表的查找算法,查找是否存在关键字,查找到就返回true,查找不到,返回false。
(2)输出散列表,计算ACL
分析:根据单链表的性质,输出散列表,然后遍历单链表计算ACL。
四、实验原始纪录(源程序、数据结构等)
public class HashSet<T>
{
private SinglyList<T>[] table;
private int count = 0;
private static final float LOAD_FACTOR = 0.75f;
public HashSet(int length)
{
if (length<10)
length=10;
this.table = new SinglyList[length];
for (int i=0; i<this.table.length; i++)
this.table[i] = new SinglyList<T>();
// this.enlarge(capacity);
}
public HashSet()
{
this(16);
}
private int hash(T x)
{
int key = Math.abs(x.hashCode());
return key % this.table.length;
}
public T search(T key)
{
Node<T> find = this.table[this.hash(key)].search(key);
return find==null ? null : find.data;
}
public boolean add(T x)
{
if (this.count>this.table.length*LOAD_FACTOR)
{
this.printAll();
System.out.print("\n添加"+x+",");
SinglyList<T>[] temp = this.table;
this.table = new SinglyList[this.table.length*2];
for (int i=0; i<this.table.length; i++)
this.table[i] = new SinglyList<T>();
this.count=0;
for (int i=0; i<temp.length; i++)
for (Node<T> p=temp[i].head.next; p!=null; p=p.next)
this.add(p.data);
}
boolean insert=this.table[this.hash(x)].insertDifferent(x)!=null;
if (insert)
this.count++;
return insert;
}
public T remove(T key)
{
T x = this.table[this.hash(key)].remove(key);
if (x!=null)
this.count--;
return x;
}
public HashSet(T[] values)
{
this((int)(values.length/HashSet.LOAD_FACTOR));
this.addAll(values);
}
public int size()
{
return count;
}
public boolean isEmpty()
{
return this.size()==0;
}
public boolean contains(T key)
{
return this.search(key)!=null;
}
public void addAll(T[] values)
{
for (int i=0; i<values.length; i++)
this.add(values[i]);
}
public void clear()
{
for (int i=0; i<this.table.length; i++)
this.table[i].clear();
}
public String toString()
{
String str=this.getClass().getName()+"(";
boolean first=true;
for (int i=0; i<this.table.length; i++)
for (Node<T> p=this.table[i].head.next; p!=null; p=p.next)
{
if (!first)
str += ",";
first=false;
str += p.data.toString();
}
return str+")";
}
public void printAll()
{
System.out.println("散列表:容量="+this.table.length+","+this.count+"个元素"+
",hash(key)=key % "+this.table.length+","+this.toString());
for (int i=0; i<this.table.length; i++)
System.out.println("table["+i+"]="+this.table[i].toString());
System.out.print("ASL成功=(");
int asl=0;
for (int i=0; i<this.table.length; i++)
{
int j=1;
for (Node<T> p=this.table[i].head.next; p!=null; p=p.next,j++)
{
System.out.print((asl==0 ? "" : "+")+j);
asl+=j;
}
}
if (count==0)
System.out.println(") = 0\n");
else
System.out.println(")/"+count+"="+asl+"/"+count+" ="+((asl+0.0)/count)+"\n");
}
public Object[] toArray()
{
Object[] values = new Object[this.size()];
int j=0;
for (int i=0; i<this.table.length; i++)
for (Node<T> p=this.table[i].head.next; p!=null; p=p.next)
values[j++] = p.data;
return values;
}
public void enlarge(int length)
{
this.table = new SinglyList[length];
for (int i=0; i<this.table.length; i++)
this.table[i] = new SinglyList<T>();
}
public static Integer[] randomDifferent(int n, int size)
{
Integer[] values = new Integer[n];
HashSet<Integer> set = new HashSet<Integer>(); //构造空散列表
int i=0;
while (i<n)
{
int key = (int)(Math.random()*size);
if (set.add(key)) //添加一个随机数到散列表成功
values[i++]=key;
}
return values; //返回数组引用
}
五、实验结果及分析(计算过程与结果、数据曲线、图表等)
public static void main(String[] args)
{
int n=10, size=100;
Integer[] values = randomDifferent(n, size);
System.out.println(n+"个元素0~"+size+"之间的互异随机数集合: ");
Array1.print(values);
System.out.println();
Integer[] values1 ={16,75,60,43,54,90,46,31,27,88,64,50};
System.out.print("关键字序列: ");
Array1.print(values1); //见例1.4
HashSet<Integer> set = new HashSet<Integer>(10); //构造空散列表,散列数组容量为10
set.addAll(values1); //插入values数组元素
set.printAll();
System.out.println(set+"是否包含关键字:"+set.contains(60));
set.clear();
System.out.println(set);
}
实验结果:
- 输出散列表:
2.判断是否有关键字: