reserve 以后一次都不搬家
补全:插入 1000 个元素之前先 reserve 够,然后统计插入过程中 bucket_count() 变了几次。一次都没变输出 一次都没有,否则输出 还是搬了。 (本题用 g++ -std=c++17 -O0 编译。)
补全:结构体键的相等比较
补全 PointEq:两个点的 x、y 都相等才算同一个点。然后数一数 5 个点里有几个不同的点。 (本题用 g++ -std=c++17 -O0 编译。)
坏哈希会挤成一桶
下面的 BadHash 对任何键都返回 0。补全:插入 100 个不同的键之后,找出最大的那个桶里有几个元素(用 bucket_size(i))。 (本题用 g++ -std=c++17 -O0 编译。)
手动 rehash 把桶开大
补全:插完 1000 个元素之后,调用 rehash 把桶数开到至少 4096,再检查桶数和元素个数。输出「桶够不够/元素个数」,格式如 桶够了/1000。 (本题用 g++ -std=c++17 -O0 编译。)
够用的哈希表至少要有什么
第 1 步:第 7 格已经有 15 第 2 步:23 % 8 也等于 7:撞上了 第 3 步:第 7 格挂一串,两个都装下 第 4 步:查 23:先到第 7 格,再比 15 第 5 步:不是它,往后比:找到 23 24 17 13 15 1
为什么说哈希表平均是 O(1)
哈希表的复杂度要加「平均」两个字,是因为【0】。
五个人占了几个格子
运行下面这段程序(链地址法,8 格): #include <iostream> #include <string> #include <utility> #include <vector> u
第一步:格子、定位和插入
最终作品第一步:在 HashMap 里写好构造函数(开 cap 个空格子)、slot(取余定位)和 put(追加到那一格)。放完五个人之后输出第 7 格里有几个。 (本题用 g++ -std=c++17 -O0 编译。)
第二步:接上按键查
给它加上 get:找到返回名字,找不到返回 没这个人。查 23 号(它和 15 号挤在同一格),输出结果。 (本题用 g++ -std=c++17 -O0 编译。)
第三步:接上删除别误伤邻居
加上 del。删掉 15 号之后,把两件事一起输出:15 号查出来是什么、23 号查出来是什么,中间用 / 隔开。只删掉该删的那条才对得上,把整格清空或者一条没删都会露馅。 (本题用 g++ -std=c++17 -O0 编译。)