散列,字符串hash初步

简介: 散列,字符串hash初步

散列是一种以空间换时间的算法思想,以整数散列为列,其精髓就在于用其一个整数数组的下标对应操作输入的对象,要查找这个对象,就直接查找其对应的下标里面信息。

举个例子: 随便输入n个数a(0-100),再输入m个数b,查询他们在这n个数中出现了几次?

这个时候我们建立一个101大的整数数组t初始为0,直接以数组下标标识0-100的数,输入a时,令t[a]++就代表那个数查询了,查询的时候也方便,t[b]大小就是b出现的次数。

再问: 如果关键词不是整数,而是字符串或坐标等别的数据怎么办?

这时候,就要体现散列的精髓了- hash函数的构造,下面以字符串为例:

现在输入的不是数了,而是3个小写字母的单词,应该怎么办?

分析小写字母是a-b,共26位,如果把它们考虑成一个26进制数,转化为十进制就会有一个唯一十进制数与之对应,借此思想我们设计程序如下:


#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=26*26*26+1;
int t[maxn]={0};
int hashfunc(char s[],int n) {  //将字符串转化为十进制数,hash函数 
  int id=0;
  for(int i=0;i<n;i++)
  id=id*26+(s[i]-'a');
  return id;
}
int main(){
  char s[3];
  int n;
  cin>>n;
  for(int i=0;i<n;i++)
  {   
    for(int j=0;j<3;j++)
    cin>>s[j];
    t[hashfunc(s,3)]++;
  }
  for(int j=0;j<3;j++)
    cin>>s[j];  
  cout<<  t[hashfunc(s,3)]<<endl;
  return 0;
}

一个结果:

1685014611339.jpg

显然,如果一个字符串数据太大,这样就不太适合,至于处理方法,我们将在字符串部分讲解

相关文章
|
数据库 C++
.NET Core 使用 EF 出错的解决方法
.NET Core 使用 EF 出错的解决方法
566 0
.NET Core 使用 EF 出错的解决方法
|
12月前
|
负载均衡 Java 网络架构
Spring Cloud原理详解
介绍了Spring Cloud的原理和核心组件,包括服务注册与发现、配置管理、负载均衡、断路器、智能路由、分布式消息传递、分布式追踪和服务熔断等,旨在帮助开发人员快速构建和管理微服务架构中的分布式系统。
469 0
|
NoSQL
技术分享:如何使用GDB调试不带调试信息的可执行程序
【8月更文挑战第27天】在软件开发和调试过程中,我们有时会遇到需要调试没有调试信息的可执行程序的情况。这可能是由于程序在编译时没有加入调试信息,或者调试信息被剥离了。然而,即使面对这样的挑战,GDB(GNU Debugger)仍然提供了一些方法和技术来帮助我们进行调试。以下将详细介绍如何使用GDB调试不带调试信息的可执行程序。
351 0
|
SQL 关系型数据库 Oracle
ORA-01466: unable to read data - table definition has changed
1. Oracle建议我们等待大约5分钟之后再进行flashback query新创建的表,否则可能会碰到这个错误ORA-01466: unable to read data - table definition has changed.
1932 0
|
分布式计算 数据处理 分布式数据库
《基于HBase和Spark构建企业级数据处理平台》电子版地址
基于HBase和Spark构建企业级数据处理平台
151 0
《基于HBase和Spark构建企业级数据处理平台》电子版地址
|
存储 缓存 JSON
Elasticsearch 开发人员最佳实践指南—Elastic Stack 实战手册
几个月以来,我一直在记录自己开发 Elasticsearch 应用程序的最佳实践。本文梳理的内容试图传达 Java 的某些思想,我相信其同样适用于其他编程语言。我尝试尽量避免重复教程和 Elasticsearch 官方文档中已经介绍的内容。
2474 0
Elasticsearch 开发人员最佳实践指南—Elastic Stack 实战手册
|
C++ 容器
STL—map(一)
map是映射,我们在定义数组的时候int a[100];其实是一个int --> int的映射,
120 0
|
数据采集 Python
Scrapy框架--通用爬虫Broad Crawls(上)
通用爬虫(Broad Crawls)介绍 [传送:中文文档介绍],里面除了介绍还有很多配置选项。 通用爬虫一般有以下通用特性: 其爬取大量(一般来说是无限)的网站而不是特定的一些网站。
2335 0
|
存储 算法 容器
设计模式概念总结
      这为我的学习笔记,原文为https://www.cnblogs.com/zhili/p/DesignPatternSummery.html 1.单例模式(Singleton)    确保一个类只有一个实例,并提供一个全局访问点 2.简单工厂   优点: 简单工厂模式解决了客户端直接依赖于具体对象的问题,客户端可以消除直接创建对象的责任,而仅仅是消费产品。
996 0