哈希表的实现

STL中的哈希表使用的是链地址法。来人，上图！

• 哈希表中的bucket（篮子）所维护的list不是list也不是slist，而是其自己定义的hashtable_node数据结构组成的linked-list
• 而哈希表的bucket聚合体本身使用vector进行存储。
• 哈希表的迭代器仅提供前进操作，不提供后退操作
• 哈希表在设计篮子数量时，内置了28个质数[53,97,193,…,429496729]
• 创建哈希表时会根据存入元素个数就近选择大于或等于元素个数的质数作为哈希表容器的容量
• 而每个篮子所维护的linked-list长度也等于哈希表的容量
• 如果插入哈希表的元素个数大于篮子数，就会进行重建哈希表的操作
• 重建哈希表会寻找下一个质数，然后重新计算每个元素在哈希表中的位置

traits的技法

traits也就是我们常说的萃取机，利用“内嵌型别”的编程技巧和编译器的template参数推导功能，来增强C++型别认证能力。

常用的有：

• iterator_traits特性萃取机
• type_traits性别萃取机

iterator_traits

特性萃取机能够给外界获取以下5种型别：

• value_type：迭代器所指对象的型别
• difference_type：两个迭代器之间的距离
• pointer：迭代器所指向的型别
• reference：迭代器所引用的型别
• iterator_category

type_traits

关注的是型别的特性，例如这个型别是否具备默认构造函数？是否具备拷贝构造函数？赋值运算符？析构函数？如果答案是否定的，便可以直接操作内存的方式来提高效率。

一般来说，支持以下5种类型的判断：

1
2
3
4
5

__type_traits<T>::has_trivial_default_constructor
__type_traits<T>::has_trivial_copy_constructor
__type_traits<T>::has_trivial_assignment_operator
__type_traits<T>::has_trivial_destructor
__type_traits<T>::is_POD_type

但是由于编译器只针对class object形式的参数进行参数推导，所以bool不作为返回结果。

问题来了，如果不用bool值，那应该用什么呢？实际上使用的是一种空的结构体：

1
2

struct __true_type{};
struct __false_type{};

因为上述两个结构体没有成员数据，所以也就占用1个字节，所以并不会带来负担

当然，我们也可以针对自定义的类型进行type_traits的特化版本

1
2
3
4
5
6
7

template<> struct __type_traits<MyClass>{
	typedef __true_type has_trivial_default_constructor;
	typedef __false_type has_trivial_copy_constructor;
	typedef __false_type has_trivial_assignment_operator;
	typedef __false_type has_trivial_destructor;
	typedef __false_type is_POD_type;
};

空间配置器

背景：首先我们需要了解一下为什么我们需要二级空间配置器

1. 我们动态申请内存是需要在堆上申请
2. 但如果我们频繁在堆上申请释放内存，会在堆上造成很多外部碎片，浪费内存空间
3. 而且每次的malloc、free函数等操作，使空间会增加附加信息，降低空间的利用率
4. 所以随着外部碎片的增加，内存分配器找不到合适的内存时需要合并空闲块，会降低工作效率和浪费时间

所以大佬们引入了二级空间适配器，当开辟内存小于等于128bytes时，便视为用二级空间配置器来开辟小块内存。

在STL中，一般默认优先使用二级空间配置器，如果大于128bytes时再转去使用一级空间配置器。

一级空间配置器

其中重要的函数就是allocate()、deallocate()、reallocate()。实际上还是以malloc()、free()、realloc()等C函数执行内存分配。大致的分配过程：

• allocate()分配内存，本事还是使用malloc()来分配，成功直接返回，否则调用处理函数
• 失败时，如果用户自定义了内存分配失败的处理函数就调用该函数，否则抛出异常
• 处理完分配失败处理函数后，再尝试继续分配。

二级空间配置器

• 维护16条链表，分别是0-15号链表，最小8字节，以8字节逐渐递增，最大128字节。
• 你传入一个字节参数，表示你需要多大的内存，会自动帮你校对到第几号链表（如需要13bytes空间，我们会给它分配16bytes大小）
• 在找到合适你的链表后查看链表是否为空，如果不为空直接从对应的free_list中拔出，将已经拨出的指针向后移动一位。
• 对应的free_list为空，先看其内存池是不是空时，如果内存池不为空：
  • 先检验它剩余空间是否够20个节点大小（即所需内存大小(提升后) * 20），若足够则直接从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接拨出。
  • 如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
  • 如果连一个节点内存都不能满足的话，则将内存池中剩余的空间挂在相应的free_list中，然后再给内存池申请内存。
• 内存池为空，此时二级空间配置器会使用malloc()从heap上申请内存，（一次所申请的内存大小为2 * 所需节点内存大小（提升后）* 20 + 一段额外空间），申请40块，一半拿来用，一半放内存池中。
• 如果malloc()还是失败了，说明heap上没有足够空间分配给我们了，这时，二级空间配置器会从比所需节点空间大的free_list中一一搜索，从比它所需节点空间大的free_list中拔除一个节点来使用。如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级适配器了。
• 释放时调用deallocate()函数，若释放的n>128，则调用一级空间配置器，否则就直接将内存块挂上自由链表的合适位置。

缺点：

• 因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数，这时若你需要1个字节，它会给你8个字节，即浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造成很多内部碎片；

• 二级空间配置器是在堆上申请大块的狭义内存池，然后用自由链表管理，供现在使用，在程序执行过程中，它将申请的内存一块一块都挂在自由链表上，即不会还给操作系统，并且它的实现中所有成员全是静态的，所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：

  • 即我不断的开辟小块内存，最后整个堆上的空间都被挂在自由链表上，若我想开辟大块内存就会失败；
  • 若自由链表上挂很多内存块没有被使用，当前进程又占着内存不释放，这时别的进程在堆上申请不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。

vector和list

vector

• 和数组类似，拥有一段连续的内存空间，并且起始地址不变。
• 因此能高效的进行随机存取，时间复杂度为o(1);
• 但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。
• 当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。
• 连续存储结构：vector是可以实现动态增长的对象数组，支持对数组高效率的访问和在数组尾端的删除和插入操作，在中间和头部删除和插入相对不易，需要挪动大量的数据。
• 它与数组最大的区别就是vector不需程序员自己去考虑容量问题，库里面本身已经实现了容量的动态增长，而数组需要程序员手动写入扩容函数进形扩容。

list

• list是由双向链表实现的，因此内存空间是不连续的。
• 只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);
• 但由于链表的特点，能高效地进行插入和删除。
• 非连续存储结构：list是一个双链表结构，支持对链表的双向遍历。每个节点包括三个信息：元素本身，指向前一个元素的节点（prev）和指向下一个元素的节点（next）。
• 因此list可以高效率的对数据元素任意位置进行访问和插入删除等操作。由于涉及对额外指针的维护，所以开销比较大。

区别

• vector的随机访问效率高，但在插入和删除时（不包括尾部）需要挪动数据，不易操作。
• list的访问要遍历整个链表，它的随机访问效率低。但对数据的插入和删除操作等都比较方便，改变指针的指向即可。
• list是单向的，
• vector是双向的。
• vector中的迭代器在使用后就失效了，
• 而list的迭代器在使用之后还可以继续使用。
• list不提供随机访问，所以不能用下标直接访问到某个位置的元素，要访问list里的元素只能遍历，不过你要是只需要访问list的最后N个元素的话，可以用反向迭代器来遍历

vector

• size()函数返回的是已用空间大小
• capacity()返回的是总空间大小
• capacity()-size()则是剩余的可用空间大小。
• size()==capacity()，说明vector目前的空间已被用完，如果再添加新元素，则会引起vector空间的动态增长。

动态扩容

• 由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。
• 因此，可以使用reserve(n)预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。
• 只有当n>capacity()时，调用reserve(n)才会改变vector容量。

1. 空的vector对象，size()和capacity()都为0

2. 当空间大小不足时，新分配的空间大小为原空间大小的2倍。

   不同的编译器，vector有不同的扩容大小。在vs下是1.5倍，在GCC下是2倍；

3. 使用reserve()预先分配一块内存后，在空间未满的情况下，不会引起重新分配，从而提升了效率。

4. 当reserve()分配的空间比原空间小时，也是不会引起重新分配的。

5. resize()函数只改变容器的元素数目，未改变容器大小（但是如果元素数目大于容器大小，那么也会改变容器大小嗷）。

6. 用reserve(size_type)只是扩大capacity值，这些内存空间可能还是“野”的，如果此时使用[]来访问，则可能会越界。而resize(size_type new_size)会真正使容器具有new_size个对象。

• 空间和时间的权衡。简单来说， 空间分配的多，平摊时间复杂度低，但浪费空间也多。
• 使用k=2增长因子的问题在于，每次扩展的新尺寸必然刚好大于之前分配的总和，也就是说，之前分配的内存空间不可能被使用。这样对内存不友好。最好把增长因子设为(1,2)
• 对比可以发现采用采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。

释放空间

• 由于vector的内存占用空间只增不减
• 比如你首先分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个。
• 所有内存空间是在vector析构时候才能被系统回收。
• empty()用来检测容器是否为空的，clear()可以清空所有元素。
• 但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。
• 如果需要空间动态缩小，可以考虑使用deque。如果vector，可以用swap()来帮助你释放内存。

1
2
3
4

vector(Vec).swap(Vec);
//将Vec的内存空洞清除；
vector().swap(Vec);
//清空Vec的内存；

删除容器元素

顺序容器

序列式容器，比如vector、deque

erase迭代器不仅使所指向被删除的迭代器失效，而且使被删元素之后的所有迭代器失效(list除外)，所以不能使用erase(it++)的方式，但是erase的返回值是下一个有效迭代器；

1

It = c.erase(it);

关联容器

关联式容器，比如map、set、multimap、multiset等

erase迭代器只是被删除元素的迭代器失效，但是返回值是void，所以要采用erase(it++)的方式删除迭代器；

1

c.erase(it++)

迭代器的实现

• 迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器内部原理的情况下遍历容器，除此之外，STL中迭代器一个最重要的作用就是作为容器与STL算法的粘合剂。
• 迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此迭代器内部必须保存一个与容器相关联的指针，然后重载各种运算操作来遍历，其中最重要的是*运算符与->运算符，以及++、--等可能需要重载的运算符重载。这和C++中的智能指针很像，智能指针也是将一个指针封装，然后通过引用计数或是其他方法完成自动释放内存的功能。
• 最常用的迭代器的相应型别有五种：value_type、difference_type、pointer、reference、iterator_catagoly;

map和set的实现

• 底层都是以红黑树的结构实现，因此插入删除等操作都在O(logN)时间内完成，因此可以完成高效的插入删除；
• 定义了一个模版参数，如果它是key那么它就是set，如果它是map，那么它就是map；底层是红黑树，实现map的红黑树的节点数据类型是key+value，而实现set的节点数据类型是value
• 因为map和set要求是自动排序的，红黑树能够实现这一功能，而且时间复杂度比较低。

map的插入数据

1
2
3
4
5
6
7
8
9
10
11

//用insert函数插入pair数据，
mapStudent.insert(pair<int, string>(1, "student_one")); 

//用insert函数插入value_type数据
mapStudent.insert(map<int, string>::value_type (1, "student_one"));

//在insert函数中使用make_pair()函数
mapStudent.insert(make_pair(1, "student_one")); 

//用数组方式插入数据
mapStudent[1] = "student_one"; 

unordered_map(hash_map)和map

• unordered_map和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序
• 存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历
• 所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些
• 那么如果是自定义类型，那么就需要自己重载operator<或者hash_value()了
• 如果需要内部元素自动排序，使用map，不需要排序使用unordered_map
• unordered_map底层使用的是hash_table，而hash_table使用的开链法进行冲突避免，所有hash_map采用开链法进行冲突解决。
• 当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值，即当前数组的长度乘以加载因子的值的时候，就要自动扩容
• 扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。

越界访问下标

• 通过下标访问vector中的元素时不会做边界检查，即便下标越界
  • 也就是说，下标与first迭代器相加的结果超过了finish迭代器的位置，程序也不会报错，而是返回这个地址中存储的值。
  • 如果想在访问vector中的元素时首先进行边界检查，可以使用vector中的at函数。通过使用at函数不但可以通过下标访问vector中的元素，而且在at函数内部会对下标进行边界检查。
• map的下标运算符[]的作用是：将key作为下标去执行查找，并返回相应的值；如果不存在这个key，就将一个具有该key和value的默认值插入这个map。

vector删除元素

• erase()函数，只能删除内容，不能改变容量大小;
• erase()函数，它删除了itVect迭代器指向的元素，并且返回要被删除的itVect之后的迭代器，迭代器相当于一个智能指针;
• clear()函数，只能清空内容，不能改变容量大小;
• 如果要想在删除内容的同时释放内存，那么你可以选择deque容器。

map中[]和find()

• map的下标运算符[]的作用是：

将关键码作为下标去执行查找，并返回对应的值；如果不存在这个关键码，就将一个具有该关键码和值类型的默认值的项插入这个map。

• map的find()函数的作用：

用关键码执行查找，找到了返回该位置的迭代器；如果不存在这个关键码，就返回尾迭代器。

list与queue的区别

• list不再能够像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在；
• list插入操作和结合才做都不会造成原有的list迭代器失效;
• list不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针；
• list不像vector那样有可能在空间不足时做重新配置、数据移动的操作，所以插入前的所有迭代器在插入操作之后都仍然有效；
• deque是一种双向开口的连续线性空间，所谓双向开口，意思是可以在头尾两端分别做元素的插入和删除操作；可以在头尾两端分别做元素的插入和删除操作；
• deque和vector最大的差异，一在于deque允许常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量概念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，deque没有所谓的空间保留功能。

allocator()和deallocator()

• 第一级配置器直接使用malloc()、free()和relloc()，第二级配置器视情况采用不同的策略：当配置区块超过128bytes时，视之为足够大，便调用第一级配置器；当配置器区块小于128bytes时，为了降低额外负担，使用复杂的内存池整理方式，而不再用一级配置器；
• 第二级配置器主动将任何小额区块的内存需求量上调至8的倍数，并维护16个free-list，各自管理大小为8~128bytes的小额区块；
• 空间配置函数allocate()，首先判断区块大小，大于128就直接调用第一级配置器，小于128时就检查对应的free-list。如果free-list之内有可用区块，就直接拿来用，如果没有可用区块，就将区块大小调整至8的倍数，然后调用refill()，为free-list重新分配空间；
• 空间释放函数deallocate()，该函数首先判断区块大小，大于128bytes时，直接调用一级配置器，小于128bytes就找到对应的free-list然后释放内存。

哈希表扩容

• 哈希表中的元素称为bucket，而由桶所链接的元素称为节点node,其中存入桶元素的容器为stl本身很重要的一种序列式容器——vector容器。之所以选择vector为存放桶元素的基础容器，主要是因为vector容器本身具有动态扩容能力，无需人工干预。
• 向前操作：首先尝试从目前所指的节点出发，前进一个位置，由于节点被安置于list内，所以利用节点的next指针即可轻易完成前进操作，如果目前正巧是list的尾端，就跳至下一个bucket身上，那正是指向下一个list的头部节点。

常见容器

• vector 底层数据结构为数组 ，支持快速随机访问

• list 底层数据结构为双向链表，支持快速增删

• deque 底层数据结构为一个中央控制器和多个缓冲区，支持首尾快速增删（中间不能快速增减，需要挪动元素），也支持随机访问

  • deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:

    [队列1] –> [队列2] –>[队列3] –> …

  • 每个队列保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品

• stack 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

• queue 底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

• stack和queue其实是适配器,而不叫容器，因为是对容器的再封装

• priority_queue 的底层数据结构一般为vector为底层容器，堆heap为处理规则来管理底层容器实现

• set底层数据结构为红黑树，有序，不重复

• multiset底层数据结构为红黑树，有序，可重复

• map底层数据结构为红黑树，有序，不重复

• multimap底层数据结构为红黑树，有序，可重复

• unordered_set底层数据结构为哈希表，无序，不重复

• unordered_multiset底层数据结构为哈希表，无序，可重复

• unordered_map底层数据结构为哈希表，无序，不重复

• unordered_multimap底层数据结构为哈希表，无序，可重复

vector增删的实现

• 新增元素：

vector通过一个连续的数组存放元素，如果集合已满，在新增数据的时候，就要分配一块更大的内存，将原来的数据复制过来，释放之前的内存，在插入新增的元素；

• 对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了 ；
• 初始时刻vector的capacity为0，塞入第一个元素后capacity增加为1；
• 不同的编译器实现的扩容方式不一样，VS2015中以1.5倍扩容，GCC以2倍扩容。

采用成倍方式扩容，可以保证常数的时间复杂度，而增加指定大小的容量只能达到O(n)的时间复杂度，因此，使用成倍的方式扩容。

• 考虑可能产生的堆空间浪费，成倍增长倍数不能太大，使用较为广泛的扩容方式有两种，以2二倍的方式扩容，或者以1.5倍的方式扩容。
• 以2倍的方式扩容，导致下一次申请的内存必然大于之前分配内存的总和，导致之前分配的内存不能再被使用，所以最好倍增长因子设置为(1,2)之间；
• 向量容器vector的成员函数pop_back()可以删除最后一个元素
• 而函数erase()可以删除由一个iterator指出的元素，也可以删除一个指定范围的元素。
• 还可以采用通用算法remove()来删除vector容器中的元素；
• 不同的是：采用remove()一般情况下不会改变size()的大小，而pop_back()与erase()等成员函数会改变size()的大小。

容器对应的迭代器

unordered_map和map的区别

• map支持键值的自动排序，底层机制是红黑树，红黑树的查询和维护时间复杂度均为O(logn)，但是空间占用比较大，因为每个节点要保持父节点、孩子节点及颜色的信息
• unordered_map是C++ 11新添加的容器，底层机制是哈希表，通过hash函数计算元素位置，其查询时间复杂度为O(1)，维护时间与bucket桶所维护的list长度有关，但是建立hash表耗时较大
• 从两者的底层机制和特点可以看出：map适用于有序数据的应用场景，unordered_map适用于高效查询的应用场景

哈希冲突的解决方案

开放定址法

线性探测

使用hash函数计算出的位置如果已经有元素占用了，则向后依次寻找，找到表尾则回到表头，直到找到一个空位

二次探测

使用hash函数计算出的位置如果已经有元素占用了，按照1^2、2^2、3^2…的步长依次寻找，如果步长是随机数序列，则称之为伪随机探测

链地址法

每个表格维护一个list，如果hash函数计算出的格子相同，则按顺序存在这个list中

再哈希法

发生冲突时使用另一种hash函数再计算一个地址，直到不冲突

公共溢出区

一旦hash函数计算的结果相同，就放入公共溢出区

感谢

转载自https://github.com/forthespada/InterviewGuide，感激大佬的整理和分享！