Set & Map
06.集合 ToySet
代码链接:https://github.com/skychx/Toy-Data-Structures/blob/main/06-Set/ToySet.d.ts
ToySet
有两个实现:
有序无序有两个角度,一种是按照元素存取的顺序,一种是元素和元素之间的关系。下文的有序无序指的是后者
- 有序集合:Set 中的元素都是有序排列的(基于搜索树实现)
- BSTSet:基于 BST 二分搜索树实现,
add
has
delete
时间复杂度平均为O(logn)
,最坏情况下退化为链表,时间复杂度变为O(n)
- AVLSet:基于 AVL Tree 实现,时间复杂度稳定为
O(logn)
,根据 AVL 特性,不会退化为链表。
- BSTSet:基于 BST 二分搜索树实现,
- 无序集合:Set 中的元素都是无序排列的
- JS Set:ES6 内置 Set,性能最优
- JS Object Set:ES6 Object 模拟的 Set,只比 Set 慢一点点(根据 JS 规范,Object string key 排序是按插入顺序排序的)
- LinkedListSet:基于 LinkedList 链表实现,
add
has
delete
时间复杂度均为O(n)
- ArraySet:基于 ToyArray 动态数组实现,
add
has
delete
时间复杂度均为O(n)
- HashTableSet:HashTable 模拟的 Set
API:
基础 | 增 | 删 | 查 | 改 |
---|---|---|---|---|
getSize() | add(e) | delete(e) | has(e) | |
isEmpty() |
07.映射 ToyMap
代码链接:https://github.com/skychx/Toy-Data-Structures/blob/main/07-Map/ToyMap.d.ts
有序无序有两个角度,一种是按照元素存取的顺序,一种是元素和元素之间的关系。下文的有序无序指的是后者
ToyMap
有两个实现:
- 有序映射:Map 中的元素都是有序排列的(基于搜索树实现)
- BSTMap:基于 BST 二分搜索树实现,
add
get
has
delete
set
时间复杂度平均为O(logn)
,最坏情况下退化为链表,时间复杂度变为O(n)
- AVLMap:基于 AVL Tree 实现,时间复杂度稳定为
O(logn)
,根据 AVL 特性,不会退化为链表。
- BSTMap:基于 BST 二分搜索树实现,
- 无序映射:Map 中的元素都是无序排列的
- JS Map:ES6 内置 Map,性能最优
- JS Object Map:ES6 Object 模拟的 Map,只比 Map 慢一点点(根据 JS 规范,Object string key 排序是按插入顺序排序的)
- LinkedListMap:基于 LinkedList 链表实现,
add
get
has
delete
set
时间复杂度均为O(n)
- HashTableMap:HashTable 模拟的 Map
API:
基础 | 增 | 删 | 查 | 改 |
---|---|---|---|---|
getSize() | add(k, v) | delete(k) | get(k) | set(k, v) |
isEmpty() | has(k) |
一个小尾巴
欢迎关注公众号:卤代烃实验室:专注于前端技术、混合开发、图形学领域,只写有深度的技术文章