经常使用的数据结构

用户头像
hasWhere
关注
发布于: 2020 年 09 月 30 日
经常使用的数据结构

Java的ConcurrentHashMap

答案:红黑树

红黑树是完全平衡二叉树,能够保证查询和插入的稳定性。由于HashMap数据是直接加载到内存当中,不涉及到磁盘IO,所以对于树的深度没有要求到极致,必须小,红黑树足以满足。

缺点:只能根据明确的key值进行查找,不支持范围查找。

Redis的List

答案:跳表

跳表类似于多层索引的数据结构,感觉和二分查找有点类似,就是通过缩小查找范围,快速定位数据。Redis数据默认也是加载到内存,因此对于索引层级其实也不是特别敏感。

Mysql的索引

答案:B+树

B+树是平衡多叉树,与B-树比较明显的区别是,B-树的节点中都存在着数据;B+树只有在叶子节点才存在数据,同时叶子节点又形成链表,方便范围查询。由于Mysql索引默认是存储在磁盘中,如果树的深度过大,会导致内存多次进行磁盘IO,从磁盘中获取数据。



布隆过滤器

答案:bitmap

bitmap(位图),通过巧妙的方式,减小数据存储空间。Hash算法来计算是否存在数据,和HashMap比较像,只是存储空间占用比较小。用来判断是否重复比较合适。



总结:感觉有些地方还不是特别明白,暂时先简单记录,方便后面进行回顾。

对于数据结构理解,只有俩种结构:数组和链表,其他复杂或者好用的数据结构,都是根据具体业务场景对于此俩种数据结构的组合。

对于算法的理解是,只有俩种算法:查找算法和排序算法,其中排序算法也是为了查找。



算法中感觉难度比较大的是动态规划。

发布于: 2020 年 09 月 30 日 阅读数: 25
用户头像

hasWhere

关注

间歇性努力的学习渣 2018.04.20 加入

通过博客来提高下对自己的要求

评论

发布
暂无评论
经常使用的数据结构