harmony 鸿蒙Nonlinear Containers

2023-10-30
浏览 (448)

Nonlinear Containers

Nonlinear containers implement a data structure that enables quick search. The bottom layer of nonlinear containers is implemented through hash tables or red-black trees. OpenHarmony provides the following nonlinear containers: HashMap, HashSet, TreeMap, TreeSet, LightWeightMap, LightWeightSet, and PlainArray. The types of key and value in nonlinear containers must meet the ECMA standard.

HashMap

HashMap 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.

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.

HashMap 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.

HashSet is implemented based on HashMap. The input parameter of HashMap consists of key and value. In HashSet, only the value object is processed.

You are advised to use HashMap when you need to quickly access, remove, and insert KV pairs.

HashMap provides the following Create, Read, Update, and Delete (CRUD) APIs.

Operation	Description
Adding elements	Use set(key: K, value: V) to add an element (a KV pair) to this container.
Accessing elements	Use get(key: K) to obtain the value of the specified key.
Accessing elements	Use keys() to return an iterator that contains all the keys in this container.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use forEach(callbackFn: (value?: V, key?: K, map?: HashMap) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<[K,V]> for data access.
Modifying elements	Use replace(key: K, newValue: V) to change the value of the specified key.
Modifying elements	Use forEach(callbackFn: (value?: V, key?: K, map?: HashMap) => void, thisArg?: Object) to modify an element in this container.
Deleting elements	Use remove(key: K) to remove an element with the specified key.
Deleting elements	Use clear() to clear this container.

HashSet

HashSet is used to store a set of values, each of which is unique in a hash set.

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.

HashSet is implemented based on HashMap. In HashSet, only the value object is processed.

Unlike TreeSet, 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 allows only unique elements. However, null values are allowed in HashSet, but not allowed in TreeSet.

You are advised to use HashSet when you need a set that has only unique elements or need to deduplicate a set.

HashSet provides the following CRUD APIs.

Operation	Description
Adding elements	Use add(value: T) to add a value to this container.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use forEach(callbackFn: (value?: T, key?: T, set?: HashSet<T>) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<T> for data access.
Modifying elements	Use forEach(callbackFn: (value?: T, key?: T, set?: HashSet<T>) => void, thisArg?: Object) to change a value in this container.
Deleting elements	Use remove(value: T) to remove a value.
Deleting elements	Use clear() to clear this container.

TreeMap

TreeMap is used to store a set of associated KV pairs. In a tree map, each key is unique and corresponds to a value.

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.

HashMap 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.

You are advised to use TreeMap when you need to store KV pairs in sorted order.

TreeMap provides the following CRUD APIs.

Operation	Description
Adding elements	Use set(key: K, value: V) to add an element (a KV pair) to this container.
Accessing elements	Use get(key: K) to obtain the value of the specified key.
Accessing elements	Use getFirstKey() to obtain the first key in this container.
Accessing elements	Use getLastKey() to obtain the last key in this container.
Accessing elements	Use keys() to return an iterator that contains all the keys in this container.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use forEach(callbackFn: (value?: V, key?: K, map?: TreeMap) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<[K,V]> for data access.
Modifying elements	Use replace(key: K, newValue: V) to change the value of the specified key.
Modifying elements	Use forEach(callbackFn: (value?: V, key?: K, map?: TreeMap) => void, thisArg?: Object) to modify an element in this container.
Deleting elements	Use remove(key: K) to remove an element with the specified key.
Deleting elements	Use clear() to clear this container.

TreeSet

TreeSet is used to store a set of values, each of which is unique in a tree set.

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.

TreeSet is implemented based on TreeMap. In TreeSet, only value objects are processed. TreeSet can be used to store values, each of which must be unique.

HashSet stores data in a random order, whereas TreeSet stores data in sorted order. Both of them allows only unique elements. However, null values are allowed in HashSet, but not allowed in TreeSet.

You are advised to use TreeSet when you need to store data in sorted order.

TreeSet provides the following CRUD APIs.

Operation	Description
Adding elements	Use add(value: T) to add a value to this container.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use getFirstValue() to obtain the first value in this container.
Accessing elements	Use getLastValue() to obtain the last value in this container.
Accessing elements	Use forEach(callbackFn: (value?: T, key?: T, set?: TreeSet<T>) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<T> for data access.
Modifying elements	Use forEach(callbackFn: (value?: T, key?: T, set?: TreeSet<T>) => void, thisArg?: Object) to change a value in this container.
Deleting elements	Use remove(value: T) to remove a value.
Deleting elements	Use clear() to clear this container.

LightWeightMap

LightWeightMap 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.

The default initial capacity of a lightweight map is 8, and it has capacity doubled in each expansion.

Compared with HashMap, which can also store KV pairs, LightWeightMap occupies less memory.

You are advised to use LightWeightMap when you need to store and access KV pairs.

LightWeightMap provides the following CRUD APIs.

Operation	Description
Adding elements	Use set(key: K, value: V) to add an element (a KV pair) to this container.
Accessing elements	Use get(key: K) to obtain the value of the specified key.
Accessing elements	Use getIndexOfKey(key: K) to obtain the index of the specified key.
Accessing elements	Use getIndexOfValue(value: V) to obtain the index of the first occurrence of the specified value.
Accessing elements	Use keys() to return an iterator that contains all the keys in this container.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use getKeyAt(index: number) to obtain the key of an element at a given position (specified by index).
Accessing elements	Use getValueAt(index: number) to obtain the value of an element at a given position (specified by index).
Accessing elements	Use forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<[K,V]> for data access.
Modifying elements	Use setValueAt(index: number, newValue: V) to change the value of an element at a given position (specified by index).
Modifying elements	Use forEach(callbackFn: (value?: V, key?: K, map?: LightWeightMap) => void, thisArg?: Object) to modify an element in this container.
Deleting elements	Use remove(key: K) to remove an element with the specified key.
Deleting elements	Use removeAt(index: number) to remove an element at a given position (specified by index).
Deleting elements	Use clear() to clear this container.

LightWeightSet

LightWeightSet is used to store a set of values, each of which is unique in a lightweight set.

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.

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.

Compared with HashSet, which can also store values, LightWeightSet occupies less memory.

You are advised to use LightWeightSet when you need a set that has only unique elements or need to deduplicate a set.

LightWeightSet provides the following CRUD APIs.

Operation	Description
Adding elements	Use add(obj: T) to add a value to this container.
Accessing elements	Use getIndexOf(key: T) to obtain the index of a key.
Accessing elements	Use values() to return an iterator that contains all the values in this container.
Accessing elements	Use entries() to return an iterator that contains all the elements in this container.
Accessing elements	Use getValueAt(index: number) to obtain the value of an element at a given position (specified by index).
Accessing elements	Use forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet<T>) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<T> for data access.
Modifying elements	Use forEach(callbackFn: (value?: T, key?: T, set?: LightWeightSet<T>) => void, thisArg?: Object) to change a value in this container.
Deleting elements	Use remove(key: K) to remove an element with the specified key.
Deleting elements	Use removeAt(index: number) to remove an element at a given position (specified by index).
Deleting elements	Use clear() to clear this container.

PlainArray

PlainArray 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.

The default initial capacity of a plain array is 16, and it has capacity doubled in each expansion.

Both PlainArray and LightWeightMap are used to store KV pairs in the lightweight structure. However, the key type of PlainArray can only be number.

You are advised to use PlainArray when you need to store KV pairs whose keys are of the number type.

PlainArray provides the following CRUD APIs.

Operation	Description
Adding elements	Use add(key: number,value: T) to add an element (a KV pair) to this container.
Accessing elements	Use get(key: number) to obtain the value of the specified key.
Accessing elements	Use getIndexOfKey(key: number) to obtain the index of the specified key.
Accessing elements	Use getIndexOfValue(value: T) to obtain the index of the specified value.
Accessing elements	Use getKeyAt(index: number) to obtain the key of an element at a given position (specified by index).
Accessing elements	Use getValueAt(index: number) to obtain the value of an element at a given position (specified by index).
Accessing elements	Use forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray<T>) => void, thisArg?: Object) to traverse the elements in this container.
Accessing elements	Use [Symbol.iterator]():IterableIterator<[number, T]> for data access.
Modifying elements	Use setValueAt(index:number, value: T) to change the value of an element at a given position (specified by index).
Modifying elements	Use forEach(callbackFn: (value: T, index?: number, PlainArray?: PlainArray<T>) => void, thisArg?: Object) to modify an element in this container.
Deleting elements	Use remove(key: number) to remove an element with the specified key.
Deleting elements	Use removeAt(index: number) to remove an element at a given position (specified by index).
Deleting elements	Use removeRangeFrom(index: number, size: number) to remove elements in a specified range.
Deleting elements	Use clear() to clear this container.

Use of Nonlinear Containers

Refer to the code snippet below to add, access, and modify elements in HashMap, TreeMap, LightWeightMap, Stack, and PlainArray.

// HashMap
import HashMap from '@ohos.util.HashMap'; // Import the HashMap module.

let hashMap1: HashMap<string, number> = new HashMap();
hashMap1.set('a', 123);
let hashMap2: HashMap<number, number> = new HashMap();
hashMap2.set(4, 123); // Add an element.
console.info(`result: ${hashMap2.hasKey(4)}`); // Check whether an element is contained.
console.info(`result: ${hashMap1.get('a')}`); // Access an element.

// TreeMap
import TreeMap from '@ohos.util.TreeMap'; // Import the TreeMap module.

let treeMap: TreeMap<string, number> = new TreeMap();
treeMap.set('a', 123);
treeMap.set('6', 356); // Add an element.
console.info(`result: ${treeMap.get('a')}`); // Access an element.
console.info(`result: ${treeMap.getFirstKey()}`); // Access the first element.
console.info(`result: ${treeMap.getLastKey()}`); // Access the last element.

// LightWeightMap
import LightWeightMap from '@ohos.util.LightWeightMap'; // Import the LightWeightMap module.

let lightWeightMap: LightWeightMap<string, number> = new LightWeightMap();
lightWeightMap.set('x', 123);
lightWeightMap.set('8', 356); // Add an element.
console.info(`result: ${lightWeightMap.get('a')}`); // Access an element.
console.info(`result: ${lightWeightMap.get('x')}`); // Access an element.
console.info(`result: ${lightWeightMap.getIndexOfKey('8')}`); // Access an element.

// PlainArray
import PlainArray from '@ohos.util.PlainArray' // Import the PlainArray module.

let plainArray: PlainArray<string> = new PlainArray();
plainArray.add(1, 'sdd');
plainArray.add(2,'sff'); // Add an element.
console.info(`result: ${plainArray.get(1)}`); // Access an element.
console.info(`result: ${plainArray.getKeyAt(1)}`); // Access an element.