unordered_map底层buket的数据结构是什么

unordered_map底层buket的数据结构是一个基于链表的哈希表，由桶和链表组成，用于实现键值对的存储与快速查询、插入、删除等操作。unordered_map是C++中的哈希表实现，它用于存储键值对并支持快速的查找、插入和删除操作。

一、unordered_map底层buket的数据结构是什么

unordered_map底层buket的数据结构是一个基于链表的哈希表，由桶和链表组成，用于实现键值对的存储与快速查询、插入、删除等操作。unordered_map是C++中的哈希表实现，它用于存储键值对并支持快速的查找、插入和删除操作。在实现中，unordered_map内部维护了一个桶（bucket）数组，该数组的每个元素是一个链表。哈希函数将键值对的键映射到桶数组的下标，然后将该键值对插入到对应桶的链表中。因此，unordered_map的桶实际上是由链表构成的。

每个桶的数据结构采用的是链表，这是因为哈希冲突可能导致多个键被映射到同一个桶中。当出现哈希冲突时，unordered_map会将新插入的键值对插入到该桶对应的链表的头部。当查找某个键时，unorderedmap首先对其进行哈希函数的映射，然后在对应桶的链表中顺序查找，直到找到对应的键值对或链表末尾。

二、unordered_map概述

1、简介

unordered_map 容器，直译过来就是”无序 map 容器”的意思，是C++中一种无序关联式容器。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。unordered_map 容器，直译过来就是”无序 map 容器”的意思。所谓“无序”，指的是 unordered_map 容器不会像 map 容器那样对存储的数据进行排序。换句话说，unordered_map 容器和 map 容器仅有一点不同，即 map 容器中存储的数据是有序的，而 unordered_map 容器中是无序的。

2、定义

模板定义如下：

template < class Key,                        //键值对中键的类型
           class T,                          //键值对中值的类型
           class Hash = hash<Key>,           //容器内部存储键值对所用的哈希函数
           class Pred = equal_to<Key>,       //判断各个键值对键相同的规则
           class Alloc = allocator< pair<const Key,T> >  // 指定分配器对象的类型
           > class unordered_map;

3、优缺点及适用场景

• 优点：内部实现了哈希表，因此其查找速度是常量级别的。
• 缺点：哈希表的建立比较耗费时间。
• 适用场景：对于查找问题，unordered_map会更加高效一些，因此遇到查找问题，常会考虑一下用unordered_map。

4、实例

std::unordered_map<std::string, std::int> umap; //定义
umap.insert(Map::value_type("test", 1));//增加
//根据key删除,如果没找到n=0
auto n = umap.erase("test")   //删除
auto it = umap.find(key) //改
if(it != umap.end()) 
    it->second = new_value; 
//map中查找x是否存在
umap.find(x) != map.end()//查
//或者
umap.count(x) != 0

三、C++语言特点

1、与C语言的兼容性

C++与C语言完全兼容，C语言的绝大部分内容可以直接用于C++的程序设计，用C语言编写的程序可以不加修改地用于C++。

2、数据封装和数据隐藏

在C++中，类是支持数据封装的工具，对象则是数据封装的实现。C++通过建立用户定义类支持数据封装和数据隐藏。

在面向对象的程序设计中，将数据和对该数据进行合法操作的函数封装在一起作为一个类的定义。对象被说明为具有一个给定类的变量。每个给定类的对象包含这个类所规定的若干私有成员、公有成员及保护成员。完好定义的类一旦建立，就可看成完全封装的实体，可以作为一个整体单元使用。类的实际内部工作隐藏起来，使用完好定义的类的用户不需要知道类的工作原理，只要知道如何使用它即可。

3、支持继承和重用

在C++现有类的基础上可以声明新类型，这就是继承和重用的思想。通过继承和重用可以更有效地组织程序结构，明确类间关系，并且充分利用已有的类来完成更复杂、深入的开发。新定义的类为子类，成为派生类。它可以从父类那里继承所有非私有的属性和方法，作为自己的成员。

4、多态性

采用多态性为每个类指定表现行为。多态性形成由父类和它们的子类组成的一个树型结构。在这个树中的每个子类可以接收一个或多个具有相同名字的消息。当一个消息被这个树中一个类的一个对象接收时，这个对象动态地决定给予子类对象的消息的某种用法。多态性的这一特性允许使用高级抽象。

继承性和多态性的组合，可以轻易地生成一系列虽然类似但独一无二的对象。由于继承性，这些对象共享许多相似的特征。由于多态性，一个对象可有独特的表现方式，而另一个对象有另一种表现方式。

延伸阅读1：C++ STL简介

STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。从根本上说，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。