哈希表创建以及哈希表迭代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