New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Set和Map的底层结构 #1

Open

fish519 opened this issue May 4, 2019 · 0 comments

Owner

fish519 commented May 4, 2019

研发过程中干的蠢事：
把immutable中的orderset打平成array用indexOf去查找索引值

Set的查询效率是O(logn)，底层的数据结构是一个二叉平衡搜索树，红黑树。

Map 二元组集合，底层数据结构也是由红黑树来实现，key来排序和确定树中的位置，由key去得到value值。

红黑树条件：
1、根是黑节点
2、红节点带两个黑节点
3、叶子节点是黑节点
4、任意一个节点到所有叶子节点的路径包含相同的黑节点

// 未完待补充...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment