系统性能优化 - 数据结构

哈希表

• 哈希函数的确定

BKDR 哈希算法

调优哈希函数：提取 key 特征，增加哈希 code 区分度

扩容：增加基数

• 冲突解决方案

链表法

开放寻址法

• 序列化：快照+op log

• 位图

哈希函数的变种，主要辅助数据的主索引，判断对象是否存在

红黑树

• 本质：二叉搜索树

• 复杂度：增删改查 lg(n)

• 内部机制：变色和旋转

• 应用示例：java->TreeSet

B+树

• 本质：多叉树

• 应用示例：MySQL 索引