20162325 2017-2018-2 《程序设计与数据结构》第11周学习总结

教材关键概念摘要

在哈希方法中，元素保存在哈希表中，其在表中的位置由哈希函数确定。

两个元素或关键字映射到表中同一个位置的情形，称为冲突。

将每个元素映射到表中唯一位置的哈希函数称为理想哈希函数。

抽取仅适用元素值或关键字中的一部分来计算保存元素的位置。

在移位折叠方法中，将关键字的各部分加在一起计算下标。

将字符串中各字符按二进制格式进行处理，长度依赖方法和平方取中方法也适用于字符串。

虽然Java为所有的对象提供了hashcode方法，最好还是为特定的类定义一个具体的哈希函数。

处理冲突的链式方法，将哈希表看成是集合的表而不是各独立单元的表。

处理冲突的开放地址方法，即在表中寻找不同于该元素初次哈希到的另一个开放的位置。

装载因子是哈希表扩展之前，表中允许的最大占有百分比。

哈希方法

HashCode是返回对象的哈希码。跟HashMap和Hashtable没多大关系。

HashTable是方法是同步的，HashMap不是。

HashMap中可以存在一条key或value为空的记录，Hashtable不可以。

HashTable继承自Dictionary,HashMap继承自Map接口。

HashCode

在Java中，哈希码代表对象的特征。

　　例如对象 String str1 = “aa”, str1.hashCode= 3104

　　String str2 = “bb”, str2.hashCode= 3106

　　String str3 = “aa”, str3.hashCode= 3104

　　根据HashCode由此可得出str1!=str2,str1==str3

　　哈希码产生的依据：哈希码并不是完全唯一的，它是一种算法，让同一个类的对象按照自己不同的特征尽量的有不同的哈希码，但不表示不同的对象哈希码完全不同。也有相同的情况，看程序员如何写哈希码的算法。

　　下面给出几个常用的哈希码的算法。

　　1：Object类的hashCode.返回对象的内存地址经过处理后的结构，由于每个对象的内存地址都不一样，所以哈希码也不一样。

　　2：String类的hashCode.根据String类包含的字符串的内容，根据一种特殊算法返回哈希码，只要字符串内容相同，返回的哈希码也相同。

　　3：Integer类，返回的哈希码就是Integer对象里所包含的那个整数的数值，例如Integer i1=new Integer(100),i1.hashCode的值就是100 。由此可见，2个一样大小的Integer对象，返回的哈希码也一样。

类 HashMap<K,V>

 java.lang.Object

  java.util.AbstractMap<K,V>

      java.util.HashMap<K,V>

类型参数：

K - 此映射所维护的键的类型

V - 所映射值的类型

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashCode和HashMap之间的关系

import java.util.HashMap;

public class Test {

	//重写Equals不重写HashCode

	static class Key {

		private Integer id;

		private String value;

		public Key(Integer id, String value) {

			super();

			this.id = id;

			this.value = value;

		}

		@Override

		public boolean equals(Object o) {

			if(o == null || !(o instanceof Key)) {

				return false;

			}else {

				return this.id.equals(((Key)o).id);

			}

		}

	}

	//重写Equals也重写HashCode

		static class Key_ {

			private Integer id;

			private String value;

			public Key_(Integer id, String value) {

				super();

				this.id = id;

				this.value = value;

			}

			@Override

			public boolean equals(Object o) {

				if(o == null || !(o instanceof Key_)) {

					return false;

				}else {

					return this.id.equals(((Key_)o).id);

				}

			}

			@Override

			public int hashCode() {

				 return id.hashCode();

			}

		}

	public static void main(String[] args) {

		//test hashcode

		HashMap<Object, String> values = new HashMap<Object, String>(5);

		Test.Key key1 =   new Test.Key(1, "one");

		Test.Key key2 =   new Test.Key(1, "one");

		System.out.println(key1.equals(key2));

		values.put(key1, "value 1");

		System.out.println(values.get(key2));

		Test.Key_ key_1 =   new Test.Key_(1, "one");

		Test.Key_ key_2 =   new Test.Key_(1, "one");

		System.out.println(key_1.equals(key_2));

		System.out.println(key_1 == key_2);

		values.put(key_1, "value 1");

		System.out.println(values.get(key_2));

	}

}

由上述例子可见:

只重写了equasl方法的Key类在用做Hash中的键值的时候两个equasl为true的对象不能获取相应的Value的

而重写了hashCode方法和equals方法的key_类两个相等的对象可以获取同一个Value的,这样更符合生活中的逻辑

HashMap对象是根据Key的hashCode来获取对应的Vlaue 因而两个HashCode相同的对象可以获取同一个Value

哈希函数

实际中的Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间，使得数据容易保存。除此以外，Hash函数往往应用于查找上。所以，在考虑使用Hash函数之前，需要明白它的几个限制：

Hash的主要原理就是把大范围映射到小范围；所以，你输入的实际值的个数必须和小范围相当或者比它更小。不然冲突就会很多。
由于Hash逼近单向函数；所以，你可以用它来对数据进行加密。
不同的应用对Hash函数有着不同的要求；比如，用于加密的Hash函数主要考虑它和单项函数的差距，而用于查找的Hash函数主要考虑它映射到小范围的冲突率。

Hash函数应用的主要对象是数组（比如，字符串），而其目标一般是一个int类型。以下我们都按照这种方式来说明。

一般的说，Hash函数可以简单的划分为如下几类：

加法Hash；
位运算Hash；
乘法Hash；
除法Hash；
查表Hash；
混合Hash；

解决冲突

　　

常用的解决hash冲突的方法

开放地址法

拉链法（链地址法）

多重散列法（再哈希法）

公共溢出区法

具体参见【java基础 10】hash算法冲突解决方法 - CSDN博客

从哈希表中删除元素

List

public class Demo {

    public static void main(String[] args) {

        List<Object> obj = new ArrayList<Object>();

        obj.add("a");

        obj.add("b");

        obj.add("c");

        System.out.println("移除前：" + obj.toString());

        Iterator<Object> it = obj.iterator();

        for(int i=0; i<obj.size(); i++){

            System.out.println(i);

            Object name = it.next();

            if("a".equals(name) || "b".equals(name)){

                it.remove();

                i--;

            }

        }

        System.out.println("移除后： " + obj.toString());

    }

Set

public class Demo {

    public static void main(String[] args) {

        Set<Object> obj = new HashSet<Object>();

        obj.add("a");

        obj.add("b");

        obj.add("c");

        System.out.println("移除前：" + obj.toString());

        Iterator<Object> it = obj.iterator();

        for(int i=0; i<obj.size(); i++){

            System.out.println(i);

            Object name = it.next();

            if("a".equals(name) || "b".equals(name)){

                it.remove();

                i--;

            }

        }

        System.out.println("移除后： " + obj.toString());

    }

API中的哈希表

比较常用的有

Hashtable、HashMap、HashSet、HashCode

教材学习中的问题和解决过程

问题1：课堂测试题

问题1解决方案：参考博客教你轻松计算AOE网关键路径（转）
问题2：HashTable和HashMap区别
问题2解决方案：

有七点不同

第一，继承的父类不同。

第二，线程安全性不同。

第三，是否提供contains方法第四，key和value是否允许null值。

第五，两个遍历方式的内部实现上不同。

第六，hash值不同。

第七，内部实现使用的数组初始化和扩容方式不同。

代码调试中的问题和解决过程

问题1：JDK中有些方法、类被划了横杠
解答：

代码托管

上周考试错题总结

活动尚未结束

本周结对学习情况

20162311
结对学习内容

- 如何画AOE网，求关键路径

其他（感悟、思考等，可选）

这周的班级活动和口语考试占用了部分时间，再加上还有团队任务，时间上就很紧张，又是熬夜才完成的博客……然而明天还有当天截止的实验四，感觉有点吃不消。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	58/	1/1	10/10
第二周			8/18
第三周	134/	3/4	12/ 30
第四周		2/6	12/42
第五&六周	750/ 6595	5/11	24/66
第七周	764/7068	7/13	18/84
第八周	888/7956	9/15	20/104
第九周	475/8431	12/18	22/126
第十周	1429/9860	16/22	24/150
第十一周	977/10837	19/25	48/198

计划学习时间: 23小时
实际学习时间: 24小时
改进情况：多思考，多总结

巴特西

20162325 金立清 S2 W11 C20