网易互娱面经

4.vector和list的区别和实现，vector和list的查找，插入删除的时间复杂度

STL包括几个部分：容器，算法（泛型算法），迭代器三个主要部分

vector插入效率On，查找效率O1，list插入效率O1，查找效率On

vector的底层数据结构为数组，list的底层数据结构为双向链表，特点是支持快速的增删。
queue为单向队列，为先入先出原则。deque为双向队列

5.***缺页置换咋弄的，LRU底层实现

letcode搜LRU可以查到，大概思路就是用双向链表+hash表实现，完成查找用hashmap时间复杂度为O1，插入用双向list效率也为O1.

class LRUCache {
private:
    int cap;
    // 双链表：装着 (key, value) 元组
    list<pair<int, int>> ***;
    // 哈希表：key 映射到 (key, value) 在 *** 中的位置
    unordered_map<int, list<pair<int, int>>::iterator> map;
public:
    LRUCache(int capacity) {
        this->cap = capacity; 
    }
    
    int get(int key) {
        auto it = map.find(key);
        // 访问的 key 不存在
        if (it == map.end()) return -1;
        // key 存在，把 (k, v) 换到队头
        pair<int, int> kv = *map[key];
        ***.erase(map[key]);
        ***.push_front(kv);
        // 更新 (key, value) 在 *** 中的位置
        map[key] = ***.begin();
        return kv.second; // value
    }
    
    void put(int key, int value) {

        /* 要先判断 key 是否已经存在 */ 
        auto it = map.find(key);
        if (it == map.end()) {
            /* key 不存在，判断 *** 是否已满 */ 
            if (***.size() == cap) {
                // *** 已满，删除尾部的键值对腾位置
                // *** 和 map 中的数据都要删除
                auto lastPair = ***.back();
                int lastKey = lastPair.first;
                map.erase(lastKey);
                ***.pop_back();
            }
            // *** 没满，可以直接添加
            ***.push_front(make_pair(key, value));
            map[key] = ***.begin();
        } else {
            /* key 存在，更改 value 并换到队头 */
            ***.erase(map[key]);
            ***.push_front(make_pair(key, value));
            map[key] = ***.begin();
        }
    }
};

7.hash冲突的链表法链表长度太长了咋办？

将链表变为红黑树，看到java中JDK1.8中就是这么干的，理想情况下，在随机哈希代码下，桶中的节点频率遵循泊松分布，

文中给出了桶长度k的频率表。由频率表可以看出，桶的长度超过8的概率非常非常小。所以作者应该是根据概率统计而选择了8作为阀值。

2.写vector怎么实现

自己可以查到，着重看push_back操作怎么做的，深度剖析STL源码里面应该有，但楼主没看过，没时间。