当前位置: 首页 > 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语言…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

DAY 26 函数专题1

函数定义与参数知识点回顾&#xff1a;1. 函数的定义2. 变量作用域&#xff1a;局部变量和全局变量3. 函数的参数类型&#xff1a;位置参数、默认参数、不定参数4. 传递参数的手段&#xff1a;关键词参数5 题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一…...