使用数组和链表实现hash表存储信息
1、HashTable的原理:
通过节点的关键码确定节点的存储位置,即给定节点的关键码k,通过一定的函数关系H(散列函数),得到函数值H(k),将此值解释为该节点的存储地址.
<!--EndFragment-->
简而言之, 哈希表之所以能够实现根据关键字来获取记录, 是因为它在内部建立了记录存储位置 - 即内部数组中的索引号和关键字的一套对应关系H, 因而在查找时, 只需根据这个映射关系H 找到给定键值 K 对应的数H(K)就可直接从数组中取得目的数据,而不必对数组进行遍历和比较. 这个对应关系H我们称为哈希函数.
哈希函数 H的两个重要特点:
1>、哈希函数可以自定义, 只要使得整数 H(K) 的范围不超出哈希表内部存储数组的上下界即可。以下代码即使用了键值index=K%table.length的方法。
2>、K 的取法有任意种, 但 H(K) 只能固定在一个范围, 因此不同的关键字可能对应了相同的哈希值, 形成了冲突.
<!--EndFragment-->2、
3、冲突及解决方案
需要注意的是哈希函数的运算和冲突的处理都需要系统开销,尤其是后者代价不菲。因此产生了两个关键问题: 如何设计函数 H的算法, 以及如何处理冲突, 才能使得哈希表更加高效。
冲突解决技术可以分为两类:开散列方法(也称单练方法或者挂链方法)和闭散列方法(也称开地址法)。这两种方法不同之处与冲突记录的存储有关系。开散列方法将冲突记录在表外,即在表外挂上链表,闭散列方法这把冲突记录存储在表中另一个槽(数组)中。<!--EndFragment-->
开散列方法(挂链法)的一种简单形式把散列表中的每个槽(数组的每个存储地址)定义为一个链表的表头,散列到一个槽的所有记录(即hash索引值相同时)都放在该槽的链表中。以下代码即以这种方式解决了冲突。
闭散列冲突解决方法以及其他改进的冲突解决方案,这里就不详述了,一般的数据结构书上都有介绍。
4、HashTable综合了数组的高效查询和链表的高效增删改,以下是以数组和链表为基础实现的hash表代码。
个人信息类:Accout_info.java
public class Account_info {
private String name;
private String password;
private String city;
public Account_info(String name,String password,String city){
this.name=name;
this.password=password;
this.city=city;
}
public String toString(){
return name+" "+password+" "+city;
}
//get和set函数省略
}
信息节点类:Account_node.java
public class Account_Node {
public Account_Node(int q_num,Account_info info){
keyQQ=q_num;
acc_info=info;
}
public Account_Node next;
public int keyQQ;
public Account_info acc_info;
public String toString(){
return keyQQ+" "+acc_info.toString();
}
}
Hash表类:HashTable.java
public class HashTable {
//基数组,hash表
private Account_Node[] table=new Account_Node[50];
//阈值 hash表存储的数据达到阈值,则rehash
private float threshold=0.75F;
//hash表中数据总数
private long len=0;
//将账号信息放入hash表中
public void put(int q_num,Account_info acc_info){
//通过自定义hash函数获取索引值
int index=hashQ_num(q_num);
/*
* 判断是否超过阈值
* 如果超过,则reHash一次,capacity扩大
* 然后再放!
*/
if(isThreshold()){
int oldCapacity=table.length;
Account_Node[] oldTab=table;
int newCapacity=oldCapacity*2+1;//数组扩容
table=new Account_Node[newCapacity];
for(int i=0;i<oldCapacity;i++){
Account_Node node=oldTab[i];
while(node!=null){
int newIndex=hashQ_num(node.keyQQ);
table[newIndex]=node;
node=node.next;
}
}
}
//1、如果hash表中索引值对应的首个地址为空,即不存在冲突
if(table[index]==null){
table[index]=new Account_Node(q_num,acc_info);
}
//2、存在冲突,则将数据节点放入挂链中的最后一个节点后
else{
Account_Node node=table[index];
//找到链表node的最后一个节点
while(node.next!=null){
node=node.next;
}
//将账户信息节点插入存在index冲突的链表中的最后一个节点
node.next=new Account_Node(q_num,acc_info);
}
len++;
}
//从hash表中取出账号信息
public Account_Node get(int Q_num){
int index=hashQ_num(Q_num);
Account_Node acc_Node=table[index];
//看是否有下了个节点,如有,则是冲突的,就要一个一个比较
if(table[index]==null)
return null;
while(acc_Node.next!=null){
if(acc_Node.keyQQ==Q_num){
return acc_Node;
}else{
acc_Node=acc_Node.next;
}
}
if(acc_Node.keyQQ!=Q_num)
return null;
return acc_Node;
}
//显示hash表
public void showTable(){
for(int index=0;index<table.length;index++){
System.out.print(index+"\t");
Account_Node node=table[index];
while(node!=null){
System.out.print(node.acc_info.getName()+"\t");
node=node.next;
}
System.out.println("");
}
}
//通过账号号码计算账号的has索引值,自定义hash函数
private int hashQ_num(int q_num){
int index=(int) (q_num%table.length);
return index;
}
//判断hash表是否达到阈值
//己放信息节点的个数和table的长度比
private boolean isThreshold(){
if(len/table.length>=threshold)
return true ;
return false;
}
//获取存入hash表中信息的数量
public long TableLen(){
return this.len;
}
}
测试函数:Test.java
public class Test {
/**测试函数
* @param args
*/
public static void main(String[] args) {
HashTable hsT=new HashTable();
Account_info acc;
for(int i=0;i<200;i++){
String name="Name"+i;
String pwd="Pwd"+i;
acc=new Account_info(name,pwd,"长沙");
hsT.put(i, acc);
}
acc=new Account_info("wxy","123","长沙");
hsT.put(108, acc);
hsT.showTable();
Account_Node node=hsT.get(50);
System.out.println(node);
node=hsT.get(120);
System.out.println(node);
}
}
疏漏偏颇之处还请高手指教!
上一篇: 怎么给移动硬盘分区?移动硬盘分区方法图解
下一篇: 假如微软发明了安卓