大家好，我是讯享网，很高兴认识大家。

简单来说查找算法，就是判断现有数据集合中是否有这个元素，或者是否有满足条件的元素。其中的 Hash 算法（散列表）则可以帮助我们判断是否有这个元素，虽然功能简单，但人家性能高啊。通过在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。相比普通的查找算法来说，仅仅在比较的环节，就会大大减少查找或映射所需要的时间。

判断这个字符串有没有出现过、出现过多少次时可以用哈希。

哈希表（散列表）

采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间即称为散列表。下面用一张图给大家展示一下散列表的实现过程：
讯享网

可以理解为数学函数，Y=F(X)，X 为自变量也就是这里的 Key, F( ) 对应图中的 H( )，也就是一个映射关系，Y 因变量也就是对应的值的 存放位置

散列既是一种查找技术，也是一种存储技术。散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，即通过关键码能推出 Key 值，但是通过关键码对应的值（即位置处的值）不能推出关键码，所以散列存储的关键码和值之间并不对称，因此散列主要是面向查找的存储结构 

散列表的缺陷

散列表并不是适用于所有的需求场景。

• 散列技术一般不适合在允许多个记录有同样关键码的情况下使用。

因为这种情况下，通常会有冲突存在，将会降低查找效率，体现不出散列表查找效率高的优点。

并且如果一定要在这个情况下使用的话，还需要想办法消除冲突，这将花费大量时间，那么就失去了 O(1) 时间复杂度的优势，所以在存在大量的冲突情况下，我们就要弃用散列表。

• 散列方法也不适用于范围查找，比如查找最大值或者最小值

因为散列表的值是类似函数的，映射函数一个变量只能对应一个值，不知道其他值，也不能查找最大值、最小值，RMQ(区间最值问题）可以采用 ST 算法、树状数组和线段树解决。

• 也不可能找到在某一范围内的记录

比如查找小于 N 的数有多少个，是不能实现的，原因也是映射函数一个变量只能对应一个值，不知道其他值。

散列技术的关键问题
在使用散列表的时候，有两个关键的技术问题需要解决：

1. 散列函数的设计，如何设计一个简单、均匀、存储利用率高的散列函数？
2. 冲突的处理，如何采取合适的处理冲突方法来解决冲突。

如何设计实现散列函数

在构建散列函数时，我们需要秉持两个原则：

• 简单

散列函数不应该有很大的计算量，否则会降低查找效率。

• 均匀：

函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。

散列函数实现三种方法

1. 直接定址法。

散列函数是关键码（Key）的映射的线性函数，形如：H(key) = a * key + b

如果关键码的集合已知且为 [11,22,33,66,88,44,99]

H(key) = 1/11 * key + 0

 缺点：

• 我们是看到了这个集合，然后想到他们都是 11 的倍数才想到这 Hash 函数。我们在平常的使用中一般不会提前知道 Key 值集合，所以使用较少。

适用范围：

• 事先知道关键码，关键码集合不大且较为连续而不离散。

 2. 除留余数法。

H(key)=key mod p 

讯享网

代码实现：

讯享网 final Integer MOD=P; Integer Hx(int n) { return n%MOD; } 

 如果p=21，key={14，21，28，35，42，44，49，56}，则：

可以发现产生了很多相同的 H(Key)，这就是发生冲突，因为一个位置只能放一个数，有两个值对应这里一个位置，是不可以的。

这种方法是最常用的方法，这个方法的关键在于如何选取 P，使得利用率较高并且冲突率较低，一般情况下，我们会选取最接近表长且小于等于表长的最大素数。

缺点：

P 选取不当，会导致冲突率上升。

适用范围：

除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。

这个方法非常常用，后面题目的展开就是使用的这个方法。在大部分的算法实现中也都是选取的这一种方式。

3. 数字分析法。

比如将集合全部转化为 16 进制数，根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。或者将 N 位 10 进制数，观察各各位的数字分布，选取分布均匀的散列地址。

首先我们考虑一位作为散列函数，发现都是很多冲突，选取两位时，百位和十位组合最适宜，分布均匀且没有冲突。

当然，我们说的是这一方法的一个具体实列，既然叫做数字分析法，那么只有对于不同数据的不同分析，才能写出更是适配的 H(x)。

另外还有两种平时使用极少的方法，分别是平方取中法和折叠法

冲突的处理方法 

1. 开散列方法：

open hashing 也称为拉链法，separate chaining 称为链地址法，简单来说，就是由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。

寻找下一个空的散列地址的方法：

• 线性探测法

当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。

对于键值 key，设 H(key)=d，闭散列表的长度为 m，则发生冲突时，寻找下一个散列地址的公式为：

Hi=(H(key)＋di) MOD m（di=1，2，...，m−1）

堆积现象：

在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。

Key 集合为 47, 7, 29, 11, 27, 92, 22, 8, 3。

P 值为 11，进行 Hash 映射，采用线性探测法处理冲突。

47 mod 11=3所以对应3的位置，7 mod 11=7所以对应7的位置，以此同理类推，但是29 mod 11=7也应该放7的位置，可是此前7的位置已经有元素了，所以线性探索发现下一个位置有空，故将29放在对应8的位置 。其余同理。3 mod 11=3但是3的位置有元素，线性探索接下来的位置（4、5）发现都有，继续直到发现空位置——对应6的位置，所以3对应6的位置。

• 二次探测法

即当发生冲突时，寻找下一个散列地址的公式为：

   Hi​=(H(key)＋di​)

其中（di​=1^2，(-1)^2，2^2，(-2)^2，...，q^2，(-q)^2且q≤m/2）

• 随机探测法

当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：

Hi=(H(key)+round)

其中 round 为随机数

• 再 hash 法

注意：用开放定址法处理冲突得到的散列表叫闭散列表。

        1.闭散列方法

closed hashing 也称为开地址方法，open addressing 开放地址法，开放地址法中涵盖了以下两种实现方式；

• 拉链法（链地址法）

  将所有散列地址相同的记录即 Key 值相同的项目，坠成一个链表，每个链表的头指针存放位置为 Key 值对应的位置。

依旧以key={47，7，29，11，27，92，22，8，3}为例：

        2.建立公共溢出区 

散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。

查找时，如果在基本表里找的到就返回成功，没找到就在溢出区顺序查找，注意这里不再是映射而是顺序查找，放置时也是按照顺序的方式。

依旧以key={47，7，29，11，27，92，22，8，3},散列函数为H（key）=key mod11 为例：

算法流程：

1.假设给定的值为 K，根据所设定的散列函数 h，计算出散列地址 h(K)；

2.如果将该地址中的值与 K 比较，若相等则检索成功，跳转到第 5 步；

3.否则，按建表时设定的处理冲突方法查找探查序列的下一个地址,反复执行并检查

        如果某个地址空间未被占用（查找不成功，可以插入），跳转到第 5 步；

        如果关键码比较相等（有重复记录，不需要插入）为止 ，跳转到第 5 步；

4.如果探测完整个 hash 表，都没有进行插入或查找失败，跳转到第 5 步；

5.end 算法结束。

公共溢出区的方式更加简洁高效率（在冲突次数远小于元素数量时）

弗里的语言

小发明家弗里想创造一种新的语言，众所周知，发明一门语言是非常困难的，首先你就要克服一个困难就是，有大量的单词需要处理，现在弗里求助你帮他写一款程序，判断是否出现重复的两个单词。

输入描述

第 1行，输入 N，代表共计创造了多少个单词。

第 2行至第 N+1 行，输入 N个单词。

1≤N≤10^4，保证字符串的总输入量不超过 10^6。

输出描述

输出仅一行。若有重复的单词，就输出重复单词，没有重复单词，就输出 NO，多个重复单词输出最先出现的。

样例 1：

输入： 
6
1fagas 
dsafa32j
lkiuopybncv
hfgdjytr
cncxfg
sdhrest

---

样例 2：

输入： 
5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds

首先我们需要创建一个散列表和一个公共溢出区。

这里用，这是因为我们需要用尽可能大的质数，并且依据题意不超过 10^6。把h设置的很大是为了避免出现冲突。

 再定义散列表映射函数。

这里介绍一种在算法竞赛中特别常用的字符串映射成数字的方式。

实现原理：

1. 将字符串中的每一个字母都看做是一个数字（例：从 a-z ，视为 1-26 ）；
2. 选取两个合适的互质常数 b 和 h，其中 h 要尽可能的大一点，为了降低冲突的概率。b 常用 131，h 常用 1e9+7，这里我们需要设置公共溢出区所以，我们需要随便找一个 string 数组能开出来的数字，这里选取 。
3. 定义哈希函数：

H(C)=[ c1*b^(m-1) + c2*b^(m-2) + . . . + cm*b^0 ] mod h

处理方式：

1. C 代表一个字符串，用 C =c1 c2 c3 c4..cm 表示该字符串，其中 ci 表示从前向后数的第 i 个字符；
2. C 当做 b 进制数 来处理，b 是基数；
3. 关于对 h 取模，若 b、h 有公因子，那么不同的字符串取余之后的结果发生冲突的几率将大大大增加（冲突：不同的字符串但会有相同的 hash 值）。

现在有一字符串 S=s1​s2​s3​s4​s5​

​hash[1]=s1​

hash[2]=s1∗p+s2

hash[3]=s1∗p2+s2∗p+s3

hash[4]=s1∗p3+s2∗p2+s3∗p+s4

5hash[5]=s1∗p4+s2∗p3+s3∗p2+s4∗p+s5

所以S 的哈希值为 Hash[5]。

但是java有hash函数，可以直接用：(s.hashCode()%h+h)%h；

Java的hashcode有点厉害，好长一大串数，会比我们设定的h还要大好多，所以要先取模，让它变成一个绝对值比h小的数。同时如果出现字符的时出现了比'a'小的数话会出现负数，所以要再加上h让它成为正数再取模。（放心，加了h后对h取模值不会变的）

定义查询函数

一开始我们建立了字符串类型的数组Value，把每个字符串映射到里面去。如果是空的，说明它不在我们的哈希表里，如果存在了且值等于s就说明查到了，如果值不等于s说明映射过来了，但是发生了冲突，要去溢出表里查。溢出区是顺序存放的，遍历以下就好，找不到就说明不存在。

 定义插入散列表函数。

 代码如下：

import java.util.Scanner; import java.util.Stack; public class Main { static final int h=; static String[] Value=new String [h];//哈希表 static String[] UpValue=new String [h];//Value表的公共溢出区 static int UpValueCount=0;//公共溢出区的下标 static int Hx(String s) { return (s.hashCode()%h+h)%h; } static boolean isAt(String s) { int n=Hx(s); if(Value[n]==null) return false; else if(Value[n].equals(s)) return true; else { for(int i=0;i<UpValueCount;i++) if(UpValue[i].equals(s)) return true; return false; } } static boolean in(String s) { int n=Hx(s); if(Value[n]==null) { Value[n]=s; return true; } else if(Value[n].equals(s)) return false; else { for(int i=0;i<UpValueCount;i++) if(UpValue[i].equals(s)) return false; UpValue[UpValueCount++]=s; return true; } } public static void main(String[] args) { int n; boolean flag=false; Scanner in=new Scanner(System.in); String ans="NO"; n=in.nextInt(); for(int i=0;i<n;i++) { String word; word=in.next(); // System.out.println(Hx(word)); if(flag) continue; if(isAt(word)){ flag=true; ans=word; } else { in(word); } } System.out.println(ans); } }