当前位置: 首页 > news >正文

STL 哈希 学习总结

概述

基础概念

哈希是通过特定的算法,将任意长度的数据映射为固定长度的数据串中。该映射的结果就被称为哈希值,也可以称为散列值。

例如在存储一个10000这个数据的时候,如果使用数组的话,则需要开辟对应大小空间内存,其他位置又不一定存储数据,所以这样就会造成数据的浪费。那么此时如果将这个数除以一个特定的数字,然后再将其存储到除数的结果下标中去,这样就避免了空间的浪费。

哈希函数

  • 概念:哈希函数是将输入的数据转换为固定长度的哈希值的函数,这个转换过程也就是哈希或者散列
  • 常用的哈希函数
    • 直接定址法
      • 取关键字的某个现行函数为散列地址:Hash(key) = A*Key + B
      • 需要事先知道关键字的分布状况
    • 除留余数法
      • 假设散列表中允许的地址数有M个,取一个不大于M的数字,但是必须是最接近或者等于M的质数作为除数
      • Hash(Key) = Key % p (p<=M) ,将关键码转换为哈希地址

哈希值

  • 哈希值则是通过哈希函数计算得到的固定长度的数据串,通常表示为一个16进制数
  • 哈希表的长度取决于具体的哈希函数

哈希应用场景

  • 数据存储于检索
    • 哈希表:利用哈希表将存储的数值,映射到哈希表中对应的位置,从而实现快速的数据存取
  • 数据验证
    • 校验和和消息摘要:通过计算数据的哈希值来验证数据的完整性
  • 负载均衡
    • 分布式系统中,通过哈希函数将请求均匀的分配到服务器中,从而实现负载均衡

基础概念总结*

  •  哈希表是一种数据结构,通过哈希函数将键映射到一个数组中的索引位置,从而实现快速查找、插入和删除操作。每一个键值都存储在在一个桶中,桶的索引则是由哈希函数计算而来
  • 哈希函数负责将一个任意大小的数据转换为固定大小的整数,哈希值通常是桶数组的索引
  • 哈希表的主要应用字典、数据存储、数据验证、负载均衡

时间复杂度分析*

  • 查插删的平均时间复杂度都是O(1)
  • 最坏情况是O(n),最坏的情况即是所有的键都被映射到同一个桶中

哈希函数设计原则

  • 均匀性:输入均匀的分布到所有桶中,从而减少冲突
  • 减少碰撞:避免产生相同的哈希数值,减少碰撞的产生

unordered_map | unordered_set

unordered_map

  • 存储数据的关联容器,用于存储键值对,通过键值来快速寻找对应数值,底层是哈希表
  • 每个元素是一个键值对,键是唯一的,但是值是可以重复的

unordered_set

  • 同样是关联容器,用于存储唯一元素并快速查找,底层仍然是哈希表
  • 集合中的元素是唯一的,不可以有重复的元素,所以可以使用在元素去重或者快速查找上

两者插入与删除的时间复杂度都是O(1)

哈希表数组初始值

 Linux系统测试

#include <unordered_map>
#include <iostream>int main() {std::unordered_map<int, int> umap;std::cout << "Initial bucket count (libstdc++): " << umap.bucket_count() << std::endl;return 0;
}

 VS系统测试

 

#define _CRT_SECURE_NO_WARNINGS 1
#include <unordered_map>
#include <iostream>int main() {std::unordered_map<int, int> umap;std::cout << "Initial bucket count (MSVC): " << umap.bucket_count() << std::endl;return 0;
}

 哈希表初始值原则质数的原因

  • 减少冲突:质数作为哈希表的初始桶数量有助于减少哈希冲突,因为质数能更加均匀的分散哈希值,减少哈希函数的重复。
  • 性能:较小的初始值,可以让哈希表在初期阶段节省内存保持高性能
  • 拓展性:哈希表增长过程中,通常采用倍增的方式,从而保证负载因子在合理的范围内
  • 平衡负载因子:负载因子是哈希表元素数量与桶数量的比值。初始桶数量设置一个较小的数值,可以保持较低的负载因子

负载因子0.75的原因

  • 查找效率
    • 降低冲突效率:保证25%的桶是空闲的,减少哈希冲突的概率
    • 查找高效:此时的查找时间接近于O(1),因为负载因子如果过高的话,冲突增加,导致查找时间增加。如果负载因子过低,虽然冲突减少,但是会浪费大量内存
  • 平衡内存和性能
    • 保证查找效率的同时,让哈希表不浪费太多的内存空间
    • 避免频繁拓展 

 

哈希冲突

 哈希冲突指的是两个不同的数据,通过同一个哈希函数映射后,产生了相同的哈希值,从而在存储位置上产生了冲突。

解决方法

开放地址法

线性探测:顺序检查下一个位置,直到找一个空闲的位置。(-1表示该位置没有存储数据)

二次探测:采用二次方步长避免线性探测中的集聚性问题。 

 双重散列:使用第二个哈希函数计算步长,从而避免数据冲突

 

链地址法

每个哈希表的槽中,都存储一个链表指针,所有哈希到同一位置的元素,全部都插入该链表中。 

二次哈希

当哈希表达到一定的负载因子时,创建一个更大的哈希表,并使用新的哈希函数重新计算所有元素的数值,然后存储到新的哈希表中。 

细节问题

动态拓展和缩减

  • 拓展:哈希表负载因子超过设置阈值时,需要拓展哈希表,创建一个更大的桶数组,并重新计算所有元素的哈希值分配到新的桶中
  • 缩减:低于阈值的时候,调整哈希表大小,从而保证高效的查找性能

性能优化:选择初始桶的数量以及合理的负载因子,从而减少冲突和内存浪费

void rehash() {std::vector<std::list<PairType>> new_buckets(buckets.size() * 2);for (const auto& bucket : buckets) {for (const auto& pair : bucket) {size_t new_index = std::hash<KeyType>()(pair.first) % new_buckets.size();new_buckets[new_index].push_back(pair);}}buckets.swap(new_buckets);
}

哈希表的实际应用场景

数据库:哈希表用于实现索引,从而加速数据的索引

缓冲系统中:快速查找缓存数据

编译器:哈希表用于符号表管理、快速查找变量以及函数信息 

 实现简单哈希表(插入删除与查找)

#include <iostream>
#include <vector>
#include <list>template <typename KeyType, typename ValueType>
class SimpleHashTable {
public:using PairType = std::pair<KeyType, ValueType>;SimpleHashTable(size_t bucket_count) : buckets(bucket_count) {}void insert(const KeyType& key, const ValueType& value) {size_t index = hashFunction(key);for (auto& pair : buckets[index]) {if (pair.first == key) {pair.second = value;  // 更新现有值return;}}buckets[index].emplace_back(key, value);  // 插入新值}bool remove(const KeyType& key) {size_t index = hashFunction(key);for (auto it = buckets[index].begin(); it != buckets[index].end(); ++it) {if (it->first == key) {buckets[index].erase(it);return true;}}return false;}bool find(const KeyType& key, ValueType& value) const {size_t index = hashFunction(key);for (const auto& pair : buckets[index]) {if (pair.first == key) {value = pair.second;return true;}}return false;}private:size_t hashFunction(const KeyType& key) const {return std::hash<KeyType>()(key) % buckets.size();}std::vector<std::list<PairType>> buckets;
};int main() {SimpleHashTable<int, std::string> table(10);table.insert(1, "one");table.insert(2, "two");table.insert(11, "eleven");std::string value;if (table.find(2, value)) {std::cout << "Found: " << value << std::endl;} else {std::cout << "Not found" << std::endl;}table.remove(2);if (table.find(2, value)) {std::cout << "Found: " << value << std::endl;} else {std::cout << "Not found" << std::endl;}return 0;
}

相关文章:

STL 哈希 学习总结

概述 基础概念 哈希是通过特定的算法&#xff0c;将任意长度的数据映射为固定长度的数据串中。该映射的结果就被称为哈希值&#xff0c;也可以称为散列值。 例如在存储一个10000这个数据的时候&#xff0c;如果使用数组的话&#xff0c;则需要开辟对应大小空间内存&#xff…...

vue3页面编写-导入导出excel、展开查询项等

数据保持 <router-view v-slot"{ Component, route }"><keep-alive><component :is"Component" :key"route.name" v-if"route.meta.keepAlive" /></keep-alive><component :is"Component" :key…...

Java学习 - Spring Boot整合 Thymeleaf 实例

什么是 Thymeleaf Thymeleaf 是新一代的 Java 模板引擎&#xff0c;类似于 Velocity、FreeMarker 等传统引擎&#xff0c;其语言和 HTML 很接近&#xff0c;而且扩展性更高&#xff1b; Thymeleaf 的主要目的是将优雅的模板引入开发工作流程中&#xff0c;并将 HTML 在浏览器中…...

ubuntu20.04安装终端终结者并设置为默认终端

1、安装 terminator sudo apt-get install terminator 2、Ctrl Alt T 试一下打开什么终端&#xff0c;我的默认启动的是terminator;如果想换换默认的终端&#xff0c;还需以下一步 3、安装dconf-tools&#xff0c;这个是设置默认终端的必须 sudo apt-get install dconf-tools…...

以Zookeeper为例 浅谈脑裂与奇数节点问题

一、脑裂现象的定义与影响 脑裂&#xff08;split-brain&#xff09;是指在分布式系统中&#xff0c;因网络分区或其他故障导致系统被切割成两个或多个相互独立的子系统&#xff0c;每个子系统可能独立选举出自己的领导节点。这一现象在依赖中心领导节点&#xff08;如Elastic…...

最新版kubeadm搭建k8s(已成功搭建)

kubeadm搭建k8s&#xff08;已成功搭建&#xff09; 环境配置 主节点 k8s-master&#xff1a;4核8G、40GB硬盘、CentOS7.9&#xff08;内网IP&#xff1a;10.16.64.67&#xff09; 从节点 k8s-node1&#xff1a; 4核8G、40GB硬盘、CentOS7.9&#xff08;内网IP&#xff1a;10…...

C++学习笔记-友元函数的定义与使用

一、引言 在C中&#xff0c;友元函数&#xff08;Friend Function&#xff09;是一个独特而强大的特性&#xff0c;它打破了类的封装性&#xff0c;允许一个或多个非成员函数访问类的私有&#xff08;private&#xff09;和保护&#xff08;protected&#xff09;成员。尽管这…...

熵、交叉熵、KL散度

这里写目录标题 熵KL散度引入交叉熵。交叉熵的二分类公式&#xff1a; 再次理解SoftMax函数结束 熵 熵&#xff0c;是一个物理上的概念&#xff0c;表示一个系统的不确定性程度&#xff0c;或者表示一个系统的混乱程序。 下边是信息熵的演示&#xff1a; 信息熵的公式如下&…...

THS配置keepalive(yjm)

启动完THS管理控制台和THS后&#xff0c;登录控制台&#xff0c;进入实例管理》节点管理&#xff0c;可以分别使用界面配置和编辑配置设置长连接。 1、界面配置 点击界面配置》集群设置&#xff0c;启用长连接&#xff0c;设置长连接数、最大请求数和超时时间。 2、编辑配置 …...

新加坡裸机云多IP服务器特性

新加坡裸机云多IP服务器是一种高性能、稳定性强&#xff0c;且具备多IP地址特性的服务器。它主要适用于需要高度计算性能、网络连接稳定和高安全性的业务场景&#xff0c;如跨境外贸等。下面将详细探讨该类型服务器的特性&#xff0c;rak部落为您整理发布新加坡裸机云多IP服务器…...

深入理解ADB:Android调试桥详解与使用指南

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Android ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 1. 什么是ADB&#xff1f; ADB的基本原理&#xff1a; 2. ADB的安装与配置 安装ADB工具集&#xff1a; 配置ADB环境变量&am…...

PACS-医学影像信息管理系统,全影像科室PACS源码,内置包括MPR、CMPR、VR等三维处理功能

PACS系统可以覆盖医院现有放射、CT、MR、核医学、超声、内镜、病理、心电等绝大部分DICOM和非DICOM检查设备&#xff0c;支持从科室级、全院机、集团医院级乃至到区域PACS的平滑扩展&#xff0c;能够与医院HIS、集成平台的有效集成和融合&#xff0c;帮助医院实现了全院医学影像…...

无人机搭载无人机反制设备可行性分析

一、引言 随着无人机技术的飞速发展&#xff0c;无人机在各个领域的应用越来越广泛。然而&#xff0c;无人机的不当使用也可能带来安全隐患和隐私问题。因此&#xff0c;无人机反制设备应运而生&#xff0c;用于对非法或危险无人机进行干扰和控制。本文将对无人机搭载无人机反…...

MATLAB绘制方波、锯齿波、三角波、正弦波和余弦波、

一、引言 MATLAB是一种具有很强的数值计算和数据可视化软件&#xff0c;提供了许多内置函数来简化数学运算和图形的快速生成。在MATLAB中&#xff0c;你可以使用多种方法来快速绘制正弦波、方波和三角波。以下是一些基本的示例&#xff0c;展示了如何使用MATLAB的命令来实现正弦…...

【通信协议-RTCM】MSM语句(2) - RINEXMSM7语句总结(重要!自动化开发计算卫星状态常用)

注释&#xff1a; 在工作中主要负责的是RTCM-MSM7语句相关开发工作&#xff0c;所以主要介绍的就是MSM7语句相关内容 1. 相位校准参考信号 2. MSM1、MSM2、MSM3、MSM4、MSM5、MSM6和MSM7的消息头内容 DATA FIELDDF NUMBERDATA TYPENO. OF BITSNOTES Message Number - 消息编…...

ios CCUIFont.m

// // CCUIFont.h // CCFC // //#import <Foundation/Foundation.h>// 创建字体对象 #define CREATE_FONT(fontSize) [UIFont systemFontOfSize:(fontSize)]interface UIFont(cc) (void)logAllFonts;end // // CCUIFont.m // CCFC // //#import "CCUIFont.h&…...

调度子系统在特定时间执行

时序逻辑调度器设计模式允许您安排Simulink子系统在指定时间执行。以下模型说明了这种设计模式。 时序逻辑调度器图表包含以下逻辑&#xff1a; 时序逻辑调度器的关键行为 时序逻辑调度器图表包含两个状态&#xff0c;它们以不同的速率调度函数调用子系统A1、A2和A3的执行&…...

【QAC】Dashboard服务端如何配置

【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 解决Dashboard服务端如何配置的问题。 2、 问题场景 客户想使用Dashboard&#xff0c;Dashboard服务端如何配置。 3、软硬件环境 1、软件版本&#xff1a;HelixQAC23.04 2、机器环境&#xff1a;Windows 64bit 3…...

深入理解Linux网络(四):TCP接收阻塞

TCP socket 接收函数 recv 发出 recvfrom 系统调用。 进⼊系统调⽤后&#xff0c;⽤户进程就进⼊到了内核态&#xff0c;通过执⾏⼀系列的内核协议层函数&#xff0c;然后到 socket 对象的接收队列中查看是否有数据&#xff0c;没有的话就把⾃⼰添加到 socket 对应的等待队列⾥…...

【iOS】内存五大分区

目录 堆&#xff08;Heap&#xff09;是什么五大分区栈区堆区全局/静态区常量区&#xff08;即.rodata&#xff09;代码区&#xff08;.text&#xff09; 函数栈堆和栈的区别和联系图解 OC语言是C语言的超集&#xff0c;所以先了解C语言的内存模型的内存管理会有很大帮助。C语言…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...