Skip to content

D
Docs

OpenHarmony / Docs
大约 1 年 前同步成功

通知 159
Star 292
Fork 28
D
Docs

体验新版 GitCode，发现更多精彩内容 >>

切换分支/标签
查找文件 普通视图历史永久链接Permalink
nonlinear-container.md 17.0 KB
Newer Older
G
update docs  
ge-yafang 已提交
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
# 非线性容器


非线性容器实现能快速查找的数据结构，其底层通过hash或者红黑树实现，包括HashMap、HashSet、TreeMap、TreeSet、LightWeightMap、LightWeightSet、PlainArray七种。非线性容器中的key及value的类型均满足ECMA标准。


## HashMap

[HashMap](../reference/apis/js-apis-hashmap.md)可用来存储具有关联关系的key-value键值对集合，存储元素中key是唯一的，每个key会对应一个value值。

HashMap依据泛型定义，集合中通过key的hash值确定其存储位置，从而快速找到键值对。HashMap的初始容量大小为16，并支持动态扩容，每次扩容大小为原始容量的2倍。HashMap底层基于HashTable实现，冲突策略采用链地址法。

HashMap和[TreeMap](../reference/apis/js-apis-treemap.md)相比，HashMap依据键的hashCode存取数据，访问速度较快。而TreeMap是有序存取，效率较低。

[HashSet](../reference/apis/js-apis-hashset.md)基于HashMap实现。HashMap的输入参数由key、value两个值组成。在HashSet中，只对value对象进行处理。

需要快速存取、删除以及插入键值对数据时，推荐使用HashMap。

HashMap进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
22 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
23 24 25 26 27 28 29 30 31 32 
| 增加元素 | 通过set(key: K, value: V)函数每次在HashMap增加一个键值对。 |
| 访问元素 | 通过get(key: K)获取key对应的value值。 |
| 访问元素 | 通过keys()返回一个选代器对象，包含map中的所有key值。 |
| 访问元素 | 通过value()返回一个迭代器对象，包含map中的所有value值。 |
| 访问元素 | 通过entries()返回一个迭代器对象，包含map中的所有键值对。 |
| 访问元素 | forEach(callbackfn: (value: T, index?: number, map?: HashMap<K,V>) => void,thisArg?: Object)访问整个map的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator<[K,V]>选代器进行数据访问。 |
| 修改元素 | 通过replace(key: K, newValue: V)对指定key对应的value值进行修改操作。 |
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, map?: HashMap<K, V>) => void,thisArg?: Object)对map中元素进行修改操作。 |
| 删除元素 | 通过remove(key: K)对map中匹配到的键值对进行删除操作。 |
G
update docs  
ge-yafang 已提交
33 
| 删除元素 | 通过clear()清空整个map集合。 |
G
update docs  
ge-yafang 已提交
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 


## HashSet

[HashSet](../reference/apis/js-apis-hashset.md)可用来存储一系列值的集合，存储元素中value是唯一的。

HashSet依据泛型定义，集合中通过value的hash值确定其存储位置，从而快速找到该值。HashSet初始容量大小为16，支持动态扩容，每次扩容大小为原始容量的2倍。value的类型满足ECMA标准中要求的类型。HashSet底层数据结构基于HashTable实现，冲突策略采用链地址法。

HashSet基于[HashMap](../reference/apis/js-apis-hashmap.md)实现。在HashSet中，只对value对象进行处理。

HashSet和[TreeSet](/reference/apis/js-apis-treeset.md)相比，HashSet中的数据无序存放，即存放元素的顺序和取出的顺序不一致，而TreeSet是有序存放。它们集合中的元素都不允许重复，但HashSet允许放入null值，TreeSet不允许。

可以利用HashSet不重复的特性，当需要不重复的集合或需要去重某个集合的时候使用。

HashSet进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
51 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
52 53 54 55 56 57 58 
| 增加元素 | 通过add(value: T)函数每次在HashSet增加一个键值对。 |
| 访问元素 | 通过value()返回一个选代器对象，包含set中的所有value值。 |
| 访问元素 | 通过entries()返回一个选代器对象，包含类似键值对的数组，键值都是value。 |
| 访问元素 | 通过forEach(callbackfn: (value: T, index?:  number, set?:  HashSet<T>) => void, thisArg?: Object)访问整个set的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():lterablelterator<T>选代器进行数据访问。 |
| 修改元素 | 通过forEach(callbackfn:(value: T, index?: number, set?: HashSet<T>) => void,thisArg?: Object)对set中value进行修改操作。 |
| 删除元素 | 通过remove(value: T)对set中匹配到的值进行删除操作。 |
G
update docs  
ge-yafang 已提交
59 
| 删除元素 | 通过clear()清空整个set集合。 |
G
update docs  
ge-yafang 已提交
60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 


## TreeMap

[TreeMap](../reference/apis/js-apis-treemap.md)可用来存储具有关联关系的key-value键值对集合，存储元素中key是唯一的，每个key会对应一个value值。

TreeMap依据泛型定义，集合中的key值是有序的，TreeMap的底层是一棵二叉树，可以通过树的二叉查找快速的找到键值对。key的类型满足ECMA标准中要求的类型。TreeMap中的键值是有序存储的。TreeMap底层基于红黑树实现，可以进行快速的插入和删除。

TreeMap和[HashMap](../reference/apis/js-apis-hashmap.md)相比，HashMap依据键的hashCode存取数据，访问速度较快。而TreeMap是有序存取，效率较低。

一般需要存储有序键值对的场景，可以使用TreeMap。

TreeMap进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
75 
| ------- | ------ |
G
update docs  
ge-yafang 已提交
76 77 78 79 80 81 82 
| 增加元素 | 通过set(key: K,value: V)函数每次在TreeMap增加一个键值对。 |
| 访问元素 | 通过get(key: K)获取key对应的value值。 |
| 访问元素 | 通过getFirstKey()获取map中排在首位的key值。 |
| 访问元素 | 通过getLastKey()获取map中排在未位的key值。 |
| 访问元素 | 通过keys()返回一个迭代器对象，包含map中的所有key值。 |
| 访问元素 | 通过value()返回一个迭代器对象，包含map中的所有value值。 |
| 访问元素 | 通过entries()返回一个选代器对象，包含map中的所有键值对。 |
G
update docs  
ge-yafang 已提交
83 84 
| 访问元素 | 通过forEach(callbackfn: (value: T, index?: number, map?: TreeMap\<K, V>) =&gt; void, thisArg?: Object)访问整个map的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator\<[K,V]>选代器进行数据访问。 |
G
update docs  
ge-yafang 已提交
85 
| 修改元素 | 通过replace(key: K,newValue: V)对指定key对应的value值进行修改操作。 |
G
update docs  
ge-yafang 已提交
86 
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, map?: TreeMap\<K, V>) =&gt; void, thisArg?: Object)对map中元素进行修改操作。 |
G
update docs  
ge-yafang 已提交
87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 
| 删除元素 | 通过remove(key: K)对map中匹配到的键值对进行删除操作。 |
| 删除元素 | 通过clear()清空整个map集合。 |


## TreeSet

[TreeSet](../reference/apis/js-apis-treemap.md)可用来存储一系列值的集合，存储元素中value是唯一的。

TreeSet依据泛型定义，集合中的value值是有序的，TreeSet的底层是一棵二叉树，可以通过树的二叉查找快速的找到该value值，value的类型满足ECMA标准中要求的类型。TreeSet中的值是有序存储的。TreeSet底层基于红黑树实现，可以进行快速的插入和删除。

TreeSet基于[TreeMap](../reference/apis/js-apis-treemap.md)实现，在TreeSet中，只对value对象进行处理。TreeSet可用于存储一系列值的集合，元素中value唯一且有序。

TreeSet和[HashSet](../reference/apis/js-apis-hashset.md)相比，HashSet中的数据无序存放，而TreeSet是有序存放。它们集合中的元素都不允许重复，但HashSet允许放入null值，TreeSet不允许。

一般需要存储有序集合的场景，可以使用TreeSet。

TreeSet进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
106 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 
| 增加元素 | 通过add(value: T)函数每次在HashSet增加一个键值对。 |
| 访问元素 | 通过value()返回一个选代器对象，包含set中的所有value值。 |
| 访问元素 | 通过entries()返回一个选代器对象，包含类似键值对的数组，键值都是value。 |
| 访问元素 | 通过getFirstValue()获取set中排在首位的value值。 |
| 访问元素 | 通过getLastValue()获取set中排在未位的value值。 |
| 访问元素 | 通过forEach(callbackfn: (value: T, index?: number, set?: TreeSet&lt;T&gt;) =&gt; void, thisArg?: Object)访问整个set的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator&lt;T&gt;选代器进行数据访问。 |
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, set?: TreeSet&lt;T&gt;) =&gt; void,thisArg?: Object)对set中value进行修改操作。 |
| 删除元素 | 通过remove(value: T)对set中匹配到的值进行删除操作。 |
| 删除元素 | 通过clear()清空整个set集合。 |


## LightWeightMap

[LigthWeightMap](../reference/apis/js-apis-lightweightmap.md)可用来存储具有关联关系的key-value键值对集合，存储元素中key是唯一的，每个key会对应一个value值。LigthWeightMap依据泛型定义，采用更加轻量级的结构，集合中的key值的查找依赖于hash值以及二分查找算法，通过一个数组存储hash值，然后映射到其他数组中的key值以及value值，key的类型满足ECMA标准中要求的类型。

初始默认容量大小为8，每次扩容大小为原始容量的2倍。LigthWeightMap底层标识唯一key通过hash实现，其冲突策略为线性探测法，查找策略基于二分查找法。

LightWeightMap和[HashMap](../reference/apis/js-apis-hashmap.md)都是用来存储键值对的集合，LightWeightMap占用内存更小。

当需要存取key-value键值对时，推荐使用占用内存更小的LightWeightMap。

LigthWeightMap进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
132 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 
| 增加元素 | 通过set(key: K,value: V)函数每次在LigthWeightMap增加一个键值对。 |
| 访问元素 | 通过get(key: K)获取key对应的value值。 |
| 访问元素 | 通过getlndexOfKey(key: K)获取map中指定key的index。 |
| 访问元素 | 通过getindexOfValue(value: V)获取map中指定value的index。 |
| 访问元素 | 通过keys()返回一个选代器对象，包含map中的所有key值。 |
| 访问元素 | 通过value()返回一个选代器对象，包含map中的所有value值。 |
| 访问元素 | 通过entries()返回一个选代器对象，包含map中的所有键值对。 |
| 访问元素 | 通过getKeyAt(index: number)获取指定index对应的key值。 |
| 访问元素 | 通过getValueAt(index：number)获取指定index对应的value值。 |
| 访问元素 | 通过forEach(callbackfn: (value: T, index?: number, map?: LigthWeightMap&lt;K, V&gt;) =&gt; void,thisArg? Object)访问整个map的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator&lt;[K,V]&gt;迭代器进行数据访问。 |
| 修改元素 | 通过setValueAt(key: K,newValue: V)对指定key对应的value值进行修改操作。 |
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, map?: LigthWeightMap&lt;K, V&gt;) =&gt; void,thisArg?: Object)对map中元素进行修改操作。 |
| 删除元素 | 通过remove(key: K)对map中匹配到的键值对进行删除操作。 |
| 删除元素 | 通过removeAt(index: number)对map中指定index的位置进行删除操作。 |
| 删除元素 | 通过clear()清空整个map集合。 |


## LightWeightSet

[LigthWeightSet](../reference/apis/js-apis-lightweightset.md)可用来存储一系列值的集合，存储元素中value是唯一的。

LigthWeightSet依据泛型定义，采用更加轻量级的结构，初始默认容量大小为8，每次扩容大小为原始容量的2倍。集合中的value值的查找依赖于hash以及二分查找算法，通过一个数组存储hash值，然后映射到其他数组中的value值，value的类型满足ECMA标准中要求的类型。

LigthWeightSet底层标识唯一value基于hash实现，其冲突策略为线性探测法，查找策略基于二分查找法。

LightWeightSet和[HashSet](../reference/apis/js-apis-hashset.md)都是用来存储键值的集合，LightWeightSet的占用内存更小。

当需要存取某个集合或是对某个集合去重时，推荐使用占用内存更小的LightWeightSet。

LigthWeightSet进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
166 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 
| 增加元素 | 通过add(obj: T)函数每次在LigthWeightSet增加一个键值对。 |
| 访问元素 | 通过getlndexOf(key: T)获取对应的index值。 |
| 访问元素 | 通过value()返回一个迭代器对象，包含map中的所有value值。 |
| 访问元素 | 通过entries()返回一个选代器对象，包含map中的所有键值对。 |
| 访问元素 | 通过getValueAt(index: number)获取指定index对应的value值。 |
| 访问元素 | 通过forEach(callbackfn: (value: T, index?: number,  set?:  LigthWeightSet&lt;T&gt;) =&gt; void,thisArg?: Object)访问整个set的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator&lt;T&gt;选代器进行数据访问。 |
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, set?: LigthWeightSet&lt;T&gt;) =&gt; void,thisArg?: Object)对set中元素进行修改操作。 |
| 删除元素 | 通过remove(key: K)对set中匹配到的键值对进行删除操作。 |
| 删除元素 | 通过removeAt(index: number)对set中指定index的位置进行删除操作。 |
| 删除元素 | 通过clear()清空整个set集合。 |


## PlainArray

[PlainArray](../reference/apis/js-apis-plainarray.md)可用来存储具有关联关系的键值对集合，存储元素中key是唯一的，并且对于PlainArray来说，其key的类型为number类型。每个key会对应一个value值，类型依据泛型的定义，PlainArray采用更加轻量级的结构，集合中的key值的查找依赖于二分查找算法，然后映射到其他数组中的value值。

初始默认容量大小为16，每次扩容大小为原始容量的2倍。PlainArray的查找策略基于二分查找法。

PlainArray和[LightWeightMap](../reference/apis/js-apis-lightweightmap.md)都是用来存储键值对，且均采用轻量级结构，但PlainArray的key值类型只能为number类型。

当需要存储key值为number类型的键值对时，可以使用PlainArray。

PlainArray进行增、删、改、查操作的相关API如下：

| 操作 | 描述 |
G
update docs  
ge-yafang 已提交
193 
| -------- | ------ |
G
update docs  
ge-yafang 已提交
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 
| 增加元素 | 通过add(key: number,value: T)函数每次在PlainArray增加一个键值对。 |
| 访问元素 | 通过get(key: number)获取key对应的value值。 |
| 访问元素 | 通过getlndexOfKey(key: number)获取PlainArray中指定key的index。 |
| 访问元素 | 通过getlndexOfValue(value: T)获取PlainArray中指定value的index。 |
| 访问元素 | 通过getKeyAt(index: number)获取指定index对应的key值。 |
| 访问元素 | 通过getValueAt(index: number)获取指定index对应的value值。 |
| 访问元素 | 通过forEach(callbackfn: (value: T, index?: number, PlainArray?: PlainArray&lt;T&gt;) =&gt;void, thisArg?: Object)访问整个plainarray的元素。 |
| 访问元素 | 通过\[Symbol.iterator]():Iterablelterator&lt;[number, T]&gt;选代器进行数据访问。 |
| 修改元素 | 通过setValueAt(index:number, value: T)对指定index对应的value值进行修改操作。 |
| 修改元素 | 通过forEach(callbackfn: (value: T, index?: number, PlainArray?: PlainArray&lt;T&gt;) =&gt; void,thisArg?: Object)对plainarray中元素进行修改操作。 |
| 删除元素 | 通过remove(key: number)对plainarray中匹配到的键值对进行删除操作。 |
| 删除元素 | 通过removeAt(index: number)对plainarray中指定index的位置进行删除操作。 |
| 删除元素 | 通过removeRangeFrom(index: number, size: number)对plainarray中指定范围内的元素进行删除操作。 |
| 删除元素 | 通过clear()清空整个PlainArray集合。 |


## 非线性容器的使用

此处列举常用的非线性容器HashMap、TreeMap、LightWeightMap、PlainArray的使用示例，包括导入模块、增加元素、访问元素及修改等操作，示例代码如下所示：


```js
// HashMap
import HashMap from '@ohos.util.HashMap'; // 导入HashMap模块

let hashMap = new HashMap();
hashMap.set('a', 123);
hashMap.set(4, 123); // 增加元素
console.info(`result: ${hashMap.hasKey(4)}`); // 判断是否含有某元素
console.info(`result: ${hashMap.get('a')}`); // 访问元素

// TreeMap
import TreeMap from '@ohos.util.TreeMap'; // 导入TreeMap模块

let treeMap = new TreeMap();
treeMap.set('a', 123);
treeMap.set('6', 356); // 增加元素
console.info(`result: ${treeMap.get('a')}`); // 访问元素
console.info(`result: ${treeMap.getFirstKey()}`); // 访问首元素
console.info(`result: ${treeMap.getLastKey()}`); // 访问尾元素

// LightWeightMap
import LightWeightMap from '@ohos.util.LightWeightMap'; // 导入LightWeightMap模块

let lightWeightMap = new LightWeightMap();
lightWeightMap.set('x', 123);
lightWeightMap.set('8', 356); // 增加元素
console.info(`result: ${lightWeightMap.get('a')}`); // 访问元素
console.info(`result: ${lightWeightMap.get('x')}`); // 访问元素
console.info(`result: ${lightWeightMap.getIndexOfKey('8')}`); // 访问元素

// PlainArray
import PlainArray from '@ohos.util.PlainArray' // 导入PlainArray模块

let plainArray = new PlainArray();
plainArray.add(1, 'sdd');
plainArray.add(2, 'sff'); // 增加元素
console.info(`result: ${plainArray.get(1)}`); // 访问元素
console.info(`result: ${plainArray.getKeyAt(1)}`); // 访问元素
```