《STL源码剖析》读书笔记(三)

• 关联式容器(缩进表示基层与衍生层的关系，衍生是内含关系)

  • RB-tree(非公开)
    
    • set
    • map
    • multiset
    • multimap
  • hashtable(非标准)
    
    • hash_set(非标准)
    • hash_map(非标准)
    • hash_multiset(非标准)
    • hash_multimap(非标准)

• 二叉搜索树
  任何节点最多只能允许两个子节点

• 平衡二叉树
  确保整棵树的深度为O(logN),左右子树的高度最多差1

  • AVL tree
  • RB tree 双向迭代器，不具备随机定位能力。可参考另一篇博文：https://blog.csdn.net/hgyan25/article/details/81098291
  • AA tree

• set

  • 特性：所有元素都会根据元素的键值自动被排序。键值就是实值，实值就是键值。不允许两个元素有相同的键值。
  • 以RB tree为底层机制，几乎所有的set操作行为，都是转调用RB-tree的操作行为。

• map

  • 所有元素都会根据元素的键值自动被排序，以RB-tree为底层机制，每个节点的内容是一个pair。同时拥有实值和键值。pair的第一个元素被看做是键值，第二个元素是实值。map不允许两个元素拥有相同的键值。
  • 不能通过map的迭代器改变map的元素内容，不能修正元素的键值。因为map的键值关系到map的元素的排列规则，任意改变map元素的键值都会严重破坏map的组织。但是可以修改元素的实值。
  • 进行insert或者erase后，迭代器依然有效。
  • subscript操作符，可能作为左值运算，也可能作为右值运算
    

    T& operator[](const key_type& k){
        return (*((insert(value_type(k,T()))).first)).second;
    }

• multiset
  特性与用法与set完全相同，唯一的差别在于它允许键值重复，插入的时候用的是RB-tree的insert_equal()而不是insert_unique()

• multimap
  特性与用法与map完全相同，唯一的差别在于它允许键值重复，插入的时候用的是RB-tree的insert_equal()而不是insert_unique()

• hash_table(散列表)
  hash table可以提供所有的有名项的存取操作和删除操作，也可以视作是一种字典结构，意在提供常数时间的基本操作。

• 所有元素都是16bits且不带正负号的整数，范围为0-65535，那么用一个array来记录，每个元素值代表相应元素出现的次数。如果i出现，那么A[i]++。

  • 问题1：如果元素是32bit，那么array的大小为2^32=4GB。
  • 问题2：如果元素是字符串，无法映射到array的索引中。可以通过字符编码来实现。
  • 避免大的荒谬的array：使用某种映射函数，将大数映射为小数，将一个元素映射为一个“大小可接受之索引”，也叫hash_function。

• 解决哈希函数出现的冲突问题

  • 线性探测，依序往下一一寻找(如果到达了尾端就从头开始寻找)，直至找到一个可用空间为止。
    问题：平均插入成本的成长幅度，远高于负载系数的成长幅度
  • 二次探测，依序尝试H+1, H+4, H+9…H+i^2（可用位移法来计算）
    用于消除主集团，却可能造成次集团(可用double hashing来消除次集团)
  • 开链法：表格内的每个单元，涵盖的不只是节点(元素)，也可能是一“桶”节点。bucket维护的是一个linked list。

• SGI STL的hash table就是采用开链法
  整个hash table是由vector和linked list组成。

  • 迭代器结构
    node * cur;//迭代器目前所指之节点
    hashtable * ht;//保持对容器的连接关系，可能需要从一个bucket跳到另一个bucket
    没有后退操作，也就是没有定义所谓的逆向迭代器
  • hash table的数据结构
    bucket聚合体以vector来完成，便于动态扩充：vector

# include<hash_set>
hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc>iht(50, hash<int>, equal_to<int>());
iht.size()=0
iht.bucket_count()=53

用迭代器遍历hashtable

hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc>::iterator ite = iht.begin();
for(int i=0;i<iht.size();++i,++ite)
    cout<<*ite<<' ';
cout<<endl;

用迭代器遍历buckets
hashtable<int, int, hash<int>, identity<int>, equal_to<int>, alloc>::iterator ite = iht.begin();
for(int i=0;i<iht.bucket_count();++i)
    int n = iht.elems_in_bucket(i);
    if(n!=0){
        cout<<"bucket["<<i<<"] has "<<n<<" elems."<<endl;
    }
cout<<endl;

• hash_set

  • 以hash_table为底层实现，基本所有的hash_set的行为都是转调用hashtable的操作行为而已。
  • set元素的键值就是实值，实值就是键值
  • 插入操作用的是hash_table的insert_unique()
  • RB tree为底层的与hash table为底层的都可以用于快速搜索元素，但是hash_set没有自动排序功能

• hash_map

  • 以hash_table为底层实现，基本所有的hash_map的行为都是转调用hashtable的操作行为而已。
  • 插入操作用的是hash_table的insert_unique()
  • RB tree为底层的与hash table为底层的都可以根据键值快速搜索元素，但是hash_map没有自动排序功能

• hash_multiset

  • 以hash_table为底层实现，基本所有的hash_multiset的行为都是转调用hashtable的操作行为而已。
  • 插入操作用的是hash_table的insert_equal()
  • RB tree为底层的与hash table为底层的都可以用于快速搜索元素，但是hash_set没有自动排序功能

• hash_multiset

  • 以hash_table为底层实现，基本所有的hash_multimap的行为都是转调用hashtable的操作行为而已。
  • 插入操作用的是hash_table的insert_equal()

• HashMap的原理，内部数据结构
  hashmap用的是hash_table,查询时间复杂度为O(1).用vector来保存每个桶，每个节点又是也用linked list来记录。
  hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域进行保存。

  • 其插入过程：
    1、得到key；
    2、通过hash函数得到hash值；
    3、得到桶号（一般都为hash值对桶数求模）；
    4、存放key和value在桶内；
  • 其取值过程是：
    1、得到key；
    2、通过hash函数得到hash值；
    3、得到桶号；
    4、比较桶的内部元素是否与key相等，若不相等，则没有找到；
    5、取出相等的记录的value；

• 什么时候需要使用hash_map，什么时候需要map？
  总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望 程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。
  现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

• HashMap 怎样解决冲突，讲一下扩容过程
  hash table 用链式法来解决冲突。
  拿元素个数与bucket_vector的大小来比较，如果前者大于后者，就进行重整。
  要扩容的时候寻找下一个质数。Next_size()

  1. 设立新的bucket_vector
  2. 依序处理每个bucket所含的(串行)的每个节点
     a. 找到这个节点位于哪个新的bucket buck_num（val, n)
     b. 将bucket的指针指向下一个节点
     c. 将当前节点插入到新的bucket中，成为其对应串行的第一个节点
     d. 回到旧bucket所指的待处理的串行中，处理下一个节点
  3. 对调两个buckets. void swap (vector& x); 如果两个vector的大小不同，那么大的变小，小的变大