哈希表的封装和位图

2024-09-09 03:44
文章标签 封装 哈希 位图

本文主要是介绍哈希表的封装和位图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 2 封装
    • 2.1 基础框架
    • 2.2 迭代器(1)
    • 2.3 迭代器(2)
  • 3. 位图
    • 3.1 问题引入
    • 3.2 左移和右移？
    • 3.3 位图的实现
    • 3.4 位图的题目
    • 3.5 位图的应用

2 封装

2.1 基础框架

文章

有了前面map和set封装的经验，容易写出下面的代码

// UnorderedSet.h
#pragma once
#include "HashTable.h"
template <class K, class Hash = HashFunc<K>>
class UnorderedSet
{// 返回keystruct SetKeyOfT{const K& operator()(const K& key){return key;}};
public:bool insert(const K& key){return _ht.Insert(key);}
private:HashTable<K, K, SetKeyOfT, Hash> _ht;
};

// UnorderedMap.h
#pragma once
#include "HashTable.h"
template <class K, class V,  class Hash = HashFunc<K>>
class UnorderedMap
{// 返回pair的first,即keystruct MapKeyOfT{const K& operator()(const pair<K, V> &kv){return kv.first;}};
public:bool insert(const pair<K, V>& kv){return _ht.Insert(kv);}private:HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
};

// HashTable.h
template <class T>
struct HashNode
{HashNode(const T& data): _data(data), _next(nullptr){}HashNode* _next;T _data;
};
// UnorderedMap->HashTable<K, pair<K, V>>
// UnorderedSet->HashTable<K, K>
template <class K, class T, class KeyOfT , class Hash>
class HashTable
{typedef HashNode<T> Node;
public:// ...bool Insert(const T& data){// 如果已经有该元素了，返回falseif (Find(kot(data)))	return false;size_t sz = _table.size();// 负载因子设置到1if (_table.size() == _n){size_t newSz = sz * 2;vector<Node*> newTable;newTable.resize(newSz, nullptr);for (size_t i = 0; i < sz; ++i) {Node* cur = _table[i];while (cur) {Node* next = cur->_next;size_t hashI = hf(kot(cur->_data)) % newSz;// 头插到新链表cur->_next = newTable[hashI];newTable[hashI] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newTable);}size_t hashI = hf(kot(data)) % sz;Node* newNode = new Node(data);// 头插newNode->_next = _table[hashI];_table[hashI] = newNode;++_n;return true;}// ...
private: vector<Node*> _table;size_t _n;Hash hf;KeyOfT kot;
};

其中HashTable.h中部分代码已经省略，详细见文章

2.2 迭代器(1)

写法1

// HashTable.h
template <class T>
struct __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<T> Self;Node* _node;vector<Node*>& _table;	// 方便找下一个桶size_t _hashI;		// 当前找到哪个桶了__HTIterator(Node* node, vector<Node*>& table, size_t hashI): _node(node), _table(table), _hashI(hashI){}Self& operator++(){if (_node->_next) {// 当前桶还有节点，走到下一个节点_node = _node->_next;}else {// 当前桶没有节点了，去找下一个桶++_hashI;while (_hashI < _table.size()) {if (_table[_hashI] != nullptr) {// 找到了非空节点_node = _table[_hashI];break;}++_hashI;}// 没有下一个有节点的桶了if (_hashI == _table.size()) {_node = nullptr;	// 让nullptr充当end()}}return *this;}bool operator!=(const Self& s){return _node != s._node;}T& operator*(){return _node->_data;}T* operator->(){return &(_node->_data);}
};template <class K, class T, class KeyOfT , class Hash = HashFunc<K>>
class HashTable
{// ...typedef __HTIterator<T> Iterator;Iterator begin(){// 找到第一个有存值的桶，传给迭代器for (size_t i = 0; i < _table.size(); i++) {if (_table[i] != nullptr) {return Iterator(_table[i], _table, i);}}// 找到最后还没有找到，证明是空哈希表return end();}Iterator end(){return Iterator(nullptr, _table, -1);}// ...
}

2.3 迭代器(2)

// 因为后面的__HTIterator使用了HashTable这个类，向上找找不到，所以需要前置声明
template <class K, class T, class KeyOfT, class Hash>
class HashTable;template <class K, class T, class KeyOfT, class Hash>
struct __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node* _node;HashTable<K, T, KeyOfT, Hash>* _ht;	// 方便找下一个桶size_t _hashI;		// 当前找到哪个桶了__HTIterator(Node* node, HashTable<K, T, KeyOfT, Hash>* ht, size_t hashI): _node(node), _ht(ht), _hashI(hashI){}Self& operator++(){if (_node->_next) {// 当前桶还有节点，走到下一个节点_node = _node->_next;}else {// 当前桶没有节点了，去找下一个桶++_hashI;while (_hashI < _ht->_table.size()) {if (_ht->_table[_hashI] != nullptr) {// 找到了非空节点_node = _ht->_table[_hashI];break;}++_hashI;}// 没有下一个有节点的桶了if (_hashI == _ht->_table.size()) {_node = nullptr;	// 让nullptr充当end()}}return *this;}// ...
};template <class K, class T, class KeyOfT, class Hash>
class HashTable
{typedef HashNode<T> Node;template <class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;		// 让__HTIterator成为HashTable的友元，因为用到了_table这个私有属性
public:typedef __HTIterator<K, T, KeyOfT, Hash> Iterator;Iterator begin(){// 找到第一个有存值的桶，传给迭代器for (size_t i = 0; i < _table.size(); i++) {if (_table[i] != nullptr) {return Iterator(_table[i], this, i);}}// 找到最后还没有找到，证明是空哈希表return end();}Iterator end(){return Iterator(nullptr, this, -1);}// ...
}

const迭代器不再实现，太复杂了。

3. 位图

概念：所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

3.1 问题引入

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

  1. 遍历，时间复杂度O(N)

  2. 排序(O(NlogN))，利用二分查找: logN

  3. 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。比如：

​ image-20240908131159204

可以计算一下，40亿个数，需要开2^32bit，即512MB

3.2 左移和右移？

image-20240908154458368

vs是以小端字节序存储的，左移指的是像高地址移动，右移是指向低地址移动，并不是按移动的方向定义的

执行完i = 1

image-20240908155207271

执行完i <<= 8

image-20240908155231047

image-20240908155547251

3.3 位图的实现

// N表示需要多少bit位
template<size_t N>
class MyBitset
{
public:MyBitset(){_bits.resize(N / 32 + 1, 0);}/*把x映射的位置1* x在数组的第几个整形呢？		i = x / 32* x在这个整形的第几个位呢？   j = x % 32*/ void set(size_t x) {size_t i = x / 32;size_t j = x % 32;// 或等上1<<j_bits[i] |= (1 << j);}// 把x映射的位置0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;// 与等上~(1<<j)_bits[i] &= (~(1 << j));}// 检查x所在的bit是0还是1bool test(size_t x){size_t i = x / 32;size_t j = x % 32;// 与上1return _bits[i] & (1 << j);}
private:vector<size_t> _bits;
};

image-20240908162435739

上面的3.1的问题，我们可以开一个bitset来解决

// solution 1
MyBitset<0xffffffff> bs;
// solution 2
MyBitset<-1> bs2;

3.4 位图的题目

  1. 给定100亿个整数，设计算法找到只出现一次的整数？

使用两个bitset，00表示出现0次，01表示出现1次，10表示出现2次或者2次以上

template<size_t N>
class TwoBitset
{
public:/** 00->01* 01->10* 10->same*/void set(size_t x){if (!_bs1.test(x) and !_bs2.test(x)) {_bs2.set(x);}else if (!_bs1.test(x) and _bs2.test(x)) {_bs1.set(x);_bs2.reset(x);}}/* 打印出现一次的数字 */void PrintOnce(){for (size_t i = 0; i < N; i++) {if (!_bs1.test(i) and _bs2.test(i))cout << i << ' ';}cout << endl;}private: MyBitset<N> _bs1;MyBitset<N> _bs2;
};
  1. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

与上面类似：将这些整数各自映射到一个位图，一个值在两个位图都存在，则是交集

  1. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

也是一样，两个位图，00表示出现0次，01表示出现1次，10表示出现2次，11表示出现3次及以上

3.5 位图的应用

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

这篇关于哈希表的封装和位图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1150065。

相关文章

鸿蒙中Axios数据请求的封装和配置方法

鸿蒙中Axios数据请求的封装和配置方法

《鸿蒙中Axios数据请求的封装和配置方法》：本文主要介绍鸿蒙中Axios数据请求的封装和配置方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.配置权限 应用级权限和系统级权限2.配置网络请求的代码3.下载在Entry中 下载AxIOS4.封装Htt
阅读更多...
SpringBoot中封装Cors自动配置方式

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》：本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties
阅读更多...
Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

《Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)》：本文主要介绍Java导入、导出excel的相关资料,讲解了使用Java和ApachePOI库将数据导出为Excel文件,包括... 目录前言一、引入Apache POI依赖二、用法&步骤2.1 创建Excel的元素2.3 样式和字体2.
阅读更多...
JAVA封装多线程实现的方式及原理

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》：本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中，封装多线程的原理主要围绕着将多线程相关的操
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...
Go语言利用泛型封装常见的Map操作

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式，允
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
JavaSE——封装、继承和多态

JavaSE——封装、继承和多态

1. 封装 1.1 概念      面向对象程序三大特性：封装、继承、多态 。而类和对象阶段，主要研究的就是封装特性。何为封装呢？简单来说就是套壳屏蔽细节 。     比如：对于电脑这样一个复杂的设备，提供给用户的就只是：开关机、通过键盘输入，显示器， USB 插孔等，让用户来和计算机进行交互，完成日常事务。但实际上：电脑真正工作的却是CPU 、显卡、内存等一些硬件元件。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2