Nonlinear Containers

Nonlinear containers, underpinned by hash tables or red-black trees, implement a data structure that enables quick lookup operations. There are several types of nonlinear containers: HashMap, HashSet, TreeMap, TreeSet, LightWeightMap, LightWeightSet, and PlainArray. The types of key and value in nonlinear containers comply with the ECMA standard.

Comparison of Nonlinear Container Types

HashMap

HashMap is used to store a collection of KV pairs with unique keys. Each key corresponds to a value.

Defined by generics, HashMap uses the hash code of the key to determine the storage location, enabling quick access to KV pairs. The initial capacity is 16, and it supports dynamic resizing, doubling its size each time. HashMap is implemented using a hash table with a chain address conflict resolution strategy.

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. HashMap takes key and value as input parameters. 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.

Common APIs for adding, removing, modifying, and accessing elements in HashMap are as follows:

HashSet

HashSet is used to store a collection of unique values.

Defined by generics, HashSet uses the hash code of the value to determine the storage location, enabling quick access to the value. The initial capacity is 16, and it supports dynamic resizing, doubling its size each time. The type of value must comply with the ECMA standard. HashSet is implemented based on HashMap and processes only the value object. The underlying data structure is consistent with HashMap.

Compared with TreeSet, which stores data in an ordered manner and allows users to define sorting functions, HashSet stores data in an unordered manner and does not support custom sorting. Neither allows duplicate elements, but HashSet permits null values, whereas TreeSet does not recommend storing null values as it may affect sorting results.

You are advised to use HashSet when you need to create non-redundant collections or remove duplicates.

Common APIs for adding, removing, modifying, and accessing elements in HashSet are as follows:

TreeMap

TreeMap is used to store a collection of KV pairs with unique keys. Each key corresponds to a value.

Defined by generics, TreeMap stores keys in an ordered manner. The underlying structure is a binary tree, allowing for quick lookup of KV pairs through binary tree search. The type of key must comply with the ECMA standard. Keys in a TreeMap are stored in order. TreeMap is implemented using a red-black tree, enabling fast insertion and removal.

Compared with HashMap, which provides faster access based on the key’s hash code, TreeMap is ordered and thus less efficient.

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

Common APIs for adding, removing, modifying, and accessing elements in TreeMap are as follows:

TreeSet

TreeSet is used to store a collection of unique values.

Defined by generics, TreeSet stores values in an ordered manner. The underlying structure is a binary tree, allowing for quick lookup of values through binary tree search. The type of value must comply with the ECMA standard. Values in a TreeSet are stored in order. TreeSet is implemented using a red-black tree, enabling fast insertion and removal.

TreeSet is based on TreeMap and processes only the value object. It allows for ordered storage of a collection of values and can be sorted according to a custom sorting function.

Compared with HashSet, which stores data in an unordered manner, TreeSet stores data in an ordered manner. Neither allows duplicate elements, but HashSet permits null values, whereas TreeSet does not recommend storing null values as it may affect sorting results.

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

Common APIs for adding, removing, modifying, and accessing elements in TreeSet are as follows:

LightWeightMap

LightWeightMap is used to store a collection of KV pairs with unique keys. Each key corresponds to a value. Defined by generics, LightWeightMap uses a more lightweight structure. The underlying structure uses hash codes to identify unique keys, with a conflict resolution strategy of linear probing. The lookup of keys relies on hash codes and binary search algorithms, storing hash codes in an array and mapping them to key and value values in other arrays. The type of key must comply with the ECMA standard.

The default initial capacity is 8, and it supports dynamic resizing, doubling its size each time.

LightWeightMap and HashMap are both used to store KV pairs, but LightWeightMap occupies less memory.

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

Common APIs for adding, removing, modifying, and accessing elements in LightWeightMap are as follows:

LightWeightSet

LightWeightSet is used to store a collection of unique values.

Defined by generics, LightWeightSet uses a more lightweight structure. The default initial capacity is 8, and it supports dynamic resizing, doubling its size each time. The lookup of values relies on hash codes and binary search algorithms, storing hash codes in an array and mapping them to values in other arrays. The type of value must comply with the ECMA standard.

LightWeightSet identifies unique values based on hash at the underlying layer, with a conflict resolution strategy of linear probing and a lookup strategy based on binary search.

LightWeightSet and HashSet are both used to store unique values, but LightWeightSet occupies less memory.

You are advised to use LightWeightSet when you need a collection that contains unique elements or need to deduplicate a collection with limited memory.

Common APIs for adding, removing, modifying, and accessing elements in LightWeightSet are as follows:

PlainArray

PlainArray is used to store a collection of KV pairs with unique keys, where keys are of the number type. Each key corresponds to a value. Defined by generics, PlainArray uses a more lightweight structure, with key lookup relying on binary search algorithms and mapping to value values in other arrays.

The default initial capacity is 16, and it supports dynamic resizing, doubling its size each time.

PlainArray and LightWeightMap are both used to store KV pairs with a lightweight structure, but PlainArray’s keys can only be of the number type.

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

Common APIs for adding, removing, modifying, and accessing elements in PlainArray are as follows:

Use of Nonlinear Containers

Here are usage examples for common nonlinear containers, including HashMap, TreeMap, LightWeightMap, and PlainArray, covering importing modules, adding elements, accessing elements, and modifying elements. The example code is as follows:

// HashMap
import { HashMap } from '@kit.ArkTS'; // Import the HashMap module.

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

// TreeMap
import { TreeMap } from '@kit.ArkTS'; // Import the TreeMap module.

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

// LightWeightMap
import { LightWeightMap } from '@kit.ArkTS'; // Import the LightWeightMap module.

let lightWeightMap: LightWeightMap<string, number> = new LightWeightMap();
lightWeightMap.set('x', 123); // Add an element with key 'x' and value 123.
lightWeightMap.set('8', 356); // Add an element with key '8' and value 356.
console.info(`result: ${lightWeightMap.get('a')}`); // Access an element with key 'a'. Output: result: undefined
console.info(`result: ${lightWeightMap.get('x')}`); // Obtain the value of the element with key 'x'. Output: result: 123
console.info(`result: ${lightWeightMap.getIndexOfKey('8')}`); // Obtain the index of the element with key '8'. Output: result: 0

// PlainArray
import { PlainArray } from '@kit.ArkTS'; // Import the PlainArray module.

let plainArray: PlainArray<string> = new PlainArray();
plainArray.add(1, 'sdd'); // Add an element with key 1 and value 'sdd'.
plainArray.add(2, 'sff'); // Add an element with key 2 and value 'sff'.
console.info(`result: ${plainArray.get(1)}`); // Obtain the value of the element with key 1. Output: result: sdd
console.info(`result: ${plainArray.getKeyAt(1)}`); // Obtain the key of the element at index 1. Output: result: 2

你可能感兴趣的鸿蒙文章

harmony 鸿蒙ArkTS

harmony 鸿蒙Configuring arkOptions in build-profile.json5

harmony 鸿蒙Asynchronous Lock

harmony 鸿蒙Ark Bytecode File Format

harmony 鸿蒙Naming Conventions for Ark Bytecode Functions

harmony 鸿蒙Ark Bytecode Fundamentals

harmony 鸿蒙Overview of Ark Bytecode

harmony 鸿蒙Shared Container

harmony 鸿蒙Asynchronous Waiting

harmony 鸿蒙ArkTS Cross-Language Interaction