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中有些方法、类被划了横杠
-
解答：
