1# Nonlinear Containers
2
3
4Nonlinear containers, underpinned by hash tables or red-black trees, implement a data structure that enables quick search. There are several types of nonlinear containers: **HashMap**, **HashSet**, **TreeMap**, **TreeSet**, **LightWeightMap**, **LightWeightSet**, and **PlainArray**. The types of **key** and **value** in nonlinear containers must meet the ECMA standard.
5
6
7## HashMap
8
9[HashMap](../reference/apis-arkts/js-apis-hashmap.md) is used to store a set of associated key-value (KV) pairs. In a hash map, each key is unique and corresponds to a value.
10
11**HashMap** uses generics. In a hash map, a key is located based on its hash code. The initial capacity of a hash map is 16, and it has capacity doubled in each dynamic expansion. The bottom layer of **HashMap** is implemented based on a hash table. It uses chaining to avoid collisions in hash tables.
12
13**HashMap** is faster in accessing data than [TreeMap](../reference/apis-arkts/js-apis-treemap.md), because the former accesses the keys based on the hash codes, whereas the latter stores and accesses the keys in sorted order.
14
15[HashSet](../reference/apis-arkts/js-apis-hashset.md) is implemented based on **HashMap**. The input parameter of **HashMap** consists of **key** and **value**. In **HashSet**, only the **value** object is processed.
16
17You are advised to use **HashMap** when you need to quickly access, remove, and insert KV pairs.
18
19**HashMap** provides the following Create, Read, Update, and Delete (CRUD) APIs.
20
21| Operation | Description |
22| -------- | ------ |
23| Create | Use **set(key: K, value: V)** to add an element (a KV pair) to this container. |
24| Read | Use **get(key: K)** to obtain the value of the specified key. |
25| Read | Use **keys()** to return an iterator that contains all the keys in this container. |
26| Read | Use **values()** to return an iterator that contains all the values in this container. |
27| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
28| Read | Use **forEach(callbackFn: (value?: V, key?: K, map?: HashMap<K, V>) => void, thisArg?: Object)** to traverse the elements in this container. |
29| Read | Use **\[Symbol.iterator]():IterableIterator&lt;[K,V]&gt;** for data access. |
30| Update | Use **replace(key: K, newValue: V)** to change the value of the specified key. |
31| Update | Use **forEach(callbackFn: (value?: V, key?: K, map?: HashMap<K, V>) => void, thisArg?: Object)** to modify an element in this container. |
32| Delete | Use **remove(key: K)** to remove an element with the specified key. |
33| Delete | Use **clear()** to clear this container. |
34
35
36## HashSet
37
38[HashSet](../reference/apis-arkts/js-apis-hashset.md) is used to store a set of values, each of which is unique in a hash set.
39
40**HashSet** uses generics. In a hash set, a value is located based on its hash code. The initial capacity of a hash set is 16, and it has capacity doubled in each dynamic expansion. The type of **value** must comply with the ECMA standard. The bottom layer of **HashSet** is implemented based on a hash table. It uses chaining to avoid collisions in hash tables.
41
42**HashSet** is implemented based on [HashMap](../reference/apis-arkts/js-apis-hashmap.md). In **HashSet**, only the **value** object is processed.
43
44Unlike [TreeSet](../reference/apis-arkts/js-apis-treeset.md), which stores and accesses data in sorted order, **HashSet** stores data in a random order. This means that **HashSet** may use a different order when storing and accessing elements. Both of them allow only unique elements. However, null values are allowed in **HashSet**, but not in **TreeSet**, because null values may affect the order of elements in the container.
45
46You are advised to use **HashSet** when you need a set that has only unique elements or need to deduplicate a set.
47
48**HashSet** provides the following CRUD APIs.
49
50| Operation | Description |
51| -------- | ------ |
52| Create | Use **add(value: T)** to add a value to this container. |
53| Read | Use **values()** to return an iterator that contains all the values in this container. |
54| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
55| Read | Use **forEach(callbackFn: (value?: T, key?: T, set?: HashSet\<T>) => void, thisArg?: Object)** to traverse the elements in this container. |
56| Read | Use **\[Symbol.iterator]():IterableIterator&lt;T&gt;** for data access. |
57| Update | Use **forEach(callbackFn: (value?: T, key?: T, set?: HashSet\<T>) => void, thisArg?: Object)** to change a value in this container. |
58| Delete | Use **remove(value: T)** to remove a value. |
59| Delete | Use **clear()** to clear this container. |
60
61
62## TreeMap
63
64[TreeMap](../reference/apis-arkts/js-apis-treemap.md) is used to store a set of associated KV pairs. In a tree map, each key is unique and corresponds to a value.
65
66**TreeMap** uses generics, and the keys in a tree map are ordered. The bottom layer of **TreeMap** is a binary tree, which supports quick search of KV pairs through the children (left child and right child) of the tree. The type of **key** must comply with the ECMA standard. Keys in a tree map are stored in order. The bottom layer of **TreeMap** is implemented based on the red-black tree and supports quick insertion and removal.
67
68[HashMap](../reference/apis-arkts/js-apis-hashmap.md) is faster in accessing data than **TreeMap**, because the former accesses the keys based on the hash codes, whereas the latter stores and accesses the keys in sorted order.
69
70You are advised to use **TreeMap** when you need to store KV pairs in sorted order.
71
72**TreeMap** provides the following CRUD APIs.
73
74| Operation | Description |
75| ------- | ------ |
76| Create | Use **set(key: K, value: V)** to add an element (a KV pair) to this container. |
77| Read | Use **get(key: K)** to obtain the value of the specified key. |
78| Read | Use **getFirstKey()** to obtain the first key in this container. |
79| Read | Use **getLastKey()** to obtain the last key in this container. |
80| Read | Use **keys()** to return an iterator that contains all the keys in this container. |
81| Read | Use **values()** to return an iterator that contains all the values in this container. |
82| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
83| Read | Use **forEach(callbackFn: (value?: V, key?: K, map?: TreeMap<K, V>) => void, thisArg?: Object)** to traverse the elements in this container. |
84| Read | Use **\[Symbol.iterator]():IterableIterator\<[K,V]>** for data access. |
85| Update | Use **replace(key: K, newValue: V)** to change the value of the specified key. |
86| Update | Use **forEach(callbackFn: (value?: V, key?: K, map?: TreeMap<K, V>) => void, thisArg?: Object)** to modify an element in this container. |
87| Delete | Use **remove(key: K)** to remove an element with the specified key. |
88| Delete | Use **clear()** to clear this container. |
89
90
91## TreeSet
92
93[TreeSet](../reference/apis-arkts/js-apis-treeset.md) is used to store a set of values, each of which is unique in a tree set.
94
95**TreeSet** uses generics, and the values in a tree set are ordered. The bottom layer of **TreeSet** is a binary tree, which supports quick search of a value through the children (left child and right child) of the tree. The type of **value** must meet the ECMA standard. Values in a tree set are stored in order. The bottom layer of **TreeSet** is implemented based on the red-black tree and supports quick insertion and removal.
96
97**TreeSet** is implemented based on [TreeMap](../reference/apis-arkts/js-apis-treemap.md). In **TreeSet**, only **value** objects are processed. **TreeSet** can be used to store values, each of which must be unique.
98
99[HashSet](../reference/apis-arkts/js-apis-hashset.md) stores data in a random order, whereas **TreeSet** stores data in sorted order. Both of them allow only unique elements. However, null values are allowed in **HashSet**, but not in **TreeSet**, because null values may affect the order of elements in the container.
100
101You are advised to use **TreeSet** when you need to store data in sorted order.
102
103**TreeSet** provides the following CRUD APIs.
104
105| Operation | Description |
106| -------- | ------ |
107| Create | Use **add(value: T)** to add a value to this container. |
108| Read | Use **values()** to return an iterator that contains all the values in this container. |
109| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
110| Read | Use **getFirstValue()** to obtain the first value in this container. |
111| Read | Use **getLastValue()** to obtain the last value in this container. |
112| Read | Use **forEach(callbackFn: (value?: T, key?: T, set?: TreeSet\<T>) => void, thisArg?: Object)** to traverse the elements in this container. |
113| Read | Use **\[Symbol.iterator]():IterableIterator&lt;T&gt;** for data access. |
114| Update | Use **forEach(callbackFn: (value?: T, key?: T, set?: TreeSet\<T>) => void, thisArg?: Object)** to change a value in this container. |
115| Delete | Use **remove(value: T)** to remove a value. |
116| Delete | Use **clear()** to clear this container. |
117
118
119## LightWeightMap
120
121[LightWeightMap](../reference/apis-arkts/js-apis-lightweightmap.md) is used to store a set of associated KV pairs. In a lightweight map, each key is unique and corresponds to a value. **LightWeightMap** uses generics and a more lightweight structure. It uses the hash code to uniquely identify a key at the bottom layer. It uses linear probing to avoid collisions. In a lightweight map, a key is located by using the hash code and binary search algorithm. The hash code is stored in an array and mapped to a key and its value in another array. The type of **key** must comply with the ECMA standard.
122
123The default initial capacity of a lightweight map is 8, and it has capacity doubled in each expansion.
124
125Compared with [HashMap](../reference/apis-arkts/js-apis-hashmap.md), which can also store KV pairs, **LightWeightMap** occupies less memory.
126
127You are advised to use **LightWeightMap** when you need to store and access **KV pairs**.
128
129**LightWeightMap** provides the following CRUD APIs.
130
131| Operation | Description |
132| -------- | ------ |
133| Create | Use **set(key: K, value: V)** to add an element (a KV pair) to this container. |
134| Read | Use **get(key: K)** to obtain the value of the specified key. |
135| Read | Use **getIndexOfKey(key: K)** to obtain the index of the specified key. |
136| Read | Use **getIndexOfValue(value: V)** to obtain the index of the first occurrence of the specified value. |
137| Read | Use **keys()** to return an iterator that contains all the keys in this container. |
138| Read | Use **values()** to return an iterator that contains all the values in this container. |
139| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
140| Read | Use **getKeyAt(index: number)** to obtain the key of an element at a given position (specified by **index**). |
141| Read | Use **getValueAt(index: number)** to obtain the value of an element at a given position (specified by **index**). |
142| Read | Use **forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap<K, V>) => void, thisArg?: Object)** to traverse the elements in this container. |
143| Read | Use **\[Symbol.iterator]():IterableIterator&lt;[K,V]&gt;** for data access. |
144| Update | Use **setValueAt(index: number, newValue: V)** to change the value of an element at a given position (specified by **index**). |
145| Update | Use **forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap<K, V>) => void, thisArg?: Object)** to modify an element in this container. |
146| Delete | Use **remove(key: K)** to remove an element with the specified key. |
147| Delete | Use **removeAt(index: number)** to remove an element at a given position (specified by **index**). |
148| Delete | Use **clear()** to clear this container. |
149
150
151## LightWeightSet
152
153[LightWeightSet](../reference/apis-arkts/js-apis-lightweightset.md) is used to store a set of values, each of which is unique in a lightweight set.
154
155**LightWeightSet** uses generics and a lightweight structure. Its default initial capacity is 8, and it has capacity doubled in each expansion. In a lightweight set, a value is located by using the hash code and binary search algorithm. The hash code is stored in an array and mapped to a value in another array. The type of **value** must comply with the ECMA standard.
156
157**LightWeightSet** uses the hash code to uniquely identify a value at the bottom layer. It uses linear probing to avoid collisions and adopts the binary search algorithm.
158
159Compared with [HashSet](../reference/apis-arkts/js-apis-hashset.md), which can also store values, **LightWeightSet** occupies less memory.
160
161You are advised to use **LightWeightSet** when you need a set that has only unique elements or need to deduplicate a set.
162
163**LightWeightSet** provides the following CRUD APIs.
164
165| Operation | Description |
166| -------- | ------ |
167| Create | Use **add(obj: T)** to add a value to this container. |
168| Read | Use **getIndexOf(key: T)** to obtain the index of a key. |
169| Read | Use **values()** to return an iterator that contains all the values in this container. |
170| Read | Use **entries()** to return an iterator that contains all the elements in this container. |
171| Read | Use **getValueAt(index: number)** to obtain the value of an element at a given position (specified by **index**). |
172| Read | Use **forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet\<T>) => void, thisArg?: Object)** to traverse the elements in this container. |
173| Read | Use **\[Symbol.iterator]():IterableIterator&lt;T&gt;** for data access. |
174| Update | Use **forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet\<T>) => void, thisArg?: Object)** to change a value in this container. |
175| Delete | Use **remove(key: K)** to remove an element with the specified key. |
176| Delete | Use **removeAt(index: number)** to remove an element at a given position (specified by **index**). |
177| Delete | Use **clear()** to clear this container. |
178
179
180## PlainArray
181
182[PlainArray](../reference/apis-arkts/js-apis-plainarray.md) is used to store a set of associated KV pairs. In a plain array, each key is unique, corresponds to a value, and is of the number type. **PlainArray** uses generics and a more lightweight structure. In a plain array, a key is located by using the binary search algorithm and is mapped to a value in another array.
183
184The default initial capacity of a plain array is 16, and it has capacity doubled in each expansion.
185
186Both **PlainArray** and [LightWeightMap](../reference/apis-arkts/js-apis-lightweightmap.md) are used to store KV pairs in the lightweight structure. However, the key type of **PlainArray** can only be **number**.
187
188You are advised to use PlainArray when you need to store KV pairs whose keys are of the number type.
189
190**PlainArray** provides the following CRUD APIs.
191
192| Operation | Description |
193| -------- | ------ |
194| Create | Use **add(key: number,value: T)** to add an element (a KV pair) to this container. |
195| Read | Use **get(key: number)** to obtain the value of the specified key. |
196| Read | Use **getIndexOfKey(key: number)** to obtain the index of the specified key. |
197| Read | Use **getIndexOfValue(value: T)** to obtain the index of the specified value. |
198| Read | Use **getKeyAt(index: number)** to obtain the key of an element at a given position (specified by **index**). |
199| Read | Use **getValueAt(index: number)** to obtain the value of an element at a given position (specified by **index**). |
200| Read | Use **forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray\<T>) => void, thisArg?: Object)** to traverse the elements in this container. |
201| Read | Use **\[Symbol.iterator]():IterableIterator&lt;[number, T]&gt;** for data access. |
202| Update | Use **setValueAt(index:number, value: T)** to change the value of an element at a given position (specified by **index**). |
203| Update | Use **forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray\<T>) => void, thisArg?: Object)** to modify an element in this container. |
204| Delete | Use **remove(key: number)** to remove an element with the specified key. |
205| Delete | Use **removeAt(index: number)** to remove an element at a given position (specified by **index**). |
206| Delete | Use **removeRangeFrom(index: number, size: number)** to remove elements in a specified range. |
207| Delete | Use **clear()** to clear this container. |
208
209
210## Use of Nonlinear Containers
211
212Refer to the code snippet below to add, access, and modify elements in **HashMap**, **TreeMap**, **LightWeightMap**, **Stack**, and **PlainArray**.
213
214
215```ts
216// HashMap
217import { HashMap } from '@kit.ArkTS'; // Import the HashMap module.
218
219let hashMap1: HashMap<string, number> = new HashMap();
220hashMap1.set('a', 123);
221let hashMap2: HashMap<number, number> = new HashMap();
222hashMap2.set(4, 123); // Add an element.
223console.info(`result: ${hashMap2.hasKey(4)}`); // Check whether an element is contained.
224console.info(`result: ${hashMap1.get('a')}`); // Access an element.
225
226// TreeMap
227import { TreeMap } from '@kit.ArkTS'; // Import the TreeMap module.
228
229let treeMap: TreeMap<string, number> = new TreeMap();
230treeMap.set('a', 123);
231treeMap.set('6', 356); // Add an element.
232console.info(`result: ${treeMap.get('a')}`); // Access an element.
233console.info(`result: ${treeMap.getFirstKey()}`); // Access the first element.
234console.info(`result: ${treeMap.getLastKey()}`); // Access the last element.
235
236// LightWeightMap
237import { LightWeightMap } from '@kit.ArkTS'; // Import the LightWeightMap module.
238
239let lightWeightMap: LightWeightMap<string, number> = new LightWeightMap();
240lightWeightMap.set('x', 123);
241lightWeightMap.set('8', 356); // Add an element.
242console.info(`result: ${lightWeightMap.get('a')}`); // Access an element.
243console.info(`result: ${lightWeightMap.get('x')}`); // Access an element.
244console.info(`result: ${lightWeightMap.getIndexOfKey('8')}`); // Access an element.
245
246// PlainArray
247import { PlainArray } from '@kit.ArkTS'; // Import the PlainArray module.
248
249let plainArray: PlainArray<string> = new PlainArray();
250plainArray.add(1, 'sdd');
251plainArray.add(2,'sff'); // Add an element.
252console.info(`result: ${plainArray.get(1)}`); // Access an element.
253console.info(`result: ${plainArray.getKeyAt(1)}`); // Access an element.
254```
255