哈希表 -- 学习笔记day2

一、哈希表的定义

（1）哈希表是根据关键字进行访问的数据结构。

（2）哈希表建立了一种关键字和存储地址之间的映射关系，使每一个关键字与结构中唯一的存储位置相对应。

（3）在理想情况下，在哈希表中进行查找的时间复杂度为O(1),即与表中的元素数量无关。

二、哈希函数

1.在了解哈希函数之前，先来回顾一下之前的一个练习：

    练习题一：统计一下字符串“sahgcxvhgc”中，每一个字符出现的次数，字符串只包含小写字母。

#include<iostream>
#include<string>
using namespace std;

string s;
int cnt[26];

int main()
{
cin >> s;
for(auto ch:s)
{
cnt[ch – \’a\’]++;
}
for(int i=0;i<26;i++)
{
if(cnt[i]) cout << (char)(i+\’a\’) << \” 的个数为：\” << cnt[i] << endl;
}
return 0;
}

运行结果：

2.哈希函数就是将关键字映射成对应的地址的函数。记作：hash(key) = address.

结合上面的这个练习题来看，ch – \’a\’ 就是一个哈希函数，记作：hash(key) = key – \’a\’ . 

回过来再看：

哈希函数就是这个映射关系；交给哈希函数一个关键字，哈希函数给我们计算出一个存储位置。 

三、哈希冲突

1.哈希冲突：哈希函数可能会把两个或两个以上的不同关键字映射到同一地址，这种情况称为哈希冲突。起冲突的不同关键字，把它们称为同义词。

2.举例说明：

练习题二：给一个数组{1,3,17,1000000007,49,49,1000000007}，记录每个数字出现的次数。

思想：设计一个哈希函数：hash(key) = key % 7;