流离之人追逐幻影

用户名：pwj666

访问量：60215

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

整数散列(补充)和字符串hash初步-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-07-14 03:02:00 浏览：272　|　评论：1　

```
上次学到了题目的每个数都不会超过10^5，因此作为数组下标是可行的，但是输入的数超过10^9,或者是字符串，就不能将他们直接作为数组的下标。
```
```
这样的做法当然存在，那就是散列：将元素通过一个函数转换成整数，使得该整数可以尽量唯一地代表这个元素。这个函数就是 散列函数H。
```

```
也就是说，如果转换前是key,那么转换后就是H(key)。
```
有这些散列函数
```
直接地址法：恒等变换--H(key)=key，线性变换--H(key)=a*key+b;

```
```
平方取中法(较少用)：先计算关键字的平方然后有目的的选取中间的若干位作为散列地址。若，假设散列地址范围是[000,999],key=4731则key^2=22382361取第三位至第五位作为其散列地址，则H(key)=382
```
```
除留余数法（较常用）：H(key)=key%mod  （通过这个函数，可以把一个很大的数转换为不超过mod的整数） 不过两个不同的key1和key2的hash值hash(key1)和hash(key2)可以是相同的，这就产生了冲突，所以得想办法避免冲突。
```
冲突解决办法
```
1.线性探测法---（计算新的hash值，开放地址）
2.平方探测法---（计算新的hash值，开放地址）
3.链地址法（拉链法）---（不计算新的hash值）
......
......
还有很多只做粗略了解
```
**字符串hash初步**
首先先思考一个小例子理解其中的思想
```
问题：如何将一个二维整点P的坐标映射为一个整数，使得整点P可以由该整数唯一地代表。
```
```
解答：假设一个整点P的坐标为（x,y）,其中0<=x,y<=range,那么hash函数就为hash(P)=x*range+y;这样一来，对数据范围内的任意两个整点P1和P2，H(P1)都不会等于H(P2),就可以用H(P)来唯一的代表该整点P,接着便可以通过整数hash的方法来进一步映射到较小的范围内。
```

补充：只讨论字符串转换为唯一的整数（进阶后期再学）
```
字符串hash是指将一个字符串映射成一个整数，使得该整数可以尽可能唯一地代表字符串S。
```
```
我们不妨设字符串S由A~Z这26个大写字母组成，再不妨把A~Z映射为0~25，这样就可以把26个字母对应到二十六进制中。 (转换成的整数最大为26^len-1，其中len为字符串长度)
接着，按照二十六进制转换成十进制的方法，即可将这个S转换成一个十进制的数。由进制转换的结论可以知道，这个十进制的数是唯一的，于是上述问题得到解决，下面是实现：
```
```
int hashFunc1(char s[],int len)
{
    int id=0;
    for(int i=0;i<len;i++)
    {
        id=id*26+(s[i]-'A');
    }
    return id;
}

```
如果出现小写字母，那么A~Z作为0~25，而把a~z作为26~51，这样就变成了五十二进制转换为十进制的问题，做法也是相同的
```
int hashFunc2(char s[],int len)
{
    int id=0;
    for(int i=1;i<len;i++)
    {
        if(s[i]>='A'&&s[i]<='Z')
            id=id*52+(s[i]-'A');
        else if(s[i]>='a'&&s[i]<='z')
            id=id*52+(s[i]-'a')+26;///注意加26，否则输出的值与大写字母相同
    }
}
```

如果出现了数字，一般有两种处理方法，
```
1.按照小写字母的处理方法，增大进制至62.
2.确保末尾是数字的话。（例如字符串BCD4,先将BCD转换成731，再将4拼接上去，变成7314，代码如下） 
```
```
int hashFunc(char s[],int len)
{
    int id=0;
    for(int i=0;i<len;i++)
    {
        id=id*26+(s[i]-'A');
    }
	id=id*10+(s[len-1]-'0');
    return id;
}
```
然后就留下一个问题，
```
若给n个字符串（恰好由三位大写字母组成），再给出m个询问字符串，问m中每个字符串.在n个字符串中出现过几次。
```
代码先隐藏起来

------------
#### 　　　　　　提示：隐藏内容需要 [分享](#starRating) 本文后，刷新页面才能查看。
------------

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

验题君

转发膜拜下大佬的代码

2019-07-14 10:11:35

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-计负均正（C语言代码）

简单的a+b （C语言代码）

C语言考试练习题_保留字母（C语言代码）

整数散列(补充)和字符串hash初步-----每日PAT

评论区

精彩推荐

字符串输入输出函数（Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符逆序（C语言代码）

K-进制数（C语言描述，蓝桥杯）

杨辉三角（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-计负均正 （C语言代码）

简单的a+b （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

整数散列(补充)和字符串hash初步-----每日PAT

评论区

精彩推荐

字符串输入输出函数 （Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

【魔板】 （C++代码）(时间超限，希望会的帮我改正一下)

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

字符逆序 （C语言代码）

K-进制数 （C语言描述，蓝桥杯）

杨辉三角 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C二级辅导-计负均正（C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

字符串输入输出函数（Java代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

【魔板】（C++代码）(时间超限，希望会的帮我改正一下)

字符逆序（C语言代码）

K-进制数（C语言描述，蓝桥杯）

杨辉三角（C语言代码）