写在前面

       顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O( )，搜索的效率取决于搜索过程中元素的比较次数。
       理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

当向该结构中：
插入元素

根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放

搜索元素

对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)

哈希冲突

对于两个数据元素的关键字 和 (i != j)，有 != ，但有：Hash(i ) == Hash(j )，
即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞.

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

发生哈希冲突该如何处理呢？

哈希冲突解决

解决哈希冲突两种常见的方法是：闭散列和开散列

1.闭散列的实现

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，
那么可以把key存放到冲突位置中的“下一个” 空位置中去。

那如何寻找下一个空位置呢？

类的成员变量：

private:
	vector<elem> _ht;
	int _size;
/

enum  state{
	empty,
	exist,
	deleted

};

typedef struct elem{

		pair<K, V> val;
		state sta;

	}elem;

//1.闭散列
#include<map>
#include<vector>
#include<utility>
#include<iostream>
using namespace std;



const int PRIMECOUNT = 28;
const size_t primeList[PRIMECOUNT] =
{
	53ul, 97ul, 193ul, 389ul, 769ul,
	1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
	49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
	1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
	50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
	1610612741ul, 3221225473ul, 4294967291ul
};

enum  state{
	empty,
	exist,
	deleted

};


template<class K,class V>

class hash_1{

typedef struct elem{

		pair<K, V> val;
		state sta;

	}elem;


public:

	hash_1(int n = 3)
		:_size(0)
		, _ht(n)
	{
		for (int i = 0; i < _ht.capacity(); ++i){
		
			_ht[i].sta = empty;
		}
	
	}
	
	bool insert(const K& key){
	
		check_capacity();

		size_t _hashaddr = hash_func(key);
		pair<K, V>_val = { key, _hashaddr };     //pair类型的变量初始化
		size_t _start = _hashaddr;
		while (_ht[_hashaddr].sta == exist)
		{
			if (_ht[_hashaddr].sta == exist && _ht[_hashaddr].val.first == key)
				return false;

			_hashaddr++;
			if (_hashaddr == _ht.capacity())
				_hashaddr == 0;
		
			if (_hashaddr == _start)
				return false;
		    	
		
		}
	

	//如果为空，可以直接插入
		_ht[_hashaddr].val = _val;
		_ht[_hashaddr].sta = exist;
		++_size;
		return true;
	}

	void check_capacity(){
	 
		//增容的条件是： α>=0.7
		if (_size*10/_ht.capacity()>=7){
			hash_1<K, V>newht(getnextprime(_ht.capacity()));
             
			for (int i = 0; i < _ht.capacity(); ++i){
				if (_ht[i].sta == exist){
				
					newht.insert(_ht[i].val.first);
				}
				
			
			}

			Swap(newht);
		
		}
	
	
	}

	int getnextprime(size_t n){
	   
		for (int i = 0; i < PRIMECOUNT; ++i){
			if (primeList[i]>n)
				return primeList[i];
		}
		
		return 0;
	
	}

	



	int find(const K& key){
	//如果找到了，返回下标；没有找到就打印“不存在”;
		int _hashaddr = hash_func(key);
		size_t start = _hashaddr;
	
		while ( _ht[_hashaddr].sta != empty ){
		
			if (_ht[_hashaddr].sta == exist && _ht[_hashaddr].val.first == key)
				return _hashaddr;
		
			++_hashaddr;

			if (_hashaddr == _ht.capacity()){
				_hashaddr = 0;
			}
			if (_hashaddr == start)
			{
				cout << "不存在" << endl;
				return -1;
			}
		
		
		}
		cout << "不存在" << endl;
		return -1;
	}

	void erase(const K& key){
		
		int index = find(key);
		if (index != -1){

			_ht[index].sta = deleted;
			++_size;

		}
        
		return;
	
	}
	void Swap(hash_1<K, V>& ht){
		swap(_ht, ht._ht);
		swap(_size, ht._size);
		

	}


private:	
 size_t hash_func(const K& key){

		return key % _ht.capacity();
	}


private:
	vector<elem> _ht;
	int _size;
	
};

2.开散列的实现

开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，
具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，
各链表的头结点存储在哈希表中。

类的成员变量：

private:
		vector<Node *> _ht;                    
		size_t _size;        
///

template<class v>

struct node{

	node(const v& data)
	:_val(data),
	_pnext(nullptr)
	
	{}

	int _val;
	node<v>* _pnext;

};

    typedef node<V> Node;
	typedef node* PNode;

//哈希---开散列--哈希桶

//开散列的实现

template<class v>

struct node{

	node(const v& data)
	:_val(data),
	_pnext(nullptr)
	
	{}

	int _val;
	node<v>* _pnext;

};



template<class V, class HF = DefHashF<T> >
class HashBucket
{
	typedef node<V> Node;
	typedef node* PNode;

public:
	//构造函数
	HashBucket(size_t capacity = 3)
		: _size(0)
	{
		_ht.resize(GetNextPrime(capacity), nullptr);
	}

	//哈希桶中的元素插入----- 哈希桶中的元素不能重复
	PNode* Insert(const V& data)
	{
		// 确认是否需要扩容。。。
		// _CheckCapacity();

		// 1. 计算元素所在的桶号
		size_t bucketNo = HashFunc(data);

		// 2. 检测该元素是否在桶中
		PNode pCur = _ht[bucketNo];
		while (pCur)
		{
			if (pCur->_data == data)
				return pCur;

			pCur = pCur->_pNext;
		}

		// 3. 插入新元素
		pCur = new Node(data);

		// 采用头插法插入，效率高
		pCur->_pNext = _ht[bucketNo];
		_ht[bucketNo] = pCur;
		_size++;

		return pCur
	}


	// 删除哈希桶中为data的元素(data不会重复)，返回删除元素的下一个节点
	PNode* Erase(const V& data)
	{
		size_t bucketNo = HashFunc(data);
		PNode pCur = _ht[bucketNo];
		PNode pPrev = nullptr;
		//PNode pRet = nullptr;

		while (pCur!=nullptr && pCur->_val!=data)
		{
			
			pPrev = pCur;
			pCur = pCur->_pnext;
			
		}

		//要删除的节点不存在
		if (pCur == nullptr)
			return nullptr;
		//如果是头删
		if (pPrev == nullptr){	
		_ht[bucketNo] = pCur->_pnext;
		return _ht[bucketNo];
		
		}

		//数据存在，并且非首元素 
		pPrev->_pnext = pCur->_pnext;
		return pPrev->_pnext;
	
	}

	// 查找data是否在哈希桶中
	PNode Find(const V& data)
	{
		size_t bucketNo = HashFunc(data);
		PNode pCur = _ht[bucketNo];

		while (pCur)
		{
			if (pCur->_data == data)
				return pCur;

			pCur = pCur->_pNext;
		}

		return nullptr;
	}

	size_t Size()const
	{
		return _size;
	}

	bool Empty()const
	{
		return 0 == _size;
	}

	void Clear()
	{
		for (size_t bucketNo = 0; bucketNo < _ht.capacity(); ++bucketNo)
		{
			PNode pCur = _ht[bucketNo];
			while (pCur)
			{
				PNode pNext = pCur->_pNext;
				delete pCur;
				pCur = pNext;
			}
		}

		_size = 0;
	}

	bool BucketCount()const
	{
		return _ht.capacity();
	}


	
	void Swap(HashBucket<V, HF>& ht)
	{
		swap(_ht, ht._ht);
		swap(_size, ht._size);
	}

	~HashBucket()
	{
		Clear();
	}


	/*桶的个数是一定的，随着元素的不断插入，每个桶中元素的个数不断增多，极端情况下，可能会导致一
		个桶中链表节点非常多，会影响的哈希表的性能，因此在一定条件下需要对哈希表进行增容，那该条件
		怎么确认呢？开散列最好的情况是：每个哈希桶中刚好挂一个节点，再继续插入元素时，每一次都会发
		生哈希冲突，因此，在元素个数刚好等于桶的个数时，可以给哈希表增容。*/

	void _CheckCapacity(){

		size_t bucketCount = BucketCount();

		if (_size == bucketCount){

			//增容
			HashBucket<V, HF> newHt(getnextprime(_ht.capacity()));
			for (int i = 0; i < newHt._ht.capacity; ++i)
				newHt._ht[i] = nullptr;


			for (int j = 0; j < _ht.capacity(); ++j){

				PNode cur = _ht[j];
				int hashNo = -1;
				while (cur){

					//取旧哈希桶i号桶的第一个节点
					_ht[j] = cur->_pnext;		//头删
					//计算当前节点在新空间的桶号
					hashNo = newHt.HashFunc(cur->_val);	//计算在那个哈希桶中
					//头插法将该节点插入新空间
					cur->_pnext = newHt[hashNo];//连接新桶中的内容
					newHt[hashNo] = cur;//将给定的第一个节点放入新空间
					//取旧哈希桶i号桶的第next个节点
					cur = ht[j]//cur取原链表中的下一个节点
				}
			}

		}
		newHt._size = _size;
		this->Swap(newHt);
	}

	


	private:
		size_t HashFunc(const V& data)
		{
			return HF()(data) % _ht.BucketCount();
		}

	private:
		vector<Node *> _ht;                    
		size_t _size;                             // 哈希表中有效元素的个数

	};

开散列与比散列比较：
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

简单来说查找算法，就是判断现有数据集合中是否有这个元素，或者是否有满足条件的元素。其中的 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

输出：
NO

---

样例 2：

输入： 
5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds

输出：
sdfggfds

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

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

 再定义散列表映射函数。

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

实现原理：

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

    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);
    }

}