哈希表创建以及哈希表迭代hasNext()与next（）方法理解_hashnext

认识哈希表：

哈希表既是一种查找方法，又是一种存贮方法。我们通常再查找过程中希望能够不经过任何比较，一次便能得到所查记录。不过这是理想状态下。
哈希表：即散列存储结构。
散列法存储的基本思想：建立关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。
优点：查找速度极快（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;
 	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

上面的代码我们可以通过不断的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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

测试用例：

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);
		}
		

	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

输出结果为：