哈希表创建以及哈希表迭代hasNext()与next()方法理解
认识哈希表:
哈希表既是一种查找方法,又是一种存贮方法。我们通常再查找过程中希望能够不经过任何比较,一次便能得到所查记录。不过这是理想状态下。
哈希表:即散列存储结构。
散列法存储的基本思想:建立关键码字与其存储位置的对应关系,或者说,由关键码的值决定数据的存储地址。
优点:查找速度极快(O(1)),查找效率与元素个数n无关!
例1:若将学生信息按如下方式存入计算机,如:
将2001011810201的所有信息存入V[01]单元;
将2001011810202的所有信息存入V[02]单元;
……
将2001011810231的所有信息存入V[31]单元。
如果想要查找2001011810216的学生信息,直接访问V[16]即可。
哈希方法(杂凑法):
选取某个函数,依该函数按关键字计算元素的存储位置,并按此存放;查找时,由同一个函数对给定值k计算地址,将k与地址单元中元素关键码进行比较,确定查找是否成功。
哈希函数:
哈希方法中使用的转换函数称为哈希函数(杂凑函数)
哈希表也叫杂凑表
冲突:
通常关键码的集合比哈希地址集合大得多,因而经过哈希函数变换后,可能将不同的关键码映射到同一个哈希地址上,这种现象称为冲突。
在哈希表中冲突是难以避免的,不过可以通过好的操作方案减少冲突。
下面介绍哈希函数构造方法:
1.直接定址法,2.除留余数法,3。乘余取整法
4.数字分析法,5.平方取中法,6.折叠法,7/随机数法。
我在这里更偏向于除留余数法,下面也就是用除留余数法简历哈希表。
为了减少尽可能的减少冲突,我选择拉链法。
拉链法基本思想:
将具有相同哈希地址的记录链成一个单链表,m个哈希地址就设m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构。
class Node<T>
{
T data;
int key;
Node<T> next;
public Node(int key, T data)
{
this.key=key;
this.data=data;
this.next=null;
}
}
public class hashMap<T>
{
private Node<T>[] bucket; //数组用存储链表头节点
private Node<T> currentPre;//数组第一个存储的节点
private int current;
public hashMap()
{
this.bucket= new Node[10];
this.current=-1;
this.currentPre=null;
}
public hashMap(int size)
{
this.bucket= new Node[size];
this.current=-1;
this.currentPre=null;
}
public boolean addObject(int key, T value)
{
int index=key%this.bucket.length; //除留余数法
Node<T> p=new Node<T>(key,value);//头插法
p.next=this.bucket[index];
this.bucket[index]=p;
return true;
}
public boolean addObject1(int key,T value)
{
int index=key%this.bucket.length;
Node<T> q=this.bucket[index];
Node<T> p=new Node<T>(key,value);
while(q!=null&&q.key!=key)
{
q=q.next;//往后遍历寻找
}
if(q!=null) q.data=value;//当key相同的,后来添加的值将覆盖原来的值。
else
{
p.next=this.bucket[index];//头插法
this.bucket[index]=p;
}
return true;
}
上面的代码我们可以通过不断的addObject()来建立一个哈希表。
获取哈希表中的值,并且通过迭代来取出哈希表中的值。
hashNext():判断集合中元素是否遍历完毕,如果没有,就返回true。
next():是返回当前元素, 并指向下一个元素。
public T getObject(int key)
{
int index=key%this.bucket.length; //除留余数法
Node<T> p=this.bucket[index];
while(p!=null)
{
if(p.key==key) return p.data;
p=p.next;
}
return null;
}
public boolean hasNext()//判断集合中元素是否遍历完毕,如果没有,就返回true。
{
while(this.current<this.bucket.length)//-1
{
if(this.currentPre!=null) return true;
//不等于null说明这个地方存有值。然后交给next()函数遍历该链表输出。
this.current++;
if(this.current==this.bucket.length) return false;//当指针等于长度说明遍历完毕
this.currentPre=this.bucket[this.current];//向存有头节点的数组下一个遍历。
}
return false;
}
public T next()//是返回当前元素, 并指向下一个元素。
{
T data=this.currentPre.data;
this.currentPre=this.currentPre.next;//把这一个链表遍历一遍
return data;
}
public void reset()//重置。
{
this.current=-1;
this.currentPre=null;
}
public boolean isEmpty()//判断哈希表是否为空。
{
for(int i=0;i<this.bucket.length;i++)
if(this.bucket[i]!=null) return false;
return true;
}
测试用例:
public static void main(String[] args) {
// TODO Auto-generated method stub
hashMap<String> hash=new hashMap<String>();
hash.addObject(12,"wowowowowo");
hash.addObject(13,"aowowowowo");
hash.addObject(22,"bowowowowo");
hash.addObject(14,"cowowowowo");
hash.addObject(15,"dowowowowo");
hash.addObject(16,"eowowowowo");
hash.addObject(34,"fowowowowo");
while(hash.hasNext())
{
String s=hash.next();
System.out.println(s);
}
System.out.println("=========");
hash.reset();
hash.addObject1(22, "hahahahahha");
while(hash.hasNext())
{
String s=hash.next();
System.out.println(s);
}
}
输出结果为:
本文地址:https://blog.csdn.net/qq_41914142/article/details/107369484