C++笔记：Hash Function 散列函数

2024-05-26 21:28
文章标签 c++ 函数 笔记 function hash 散列

本文主要是介绍C++笔记：Hash Function 散列函数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. Hash Function 散列函数

  • 简单的Hash实现：
class CustomerHash {
public:size_t operator()(const Customer& c) const {return hash<std::string>()(c.fname) +  // first namehash<std::string>()(c.lname) +  // last namehash<long>()(c.no);// 返回hash_code}
};

  • 针对Customer类对象，直接对其各个成员变量分别调用标准库中的hash函数，并将得到的哈希值相加。

  • 虽然简单，但这种实现方式可能会导致哈希冲突（即不同对象可能产生相同的哈希值）。

  • 改进的Hash实现：

class CustomerHash {
public:size_t operator()(const Customer& c) const {return hash_val(c.frame, c.lname, c.no);}
};

template <typename... Type>
inline size_t hash_val(const Type&... args){size_t seed = 0;hash_val(seed, args...);return seed;  //seed最终就被视为hash code
}
  • 顶层主函数：初始化 seed 为0，调用 hash_val递归处理所有参数，并返回最终的哈希值。
template <typename T, typename... Types>
inline void hash_val(size_t& seed, const T& val, const Type&... args){hash_combine(seed, val);hash_val(seed, args);
};
  • 这是一个递归函数模板，它处理一个或多个参数：
    • 首先，调用 hash_combine函数处理当前参数 val并更新 seed。
    • 然后，递归调用自身处理剩余的参数。
template <typename T>
inline void hash_val(size_t& seed, const T& val){hash_combine(seed, val);
}
  • 这是上面递归函数的终止版本，当没有更多参数时，只处理最后一个参数。
#include<functional>
template <typename T>
inline void hash_combine(size_t& seed, const T& val){seed ^= hash<T>()(val) + 0x9e3779b9 + (seed<<6) + (seed<<2);
}

  • 结合当前的哈希值和传入的值来更新seed，使用了一些常见的哈希组合技巧（例如魔数0x9e3779b9），以减少冲突。

  • 以struct hash 偏特化的形式实现Hash function

    • 在 std 命名空间中特化 hash 结构体以支持 MyString 类型
namespace std {template<>struct hash<MyString> {size_t operator()(const MyString& s) const noexcept {return hash<string>()(s.get());}};
}

2. tuple

  • 构造方式：
// 构造方式1
tuple<int, float, string> t1(41, 6.3, "nico");
cout << "t1: " << get<0>(t1) << " " << get<1>(t1) << " " << get<2>(t1) << endl;// 构造方式2
auto t2 = make_tuple(22, 44, "stacy");// 构造方式3
tuple<int,float,string> t3(77, 1.1, "more light");
int i1;
float f1;
stting s1;
tie(i1, f1, s1) = t3;
  • 用例：
tuple<int, float, string> t(41, 6.3, "nico"); // 调用了构造函数
t.head() // 调用了head()函数，返回 41
t.tail() // 调用了tail()函数，返回 tuple<float, string>
t.tail().head() // 调用了tail()然后是head()函数，返回 6.3
t.tail().tail().head() // 调用了两次tail()然后是head()函数，返回 "nico"
&(t.tail()) // 调用了tail()函数，返回 tuple<float, string> 的引用
  • 源码：
// 这是一个变长模板声明，表示tuple类可以接受任意数量和类型的模板参数
template<typename... Values> class tuple;
template<> class tuple<> {};

template<typename Head, typename... Tail>
class tuple<Head, Tail...> : public tuple<Tail...>
{typedef tuple<Tail...> inherited;
public:tuple() {};tuple(Head v, Tail... vtail) : m_head(v), inheriter(vtail...) {}typename Head::type head() { return m_head;}inherited& tail { return *this;}
protected:Head m_head;
};
  • tuple<Head, Tail...>递归地继承了tuple<Tail...>，即剩下的参数组成的元组。
    • tuple<int, float, string> : private tuple<float, string>
    • tuple<float, string> : private tuple<string>
    • tuple<string>
  • 在t.tail()中，调用tail()函数，tail()返回*this。此时，*this指向的对象类型是tuple<int, float, string>，但通过类型转换返回为inherited&，即tuple<float, string>&。
  • t.tail() 会返回一个 tuple<float, string>
  • &(t.tail()) 会返回一个tuple<float, string>的引用

3. type traits

 

应用：

template <typename T>
void type_traits_output(const T&x)
{cout << "\\n type traits for type:" << typeid(T).name() << endl;cout << "is_void\\t" << is_void<T>::value << endl; // 0 or 1cout << "is_integral\\t" << is_integral<T>::value << endl; // 0 or 1...
}int i = 0;
double d = 0.0;
type_traits_output(i);
type_traits_output(d);

4. type traits中is_void的实现

为什么判断void时需要移除volatile和const限定符？

假设你有一个类型是const void或volatile void，这些类型本质上还是void类型，只是加了限定符。如果不去除这些限定符，直接判断类型是否为void，判断结果将会是错误的，因为const void和void在严格意义上是不同的类型。

通过移除这些限定符，可以确保我们判断的基础类型是void，而不是const void或volatile void。这确保了类型特性模板的准确性和一致性。

  • 移除volatile限定符：
// 如果类型不带volatile限定符，通用模板直接定义type为原始类型_Tp
template<typename _Tp>
struct remove_volatile {typedef _Tp type;
};// 如果类型带有volatile限定符，特化模板定义会去掉volatile限定符
template<typename _Tp>
struct remove_volatile<_Tp volatile> {typedef _Tp type;
};
  • 移除const限定符：
template<typename _Tp>
struct remove_const {typedef _Tp type;
};template<typename _Tp>
struct remove_const<_Tp const> {typedef _Tp type;
};
  • 移除const和volatile限定符：
template<typename _Tp>
struct remove_cv {typedef typename remove_const<typename remove_volatile<_Tp>::type>::type type;
};
  • 判断是否为void 类型：
template<typename>
struct __is_void_helper : public false_type {};template<>
struct __is_void_helper<void> : public true_type {};
  • 最终的is_void实现：
template<typename _Tp>
struct is_void : public __is_void_helper<typename remove_cv<_Tp>::type> {};

5. cout 标准输出流

  • ostream类是标准C++库中的输出流类，定义在<ostream>头文件中。这个类提供了多种运算符重载，以便将不同类型的数据输出到流中。
ostream& operator<<(char c) {// 输出一个字符return *this;
}ostream& operator<<(unsigned char c) {// 输出一个无符号字符return *this << static_cast<char>(c);
}ostream& operator<<(signed char c) {// 输出一个有符号字符return *this << static_cast<char>(c);
}ostream& operator<<(const char* s) {// 输出一个C风格字符串return *this;
}ostream& operator<<(const unsigned char* s) {// 输出一个无符号字符指针，转换为C风格字符串return *this << reinterpret_cast<const char*>(s);
}ostream& operator<<(const signed char* s) {// 输出一个有符号字符指针，转换为C风格字符串return *this << reinterpret_cast<const char*>(s);
}ostream& operator<<(const void* p) {// 输出一个指针return *this;
}ostream& operator<<(int n) {// 输出一个整数return *this;
}ostream& operator<<(unsigned int n) {// 输出一个无符号整数return *this;
}ostream& operator<<(long n) {// 输出一个长整数return *this;
}ostream& operator<<(unsigned long n) {// 输出一个无符号长整数return *this;
}
  • cout是一个全局的_IO_ostream_withassign对象，表示标准输出流。其继承自ostream，并提供赋值运算符的重载。
class _IO_ostream_withassign : public ostream {
public:_IO_ostream_withassign& operator=(ostream& os) {// 实现赋值操作// 允许将一个ostream对象赋值给_IO_ostream_withassign对象return *this;}_IO_ostream_withassign& operator=(_IO_ostream_withassign& rhs) {// 实现赋值操作return operator=(static_cast<ostream&>(rhs));}
};extern _IO_ostream_withassign cout;

6.moveable元素对于vector速度效能的影响

  • 深拷贝：创建一个新对象，并复制所有的原始对象的数据，包括指向动态分配内存的指针。深拷贝确保新对象和原始对象独立，修改一个不会影响另一个。

    // 拷贝构造函数
MyString(const MyString& other) {len = other.len;data = new char[len + 1];  // 为新对象开辟内存strcpy(data, other.data);  // 将原对象的数据复制到新对象
}// 拷贝赋值运算符
MyString& operator=(const MyString& str) {if (this != &str) {if (_data) delete[] _data;_len = str._len;_init_data(str._data);  // 复制数据}return *this;
}

  • 浅拷贝：只复制对象的成员变量的值，包括指针的值。这意味着复制后的对象和原始对象共享同一块动态分配的内存。这可能会造成一个对象销毁时释放了共享的内存时，导致另一个对象访问无效内存。

    MyString(const Mystring& other) {len = other.len;data = other.data;
}

  • 移动语义（Move Semantics）：通过转移指针操作将资源从一个对象转移到另一个对象，避免深拷贝。通过移动构造函数和移动赋值运算符实现。

    #include <utility>
class  MyString {
public:// 移动构造函数// data = other.data; 新对象直接使用原对象的指针。MyString(MyString&& other) noexcept: data(other.data), len(other.len) {other.data = nullptr; // 将原对象的指针设置为nullptr，防止原对象析构时释放内存other.len = 0;}// 移动赋值运算符MyString& operator=(MyString&& other) noexcept {if (this == &other) return *this;delete[] data;data = other.data;len = other.len;other.data = nullptr;other.len = 0;return *this;}// 析构函数~MyString() {++Dtor;if (_data) delete[] _data;}// 禁用拷贝构造函数和拷贝赋值运算符MyString(const MyString& other) = delete;MyString& operator=(const MyString& other) = delete;

  • 具体示例

    int main() {Mystring str1("Hello, world!");// 调用拷贝构造函数Mystring str2 = str1;cout << str2 << endl;  // "Hello, world!"// 调用移动构造函数Mystring str3 = move(str1);cout << str3 << endl;  // "Hello, world!"cout << str1 << endl;  // 空，因为str1的资源已经转移

这篇关于C++笔记：Hash Function 散列函数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
Python itertools中accumulate函数用法及使用运用详细讲解

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》：本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言：1.2定义：1.3衍生用法：1.3Leetcode的实际运用:总结 1.1前言：本文将详
阅读更多...
轻松上手MYSQL之JSON函数实现高效数据查询与操作

轻松上手MYSQL之JSON函数实现高效数据查询与操作

《轻松上手MYSQL之JSON函数实现高效数据查询与操作》：本文主要介绍轻松上手MYSQL之JSON函数实现高效数据查询与操作的相关资料,MySQL提供了多个JSON函数,用于处理和查询JSON数... 目录一、jsON_EXTRACT 提取指定数据二、JSON_UNQUOTE 取消双引号三、JSON_KE
阅读更多...
MySQL数据库函数之JSON_EXTRACT示例代码

MySQL数据库函数之JSON_EXTRACT示例代码

《MySQL数据库函数之JSON_EXTRACT示例代码》：本文主要介绍MySQL数据库函数之JSON_EXTRACT的相关资料,JSON_EXTRACT()函数用于从JSON文档中提取值,支持对... 目录前言基本语法路径表达式示例示例 1: 提取简单值示例 2: 提取嵌套值示例 3: 提取数组中的值注意
阅读更多...
c++中std::placeholders的使用方法

c++中std::placeholders的使用方法

《c++中std::placeholders的使用方法》std::placeholders是C++标准库中的一个工具,用于在函数对象绑定时创建占位符,本文就来详细的介绍一下,具有一定的参考价值,感兴... 目录1. 基本概念2. 使用场景3. 示例示例 1：部分参数绑定示例 2：参数重排序4. 注意事项5.
阅读更多...
使用C++将处理后的信号保存为PNG和TIFF格式

使用C++将处理后的信号保存为PNG和TIFF格式

《使用C++将处理后的信号保存为PNG和TIFF格式》在信号处理领域,我们常常需要将处理结果以图像的形式保存下来,方便后续分析和展示,C++提供了多种库来处理图像数据,本文将介绍如何使用stb_ima... 目录1. PNG格式保存使用stb_imagephp_write库1.1 安装和包含库1.2 代码解
阅读更多...
C++实现封装的顺序表的操作与实践

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

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

使用C++实现单链表的操作与实践

《使用C++实现单链表的操作与实践》在程序设计中,链表是一种常见的数据结构,特别是在动态数据管理、频繁插入和删除元素的场景中,链表相比于数组,具有更高的灵活性和高效性,尤其是在需要频繁修改数据结构的应... 目录一、单链表的基本概念二、单链表类的设计1. 节点的定义2. 链表的类定义三、单链表的操作实现四、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2