一、导引
考虑下面这样一个例子：如果数据中存在重复的元素，请给出输出第一个重复字符的算法。最简单最直接的办法当然是：在给定的字符串中，检查每个字符是否重复。这种方法的时间复杂度为O(n^2)。
现在给出一个更好的解决方案：我们知道可能的字符集合大小是256(为了简单期起见，假设只有ASCII字符)。由此创建一个长度为256的数组，并将其所有元素初始化为0。将每个输入字符放到该数组对应的位置，并增加其计数。由于使用的是数组，所以它仅需要常数时间就可以到达任意指定的位置。当扫描输入字符时，若得到了一个计数器值已经是1的字符，则可以认为该字符就是第一个重复的字符。
char FirstRepeatedChar(char[] str){
int count[256];
for(int i=0;i<256;++i)
count[i] = 0;
for(int i=0;i<str.length;++i){
if(count[str[i]]==1){
System.out.println(str[i]);
break;
}
}
if(i==len)
System.out.println("No Repeated Characters");
return 0;
}
但是如果我们给定的数组是数字而不是字符，那么关键字的取值范围将为无穷大(字符的个数是256是已知的，但是数字的范围是未知的)。使用简单的数组来解决那些关键字取值范围巨大的问题并不是一个正确的选择。所以要想解决这个问题，则需要以某种方式将所有这些可能的关键字映射到可能的内存位置，将关键字映射到存储位置的过程成为散列。
二、散列表的简介
Java中最底层的数据存储方式有两种，一种是数组，另一种就是链表。数组查询速度快，但是增加和删除元素速度慢；链表则正好相反。有没有一种数据结构能够综合一下数组和链表，以便发挥它们各自的优势呢？答案就是散列表！散列表也叫作哈希表，哈希表有较快的查询速度，以及较快的增删速度，所以很适合在海量数据的环境中使用。
一般实现哈希表的方法采用“拉链法”，我们可以理解为“链表的数组”，如下图：
从上图我们可以发现哈希表是由数组+链表组成的。当我们面临较少的存储位置和较多可能的关键字时，仅利用简单数组是没有足够的内存空间的。一种解决方案就是使用散列表。散列表是一种数据结构，利用散列函数将关键字映射到其关联的值。
三、散列函数
一个好的散列函数应该具有以下特点：
- 最大限度地减少冲突
- 简单并快速计算
- 将键值在散列表中均匀分布
- 能使用关键字提供的所有信息
- 对一组给定关键字具有一个高负载因子
其中负载因子=散列表中元素的个数 / 散列表的长度，此参数指出了散列函数是否将关键字均匀分布
四、冲突
冲突是指两个记录存储在相同位置的情况。目前解决冲突最常用的是直接链接法和开放定址法。
- 直接链接法：链表数组的应用
分离链接法 - 开放定址法：基于数组实现
线性探测法(线性搜索)
二次探测法(非线性搜索)
双重散列法(使用两个散列函数)
(1)分离链接法
基于链接法的冲突解决方案是将散列表与链表形式结合起来实现的。当两个或多个记录散列到相同的位置时，这些记录将构成一个单项链表。
(2)开放定址法
这种方法是通过探测来解决冲突的。
1.线性探测法
探测间隔为固定值1。在线性探测中，从发生冲突的原始位置按顺序搜索散列表，如果表中的某个位置被占据，则查找下一个位置。必要时，还可以从表的最后一个位置循环到表的第一个位置进行搜索。用于再次散列的函数如下：
rehash(key) = (n+1)%tablesize
线性探测的一个问题是，表项往往在散列表中聚集，集散列表包含一组连续的被占据的位置，这一现象称为聚集。因此，散列表中的某部分可能相当密集，即使另一部分元素相对较少。因此聚集会导致较长的探测搜索，从而降低整体效率。
2.二次探测法
探测间隔的增加与散列值成正比(因此间隔线性地增加，索引值由一个二次函数描述)。在二次探测中，从发生冲突的初始位置i开始，如果某个位置被占据，则探测i+1^2、i+2 ^2 、i+3^2、i+4 ^2等位置。如果有必要，将从表的最后一个位置循环到表的第一个位置进行探测。再次散列的函数如下：
rehash(key) = (n+k^2)%tablesize
【例子】
表长是11(0..10)；散列函数：h(key) = key mod 11
31 mod 11 = 9
19 mod 11 = 8
2 mod 11 = 2
13 mod 11 = 2 → (2+1^2)mod 11 = 3
25 mod 11 = 3 → (3+1^2)mod 11 = 4
24 mod 11 = 2 → (2+1^2)mod 11 , (2+2^2)mod 11 = 6
聚集问题可以使用二次探测方法消除。但是还是存在出现聚集的可能。聚集是由多个关键字映射到同一个散列值引起的，所以与这些关键字相关的探测序列将随着重复冲突的出现而被延长。
3.双重散列法
探测间隔由另一个散列函数计算生成，双重散列法用一种更好的方式减少了聚集。由于探测序列的增量使用第二个散列函数计算，所以第二个散列函数h2应遵循：
h2(key)≠0且h2≠h1
算法首先探测位置h1(key)。若该位置已被占据，那么继续探测位置h1(key)+h2(key)，h1(key)+2×h2(key)....。
【例子】
表长是11(0..10)
散列函数：假设h1(key) = key mod 11、h2(key) =7- (key mod 7)
插入关键字：
58 mod 11 = 3
14 mod 11 = 3 → (3+7) mod 11 =10
91 mod 11 = 3 → (3+7) mod 11 , (3+2×7) mod 11=6
25 mod 11 = 3 → (3+3) mod 11 , (3+2×3) mod 11 = 9
五、哈希的应用
Java的每个类都有hashCode方法，hashCode方法返回该对象的哈希码值。
那么为什么对象都要有hashCode方法呢？考虑一种情况，当向集合中插入对象时，如何判别在集合中是否已经存在该对象了？也许大多数人都会想到调用equals方法来逐个进行比较，这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据，如果采用equals方法去逐一比较，效率必然是一个问题。此时hashCode方法的作用就体现出来了，当集合要添加新的对象时，先调用这个对象的hashCode方法，得到对应的hashcode值来进行重复的判断。所以，之所以有hashCode方法，是因为在批量的对象比较中，hashCode要比equals来得快。
两个对象equals相等那么hashcode是一定相等的；equals不相等hashcode可能相等可以不相等。因为hashCode说白了是地址值经过一系列的复杂运算得到的结果，而Object中的equals方法底层比较的就是地址值，所以equals()相等，hashCode必定相等；equals()不等，在java底层进行哈希运算的时候有一定的几率出现相等的hashCode，所以hashCode可等可不等。
如果你重写了equals()方法，那么一定要记得重写hashCode()方法。重写的原则就是按照equals( )中比较两个对象是否一致的条件用到的属性来重写hashCode()。
// HASH
@Override
public int hashCode()
{
int hash = 17;
//根据id生成hashCode
if (this.id != null)
hash = hash * 31 + this.id.hashCode();
return(hash);
}
@Override
public boolean equals(Object o)
{
if (this == o)
return(true);
//利用getClass()获得当前对象的类型
if (o==null || !this.getClass().equals(o.getClass()))
return(false);
C c = (C)o;
//通过id判断两个对象是否相等
return(
(this.id == c.id) ||
(this.id != null && this.id.equals(c.id))
);
}
