为了减少冲突经常需要开辟更多的桶，但更多的桶需要更大的存储空间，特别是元素数量不确定的时候，桶的数量选择变得两难，随着装载的元素变多，冲突加剧，在扩容的时候，将需要对已存在的元素重新哈希，这是很费的点。
哈希表的冲突极端情况下会退化成链表，当初设想的快速查找变得不再可行，HashMap是普通哈希表的改进版，结合哈希和二叉平衡搜索树。
另一个常用来做查找的结构是红黑树，它能确保最坏情况下，有logN的时间复杂度，但红黑树的查找过程需要沿着链走，不同结点内存通常不连续，CACHE命中性经常很差，红黑树的中序遍历结果是有序的，这是哈希表不具备的，另外，红黑树不存在哈希表那般预估容量难的问题。
基于有序数组的二分查找二分查找的时间复杂度也是logN，跟红黑树一致，但二分查找的空间局部性更好，不过二分查找有约束，它只能在有序数组上进行，所以，如果你需要在固定的数据集合（比如配置数据）做查找，二分查找是个不错的选择。
跳表（Skip List）跳表增加了向前指针，是一种多层结构的有序链表，插入一个值时有一定概率晋升到上层形成间接的索引。
跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
跳表适合大量并发写的场景，可以认为是随机平衡的二叉搜索树，不存在红黑树的再平衡问题。Redis强大的ZSet底层数据结构就是哈希加跳表。
相比哈希表和红黑树，跳表用的不那么多。
数据结构的实现优化我们通常只会讲数据的逻辑结构，但数据的实现（存储）结构也会影响性能。
数组在存储上一定是逻辑地址连续的，但链表不具有这样的特点，链表通过链域寻找临近节点，如果相邻节点在地址上发散，则沿着链域访问效率不高，所以实现上可以通过从单独的内存配置器分配结点（尽量内存收敛）来优化访问效率，同样的方法也适应红黑树、哈希表等其他结构。
排序尽量对指针、索引、ID排序，而不要对对象本身排序，因为交换对象比交换地址/索引慢；求topN不要做全排序；非稳定排序能满足要求不要搞稳定排序。
延迟计算 & 写时拷贝延迟计算和写时拷贝（COW）思想上是一样的，即可以通过把计算尽量推迟来减少计算开销。
我拿游戏服务器开发来举例，假设玩家的战斗力（fight）是通过等级，血量，称号等其他属性计算出来的，我们可以在等级、血量、称号变化的时候立即重算fight，但血量可能变化比较频繁，所以就会需要频繁重算战力。通过延迟计算，我们可以为战力添加一个dirtyFlag，在等级、血量、称号变化的时候设置dirtyFlag，等到真正需要用到战力的时候（GetFight函数）里判断dirtyFlag，如果dirtyFlag为true则重算战力并清dirtyFlag，如果dirtyFlag为false则直接返回fight值。
写时拷贝（COW）跟这个差不多，linux kernel在fork进程的时候，子进程会共享父进程的地址空间，只有在子进程对自身地址空间写的时候，才会clone一份出来，同样，string的设计也用到了类似的思想。
预计算有些值可以提前计算出结果并保存起来，不用重复计算的尽量不重复计算，特别是循环内的计算，要避免重复的常量计算，C++甚至增加了一个constexpr的关键词。
增量更新增量更新的原理不复杂，只做增量，只做DIFF，不做全量，这个思想有很多应用场景。
举个例子，游戏服务器每隔一段时间需要把玩家的属性（比如血量、魔法值等）同步到客户端，简单的做法是把所有属性打包一次性全发送过去，这样比较耗费带宽，可以考虑为每个属性编号，在发送的时候，只发送变化的属性。
在发送端，编码一个变化的属性的时候，需要发送一个属性编号+属性值的对子，接收端类似，先解出属性编号，再解出属性值，这种方式可能需要牺牲一点CPU换带宽。
3、代码优化 内存优化（a）小对象分配器
C的动态内存分配是介于系统和应用程序的中间层，malloc/free本身体现的就是一种按需分配+复用的思想。
当你调用malloc向glibc的动态内存分配器ptmalloc申请6字节的内存，实际耗费的会大于6字节，6是动态分配块的有效载荷，动态内存分配器会为chunk添加首部和尾部，有时候还会加一下填充，所以，真正耗费的存储空间会远大于6字节，在我的机器上，通过malloc_usable_size发现申请6字节，返回的chunk，实际可用的size为24，加上首尾部就更多了。
但你真正申请（可用）的大小是6字节，可见，动态内存分配的chunk内有大量的碎片，这就是内碎片，而外碎片是存在chunk之间的，是另一个问题。