注:这只是我视频内容的底稿,有些细节只在视频内容里呈现了,所以有不清楚的地方请先看视频!
大家好,欢迎来到 C++ 한번 봅시다.的第三期,在这一起里我想和大家探讨一下关于 STL里面的一个著名的容器类,표준: 무질서 지도的性能问题.

표준: 무질서 지도也会有性能问题？

很多小伙伴都知道,我们一般不推荐大家使用 지도.这是因为 지도.会自动把你插入的元素按照他们的键值排序,为了实现这样的 이음매有好的中文翻译么?),一般的 C++实现会用红黑树或者 AVL树这样的自平衡二叉树.这样的话每次插入新的元素,查找元素和删除元素的操作都是 O(logn),所以从原理上讲 지도.就是比较慢的.所以当我们需要一个类似 활용단어참조里的 자전的数据结构时,我们一般会使用 std::무질서 그림, std::무질서 그림和 활용단어참조里的 자전一样,都可以理解为一个哈希表的具体实现.它的插入,查找,删除都是 O(1)的,比 지도.好了不少.
那么,표준: 무질서 지도已经用上了理论上讲操作最优的实现,为什么我们还在谈它的性能问题呢?
我曾在一家 헤지펀드工作,当时在我们内部的代码库中用 C++实现了一个像 구렁이 판다一样的 데이터 프레임类,我在这个 헤지펀드的第一个 계획就是为这个 C++ 데이터 프레임做性能调优.在这个 데이터 프레임内部我们保存数据时用到的就是 무질서한 지도也就是在我做性能调优的过程中通过不断地 분석하다发现很多 데이터 프레임的瓶颈其实是在 무질서한 지도
给大家举个例子,我们参考这个简单的面试题:给你一个整数 벡터请你返回一个 부울告诉我这个 벡터里有没有重复的元素.
加入我们不考虑 해시 세트一个简单的实现可以写成这样:

#include <unordered_map>

using namespace std;

class UnorderedMapSolution {
public:
  bool containsDuplicate(const vector<int> &nums) {
    unordered_map<int, int> m;
    for (auto i : nums) {
      m[i] += 1;
    }

    for (auto i : m) {
      if (i.second > 1)
        return true;
    }

    return false;
  }
};

这里的 무질서 지도其实可以替换成任何一个 해시표的实现,包括我们刚刚谈到的 지도.不久前 구글开源了他们内部的 abesil 평면 산열 매핑类,这也是一个 해시표我在网上还找到了一些 C++爱好者的作品,那么我们可以看一下他们之间的对比.

我们可以看到,同样的算法,如果我们用 지도.比 표준: 무질서 지도大约慢了三倍,然而如果我们用 구글的实现,那么他们比 STL又快了 셋倍,就连社区里的爱好者自己写的,也比 짤랑짤랑这些“久经考验”的开源库自带的 C++STL实现快,那么这是为什么呢?

해시표的实现

在我们的算法和数据结构的课程里我们一般会介绍下面这样的一种哈希表的实现,每个哈希表都是一个定长的数组,每个 열쇠.可以用一个 해시 함수被影射到这个数组中的一个 감방每个 감방其实包含了一个链表.

当我们插入一个元素的时候,我们会根据它的 열쇠.算出相对的哈希值,如果两个元素的哈希值是相同的,那么我们就会把后插入的元素加入在它哈希值对应的那个链表的最后.这种处理哈希碰撞的办法我们一般叫做 개방 산열或者叫做 폐식 주소 지정
但是我们其实还有另一种处理哈希碰撞的办法,与 개방 산열相对应,可以叫做 폐식 산열也可以叫做 공개 주소 지정

在两个元素的哈希值相同时,与其我们把后插入的这个元素放在一个链表中,我们可以把这个元素放在哈希表本来就有的这个数组当中,只要我们能够找到一个还没有被使用的 감방那么我们就可以把后插入的元素放在这个空的 감방当中.至于怎么找这个 감방一般使用的办法有三种:

선형 탐지: h(x,k+1)=a*h(x,k)+c

양자 탐지: h(x,k+1) = ah(x,k)^2+bh(x,k)+c

쌍해시 탐지: h(x,k+1)=h(h(x,k))

这里 k代表我们调用这个哈希函数的次数.如果一个元素在第一次哈希之后的 감방不是空的,那么我们就用上面的 조사하다技巧为这个元素再找一个新的 감방
最简单的 선형 탐지 함수可以是 h(x,k+1)=h(x,k)+1
大家可以猜一下:구글的实现用了那种哈希碰撞的解决办法?
答案是第二种,也就是我们说的 공개 연설而且 구글用的就是最简单的 선형 탐지那么为什么这样写出来的哈希表比较快呢?给大家一点提示-->从硬件的角度考虑考虑?
答案是缓存,我们都知道如果我们的程序如果是顺序处理连续的内存,那么 중앙처리기会把我们正在处理的内存附近的内容读到他自己的缓存当中,下次如果 중앙처리기需要处理已经在缓存中的内容时,它就不需要从系统的主存重新读取相同的内容.
因为 구글的哈希表用没有使用链表,而是采用了 공개 주소 지정 +用一个 어레이保存所有的键值对的方案,所以它的 표현才远好于使用了传统的基于链表的实现.
那么 표준: 무질서 지도是不是可以改成这种实现呢?答案是暂时不行:如果我们看 STL的文档,那么我们会发现 무질서 지도把它内部试用 통+체인 시계的细节也暴露在了它的 미국 석유 학회当中.

Hyrum's Law:
With a sufficient number of users of an API, it does not matter what you promise in the contract, all observable behaviors of you system will be depended on by somebody

问题

那么 구글 평면도是不是没有缺点呢?포인터 실패提一句.

更深一点

对我们普通程序员了解这些有什么用呢:

주닐: 캐시가 중요해!가능한 연속 데이터 구조 사용

고급: 개원이 중요합니다!개원이 없으면 우리가 무엇을 할 수 있겠는가?

모두: API 디자인이 중요합니다. API를 가진 이유는 디테일을 숨기기 위해서입니다!

재미있는 사실

구글의 매 순간:

C++ 해시 테이블

에 1%의 CPU 소모

C++ 해시표

는 4%의 RAM을 소모했다

참고 문헌