数组、链表、Hash（转）

在程序中，存放指定的数据最常用的数据结构有两种：数组和链表。

数组和链表的区别：

1、数组是将元素在内存中连续存放。

链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。

2、数组必须事先定义固定的长度，不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

链表动态地进行存储分配，可以适应数据动态地增减的情况。

3、(静态)数组从栈中分配空间, 对于程序员方便快速,但是*度小。

链表从堆中分配空间, *度大但是申请管理比较麻烦。

数组和链表在存储数据方面到底孰优孰劣呢？根据数组和链表的特性，分两类情况讨论。

一、当进行数据查询时，数组可以直接通过下标迅速访问数组中的元素。而链表则需要从第一个元素开始一直找到需要的元素位置，显然，数组的查询效率会比链表的高。

二、当进行增加或删除元素时，在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样，如果想删除一个元素，需要移动大量元素去填掉被移动的元素。而链表只需改动元素中的指针即可实现增加或删除元素。

那么，我们开始思考：有什么方式既能够具备数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势？HASH呼之欲出。

所谓的hash，简单的说就是散列，即将输入的数据通过hash函数得到一个key值，输入的数据存储到数组中下标为key值的数组单元中去。

我们发现，不相同的数据通过hash函数得到相同的key值。这时候，就产生了hash冲突。解决hash冲突的方式有两种。一种是挂链式，也叫拉链法。挂链式的思想在产生冲突的hash地址指向一个链表，将具有相同的key值的数据存放到链表中。另一种是建立一个公共溢出区。将所有产生冲突的数据都存放到公共溢出区，也可以使问题解决。

如何实现hash的动态增加空间的效果？这和装在因子密切相关。装填因子 = 填入表中的元素个数 / 散列表的长度。当装填因子达到一定值a时，我们就让数组增加一定的内存空间，同时rehash。

下面用两个示例来加深理解。

示例一：用链表实现队列

节点类

1. package cn.netjava.hash;
2. public class LinkNode {
3. //构造器：传入Object对象
4. public LinkNode(Object obj){
5. data=obj;
6. }
7. public Object data; //Object对象
8. public LinkNode next;//下一个节点
9. //重写toString方法
10. public String toString(){
11. //System.out.println(data);
12. return (String)data;
13. }
14. //返回Object对象
15. public Object getData(){
16. return data;
17. }
18. //修改Onject对象
19. public Object Update(Object o){
20. data=o;
21. return o;
22. }
23. }

package cn.netjava.hash;

public class LinkNode {

	//构造器：传入Object对象

	public LinkNode(Object obj){
		data=obj;
	}
	public Object data; //Object对象
	public LinkNode next;//下一个节点

        //重写toString方法

	public String toString(){
		//System.out.println(data);
		return (String)data;
	}

       //返回Object对象
	public Object getData(){
		return data;
	}
        //修改Onject对象
	public Object Update(Object o){
		data=o;
		return o;
	}
}

队列类

1. package cn.netjava.hash;
2. public class LinkQueue {
3. public LinkNode front=null;//第一个节点
4. public LinkNode last=null;//最后一个节点
5. public static void main(String args[]){
6. LinkQueue lq=new LinkQueue();
7. LinkNode lq1=new LinkNode("郑睿1");
8. LinkNode lq2=new LinkNode("郑睿2");
9. LinkNode lq3=new LinkNode("郑睿3");
10. LinkNode lq4=new LinkNode("郑睿4");
11. lq.InsertLinkNode(lq1);
12. lq.InsertLinkNode(lq2);
13. lq.InsertLinkNode(lq3);
14. lq.InsertLinkNode(lq4);
15. int count=lq.getLength();
16. System.out.println("链表的长度为"+count);
17. for(int i=0;i<count;i++){
18. LinkNode ln = lq.getLinkNode(i);
19. System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
20. }
21. lq.deleteLinkNode(2);
22. count=lq.getLength();
23. System.out.println("链表现在的长度是"+lq.getLength());
24. for(int i=0;i<count;i++){
25. LinkNode ln = lq.getLinkNode(i);
26. System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
27. }
28. lq.getLinkNode(1).Update("更新后的对象郑睿");
29. for(int i=0;i<count;i++){
30. LinkNode ln = lq.getLinkNode(i);
31. System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
32. }
33. for(int i=0;i<200;i++){
34. LinkNode ln = new LinkNode(i);
35. lq.InsertLinkNode(ln);
36. }
37. System.out.println("数组长度为"+lq.getLength());
38. }
39. /**
40. * 插入节点
41. * @param obj：插入节点的对象
42. */
43. public void InsertLinkNode(Object obj){
44. //当链表为空，新建一个节点并设置为第一个节点
45. if(front==null){
46. front=new LinkNode(obj);
47. last=front;
48. }
49. //当链表不为空，新建一个节点并插入到最后一个节点的后面
50. else{
51. LinkNode next=new LinkNode(obj);
52. last.next=next;
53. last=next;
54. }
55. }
56. /**
57. *在指定索引下插入节点
58. * @param index
59. */
60. public void insertIndexObj(int index,Object obj){
61. //判断输入的索引是否越界，如果越界，则抛出异常
62. int total=getLength();
63. if(index>total||index<0)
64. throw new java.lang.RuntimeException("输入的索引越界了！");
65. LinkNode lNode=getLinkNode(index);
66. LinkNode linkNode=new LinkNode(obj);
67. lNode.insert(linkNode);
68. }
69. /**
70. * 根据索引删除链表
71. * @param index：索引
72. */
73. public void deleteLinkNode(int index){
74. //判断输入的索引是否越界，如果越界，则抛出异常
75. int total=getLength();
76. if(index>total||index<0)
77. throw new java.lang.RuntimeException("输入的索引越界了！");
78. if(front!=null){
79. LinkNode n=front;
80. LinkNode m=front;
81. int count=0;
82. while(n!=null){
83. if(count==index){
84. if(n.equals(front)){
85. front=front.next;
86. }
87. else{
88. m.next=n.next;
89. }
90. }
91. m=n;
92. n=n.next;
93. count++;
94. }
95. }
96. }
97. /**
98. * 根据索引取出节点
99. * @param lNode:节点
100. * @return：根据索引返回的节点
101. */
102. public LinkNode getLinkNode(int index){
103. if(front==null)
104. return null;
105. LinkNode l=front;
106. int count=0;
107. while(l!=null){
108. if(count==index)
109. return l;
110. count++;
111. l=l.next;
112. }
113. return null;
114. }
115. /**
116. * 得到链表的长度
117. * @return：链表的长度
118. */
119. public int getLength(){
120. if(front==null)
121. return 0;
122. LinkNode l=front;
123. int count=0;
124. while(l!=null){
125. count++;
126. l=l.next;
127. }
128. return count;
129. }
130. /**
131. * 修改对象节点
132. * @param index：对象节点索引
133. * @param obj：修改对象内容
134. */
135. public void UpdateLinkNode(int index,Object obj){
136. LinkNode lNode=getLinkNode(index);
137. lNode.Update(obj);
138. }
139. }

package cn.netjava.hash;

public class LinkQueue {

	public LinkNode front=null;//第一个节点
	public LinkNode last=null;//最后一个节点

	public static void main(String args[]){
		LinkQueue lq=new LinkQueue();
		LinkNode lq1=new LinkNode("郑睿1");
		LinkNode lq2=new LinkNode("郑睿2");
		LinkNode lq3=new LinkNode("郑睿3");
		LinkNode lq4=new LinkNode("郑睿4");
		lq.InsertLinkNode(lq1);
		lq.InsertLinkNode(lq2);
		lq.InsertLinkNode(lq3);
		lq.InsertLinkNode(lq4);
		int count=lq.getLength();
		System.out.println("链表的长度为"+count);
		for(int i=0;i<count;i++){
			LinkNode ln = lq.getLinkNode(i);
			System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
		}
		lq.deleteLinkNode(2);
		count=lq.getLength();
		System.out.println("链表现在的长度是"+lq.getLength());
		for(int i=0;i<count;i++){
			LinkNode ln = lq.getLinkNode(i);
			System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
		}
		lq.getLinkNode(1).Update("更新后的对象郑睿");
		for(int i=0;i<count;i++){
			LinkNode ln = lq.getLinkNode(i);
			System.out.println("链表的第"+i+"个元素的的值为"+ln.getData().toString());
		}
		for(int i=0;i<200;i++){
			LinkNode ln = new LinkNode(i);
			lq.InsertLinkNode(ln);
		}
		System.out.println("数组长度为"+lq.getLength());
	}

	/**
	 * 插入节点
	 * @param obj：插入节点的对象
	 */
	public void InsertLinkNode(Object obj){

		//当链表为空，新建一个节点并设置为第一个节点
		if(front==null){
			front=new LinkNode(obj);
			last=front;
		}
		//当链表不为空，新建一个节点并插入到最后一个节点的后面
		else{
			LinkNode next=new LinkNode(obj);
			last.next=next;
			last=next;
		}
	}
	/**
	 *在指定索引下插入节点
	 * @param index
	 */
	public void insertIndexObj(int index,Object obj){
		//判断输入的索引是否越界，如果越界，则抛出异常
		int total=getLength();
		if(index>total||index<0)
			throw new java.lang.RuntimeException("输入的索引越界了！");
		LinkNode lNode=getLinkNode(index);
		LinkNode linkNode=new LinkNode(obj);
		lNode.insert(linkNode);

	}
	/**
	 * 根据索引删除链表
	 * @param index：索引
	 */
	public void deleteLinkNode(int index){

		//判断输入的索引是否越界，如果越界，则抛出异常
		int total=getLength();
		if(index>total||index<0)
			throw new java.lang.RuntimeException("输入的索引越界了！");
		if(front!=null){
		LinkNode n=front;
		LinkNode m=front;
		int count=0;
		while(n!=null){
			if(count==index){
				if(n.equals(front)){
					front=front.next;
				}
				else{
					m.next=n.next;
				}
			}
			m=n;
			n=n.next;
			count++;
		}
		}
	}
	/**
	 * 根据索引取出节点
	 * @param lNode:节点
	 * @return：根据索引返回的节点
	 */
	public LinkNode getLinkNode(int index){
		if(front==null)
		return null;
		LinkNode l=front;
		int count=0;
		while(l!=null){
			if(count==index)
			return l;
			count++;
			l=l.next;
		}
		return null;
	}

	/**
	 * 得到链表的长度
	 * @return：链表的长度
	 */
	public int getLength(){
		if(front==null)
			return 0;
		LinkNode l=front;
		int count=0;
		while(l!=null){
			count++;
			l=l.next;
		}
		return count;
	}
	/**
	 * 修改对象节点
	 * @param index：对象节点索引
	 * @param obj：修改对象内容
	 */
	public void UpdateLinkNode(int index,Object obj){
		LinkNode lNode=getLinkNode(index);
		lNode.Update(obj);

	}
}

示例二：保存QQ号码及QQ用户

QQ用户类

1. package cn.netjava.hash;
2. public class QQUser {
3. public String userName;//用户姓名
4. public String passWord;//用户密码
5. public String sex;//用户性别
6. public int age;//用户年龄
7. public String getUserName() {
8. return userName;
9. }
10. public void setUserName(String userName) {
11. this.userName = userName;
12. }
13. public String getPassWord() {
14. return passWord;
15. }
16. public void setPassWord(String passWord) {
17. this.passWord = passWord;
18. }
19. public String getSex() {
20. return sex;
21. }
22. public void setSex(String sex) {
23. this.sex = sex;
24. }
25. public int getAge() {
26. return age;
27. }
28. public void setAge(int age) {
29. this.age = age;
30. }
31. }

package cn.netjava.hash;

public class QQUser {

	public String userName;//用户姓名
	public String passWord;//用户密码
	public String sex;//用户性别
	public int age;//用户年龄

	public String getUserName() {
		return userName;
	}
	public void setUserName(String userName) {
		this.userName = userName;
	}
	public String getPassWord() {
		return passWord;
	}
	public void setPassWord(String passWord) {
		this.passWord = passWord;
	}
	public String getSex() {
		return sex;
	}
	public void setSex(String sex) {
		this.sex = sex;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}

}

队列类

1. package cn.netjava.hash;
2. public class LinkQueue {
3. public LinkNode front=null;//第一个节点
4. public LinkNode last=null;//最后一个节点
5. /**
6. * 根据索引删除链表
7. * @param index：索引
8. */
9. public void deleteLinkNode(int index){
10. if(index<0||index>)
11. if(front!=null){
12. LinkNode n=front;
13. LinkNode m=front;
14. int count=0;
15. while(n!=null){
16. if(count==index){
17. if(n.equals(front)){
18. front=front.next;
19. }
20. else{
21. m.next=n.next;
22. }
23. }
24. m=n;
25. n=n.next;
26. count++;
27. }
28. }
29. }
30. /**
31. * 根据索引取出节点
32. * @param lNode:节点
33. * @return：根据索引返回的节点
34. */
35. public LinkNode getLinkNode(int index){
36. if(front==null)
37. return null;
38. LinkNode l=front;
39. int count=0;
40. while(l!=null){
41. if(count==index)
42. return l;
43. count++;
44. l=l.next;
45. }
46. return null;
47. }
48. /**
49. * 得到链表的长度
50. * @return：链表的长度
51. */
52. public int getLength(){
53. if(front==null)
54. return 0;
55. LinkNode l=front;
56. int count=0;
57. while(l!=null){
58. count++;
59. l=l.next;
60. }
61. return count;
62. }
63. /**
64. * 修改对象节点
65. * @param index：对象节点索引
66. * @param obj：修改对象内容
67. */
68. public void UpdateLinkNode(int index,Object obj){
69. LinkNode lNode=getLinkNode(index);
70. lNode.Update(obj);
71. }
72. }

package cn.netjava.hash;

public class LinkQueue {

	public LinkNode front=null;//第一个节点
	public LinkNode last=null;//最后一个节点

	/**
	 * 根据索引删除链表
	 * @param index：索引
	 */
	public void deleteLinkNode(int index){
                if(index<0||index>)
		if(front!=null){
		LinkNode n=front;
		LinkNode m=front;
		int count=0;
		while(n!=null){
			if(count==index){
				if(n.equals(front)){
					front=front.next;
				}
				else{
					m.next=n.next;
				}
			}
			m=n;
			n=n.next;
			count++;
		}
		}
	}
	/**
	 * 根据索引取出节点
	 * @param lNode:节点
	 * @return：根据索引返回的节点
	 */
	public LinkNode getLinkNode(int index){
		if(front==null)
		return null;
		LinkNode l=front;
		int count=0;
		while(l!=null){
			if(count==index)
			return l;
			count++;
			l=l.next;
		}
		return null;
	}

	/**
	 * 得到链表的长度
	 * @return：链表的长度
	 */
	public int getLength(){
		if(front==null)
			return 0;
		LinkNode l=front;
		int count=0;
		while(l!=null){
			count++;
			l=l.next;
		}
		return count;
	}
	/**
	 * 修改对象节点
	 * @param index：对象节点索引
	 * @param obj：修改对象内容
	 */
	public void UpdateLinkNode(int index,Object obj){
		LinkNode lNode=getLinkNode(index);
		lNode.Update(obj);

	}
}

QQ节点类

1. package cn.netjava.hash;
2. public class QQNode {
3. //构造器：传入QQ号，QQ用户对象
4. public QQNode(int qq,QQUser user){
5. this.qq=qq;
6. this.user=user;
7. }
8. public int qq;//QQ号
9. public QQUser user;//QQ用户
10. public QQNode next;//下一个QQ节点对象
11. public LinkQueue lq;//队列
12. public LinkQueue getLq() {
13. return lq;
14. }
15. public void setLq(LinkQueue lq) {
16. this.lq = lq;
17. }
18. public int getQq() {
19. return qq;
20. }
21. public void setQq(int qq) {
22. this.qq = qq;
23. }
24. public QQUser getUser() {
25. return user;
26. }
27. public void setUser(QQUser user) {
28. this.user = user;
29. }
30. public QQNode getNext() {
31. return next;
32. }
33. public void setNext(QQNode next) {
34. this.next = next;
35. }
36. }

package cn.netjava.hash;

public class QQNode {

        //构造器：传入QQ号，QQ用户对象
	public QQNode(int qq,QQUser user){
		this.qq=qq;
		this.user=user;
	}

	public int qq;//QQ号
	public QQUser user;//QQ用户
	public QQNode next;//下一个QQ节点对象
	public LinkQueue lq;//队列

	public LinkQueue getLq() {
		return lq;
	}
	public void setLq(LinkQueue lq) {
		this.lq = lq;
	}
	public int getQq() {
		return qq;
	}
	public void setQq(int qq) {
		this.qq = qq;
	}
	public QQUser getUser() {
		return user;
	}
	public void setUser(QQUser user) {
		this.user = user;
	}
	public QQNode getNext() {
		return next;
	}
	public void setNext(QQNode next) {
		this.next = next;
	}

}

Hash方法类

1. package cn.netjava.hash;
2. public class QQHash {
3. private QQNode[] table=new QQNode[100];
4. private float load=0.75F;//装载因子
5. private int count=0;
6. private int gain=100;
7. public static void main(String args[]){
8. QQHash qqHash=new QQHash();
9. QQUser user1=new QQUser();
10. user1.setUserName("用户一");
11. user1.setPassWord("1");
12. user1.setAge(20);
13. user1.setSex("女");
14. qqHash.put(1, user1);
15. QQUser user2=new QQUser();
16. user2.setUserName("用户二");
17. user2.setPassWord("12");
18. user2.setAge(20);
19. user2.setSex("男");
20. qqHash.put(2, user2);
21. QQUser user3=new QQUser();
22. user3.setUserName("用户三");
23. user3.setPassWord("123");
24. user3.setAge(20);
25. user3.setSex("男");
26. qqHash.put(3, user3);
27. QQUser user4=new QQUser();
28. user4.setUserName("用户四");
29. user4.setPassWord("1234");
30. user4.setAge(20);
31. user4.setSex("女");
32. qqHash.put(101, user4);
33. qqHash.returnQQNode();
34. user1=qqHash.get(1);
35. user2=qqHash.get(2);
36. user3=qqHash.get(3);
37. user4=qqHash.get(101);
38. QQNode[] table=qqHash.returnQQNode();
39. //      System.out.println("表的长度为   "+table.length);
40. qqHash.returnTabLen();
41. for(int i=0;i<table.length;i++){
42. if(table[i]!=null){
43. System.out.println("实际存在的Table["+i+"]的值"+table[i].getQq());
44. LinkQueue lq=table[i].getLq();
45. if(lq.getLength()>0){
46. System.out.println("存在挂链");
47. for(int j=0;j<lq.getLength();j++)
48. System.out.println("挂链第"+i+"个值为"+((QQNode)lq.getLinkNode(i).getData()).getUser().getUserName());
49. }
50. }
51. }
52. }
53. /**
54. * 存放QQ及用户
55. * @param qq:QQ号
56. * @param user：QQ用户
57. */
58. public void put(int qq,QQUser user){
59. //判断己放对象的个数和table的长度比是否达到装载因子,
60. //如果超过,则reHash一次,增长,
61. //然后再放!
62. float rate=(float)count/table.length;
63. if(rate>=load){
64. QQNode[] table1=new QQNode[table.length+gain];
65. for(int i=0;i<table.length;i++){
66. QQNode q=table[i];
67. int qqnum=q.getQq();
68. QQUser u=q.getUser();
69. int qqhash=hashQQ(qqnum);
70. q.setQq(qqnum);
71. q.setUser(user);
72. table1[qqhash]=q;
73. }
74. table=table1;
75. }
76. System.out.println("table长度："+table.length);
77. //判断是否存在hash冲突
78. boolean judge=exist(qq);
79. System.out.println("是否存在冲突"+judge);
80. int index=hashQQ(qq);
81. System.out.println("hash值"+index);
82. if(judge){//不存在hash冲突，直接将qq和用户存放在通过hash函数获得的地址中
83. QQNode q=new QQNode(qq,user);
84. q.setQq(qq);
85. q.setUser(user);
86. table[index]=q;
87. count++;
88. }
89. else{//存在hash冲突
90. QQNode q=new QQNode(qq,user);
91. q.setQq(qq);
92. q.setUser(user);
93. System.out.println("   "+q.getQq()+"  "+q.getUser());
94. LinkQueue lq=q.getLq();
95. lq.InsertLinkNode(q);
96. for(int i=0;i<lq.getLength();i++)
97. System.out.println("======"+((QQNode)lq.getLinkNode(i).getData()).getQq());
98. if(lq.getLength()==0){
99. table[index].setNext(q);
100. }
101. }
102. }
103. /**
104. * 根据QQ号取得QQ用户信息
105. * @param qq：QQ号
106. * @return:QQ用户
107. */
108. public QQUser get(int qq){
109. int index=hashQQ(qq);
110. QQNode q=table[index];
111. System.out.println("节点"+q.getQq());
112. //看是否有下了个节点,如有,则是冲突的,就要一个一个比较
113. if(q.next==null)
114. return q.getUser();
115. LinkQueue lq=q.getLq();
116. for(int i=0;i<lq.getLength();i++){
117. QQNode aa=(QQNode)lq.getLinkNode(i).data;
118. int qqq=aa.getQq();
119. if(qqq==qq)
120. System.out.println("查找到了！");
121. return aa.getUser();
122. }
123. return null;
124. }
125. //计算QQ号的has值,自定义has函数
126. private int hashQQ(int qq){
127. return qq%table.length;
128. }
129. //判断是否存在hash冲突
130. private boolean exist(int qq){
131. int qqhash=hashQQ(qq);
132. if(table[qqhash]!=null)
133. return false;
134. return true;
135. }
136. //返回表
137. private QQNode[] returnQQNode(){
138. System.out.println("已存在数据个数为"+count);
139. return this.table;
140. }
141. //返回表中实际存在的数据的个数
142. private int returnTabLen(){
143. return this.count;
144. }
145. }

http://1029975378-qq-com.iteye.com/blog/814552