HarmonyOS开发中线性容器与非线性容器怎么选

ArkTS 提供了一套容器类库，包括 ArrayList、HashMap、LinkedList 这些。有人会问：JS 原生的 Array、Map、Set 不能用吗？能用，但 ArkTS 容器在性能上做了专门优化，运行时通过一条字节码指令就能完成增删改查，比原生 Array 的方法调用快。这篇把线性容器和非线性容器捋一遍，重点讲怎么按场景选容器。

为什么不用原生 Array/Map/Set

原生 Array、Map、Set 在 ArkTS 里能用，但有两个问题：

性能：原生 Array 的 push、pop 等方法是函数调用，有调用开销。ArkTS 容器的操作被编译成单条字节码指令，没有方法调用开销。

类型安全：原生 Array 是动态类型，可以往里塞任何东西。ArkTS 容器基于泛型定义，类型在编译期就确定，配合 ArkTS 的类型系统能更早发现类型错误。

容器类库从 @kit.ArkTS 导入：

import { ArrayList, HashMap, LinkedList } from '@kit.ArkTS';

线性容器

线性容器实现按顺序访问的数据结构，底层主要用数组实现。包括 ArrayList、Vector、List、LinkedList、Deque、Queue、Stack。

各线性容器对比

类名	底层结构	初始容量	扩容	适用场景
ArrayList	动态数组	10	1.5 倍	频繁读取元素
Vector	动态数组	10	2 倍	已废弃，用 ArrayList
List	单向链表	-	-	频繁增删，单向遍历
LinkedList	双向链表	-	-	频繁增删，双向操作
Deque	循环队列	8	2 倍	频繁头尾增删
Queue	循环队列	8	2 倍	先进先出
Stack	数组	8	1.5 倍	先进后出

Vector 已经不再维护，新代码用 ArrayList 替代。

ArrayList

最常用的线性容器。动态数组，连续内存，初始容量 10，每次扩容 1.5 倍。

import { ArrayList } from '@kit.ArkTS';

let list: ArrayList<string> = new ArrayList();
list.add('a');                    // 尾部添加
list.add('b');
list.insert('x', 0);              // 指定位置插入
console.info(`${list[0]}`);       // 索引访问，输出 x
console.info(`${list.length}`);   // 输出 3

list.forEach((value, index) => {
  console.info(`${index}: ${value}`);
});

list.remove('a');                 // 删除第一个匹配
list.removeByRange(0, 1);         // 删除范围

ArrayList 的优势在随机访问——list[index] 一条指令搞定。频繁读取元素选 ArrayList。

List 和 LinkedList

List 是单向链表，LinkedList 是双向链表。链表的优势在插入删除——不需要移动元素，改指针就行。但随机访问慢，要从头遍历。

import { LinkedList } from '@kit.ArkTS';

let list: LinkedList<number> = new LinkedList();
list.add(1);
list.add(2);
list.add(3);

// 头尾快速访问
console.info(`${list.getFirst()}`);  // 1
console.info(`${list.getLast()}`);   // 3

// 中间插入比 ArrayList 快
list.insert(99, 1);  // 在位置 1 插入

选型要点：

• 频繁读取 → ArrayList
• 频繁中间插入删除 → LinkedList
• 需要双向遍历 → LinkedList（List 是单向的）

Deque、Queue、Stack

这三个是特殊场景的容器。

Queue：先进先出，尾部 add，头部 pop。

import { Queue } from '@kit.ArkTS';

let queue: Queue<string> = new Queue();
queue.add('task1');
queue.add('task2');
console.info(`${queue.getFirst()}`);  // task1，不出队
console.info(`${queue.pop()}`);       // task1，出队

Stack：先进后出，push 入栈，pop 出栈。

import { Stack } from '@kit.ArkTS';

let stack: Stack<number> = new Stack();
stack.push(1);
stack.push(2);
console.info(`${stack.peek()}`);   // 2，看出栈顶不出栈
console.info(`${stack.pop()}`);    // 2，出栈

Deque：双端队列，两头都能增删。

import { Deque } from '@kit.ArkTS';

let deque: Deque<string> = new Deque();
deque.insertFront('a');    // 头部插入
deque.insertEnd('b');      // 尾部插入
console.info(`${deque.getFirst()}`);  // a
console.info(`${deque.getLast()}`);   // b
deque.popFirst();          // 头部出队
deque.popLast();           // 尾部出队

选型要点：

• 先进先出 → Queue
• 先进后出 → Stack
• 两头都要增删 → Deque

非线性容器

非线性容器实现快速查找的数据结构，底层用 hash 或红黑树实现。包括 HashMap、HashSet、TreeMap、TreeSet、LightWeightMap、LightWeightSet、PlainArray。

各非线性容器对比

类名	底层结构	初始容量	是否有序	适用场景
HashMap	哈希表	16	否	快速存取键值对
HashSet	哈希表	16	否	去重、不重复集合
TreeMap	红黑树	-	是	有序键值对
TreeSet	红黑树	-	是	有序不重复集合
LightWeightMap	轻量 hash	8	否	内存敏感的键值对
LightWeightSet	轻量 hash	8	否	内存敏感的去重
PlainArray	轻量结构	16	否	number 键的键值对

HashMap

最常用的键值对容器。哈希表实现，初始容量 16，扩容 2 倍，冲突用链地址法处理。

import { HashMap } from '@kit.ArkTS';

let map: HashMap<string, number> = new HashMap();
map.set('a', 123);
map.set('b', 456);

console.info(`${map.get('a')}`);     // 123
console.info(`${map.hasKey('a')}`);  // true

// 遍历
map.forEach((value, key) => {
  console.info(`${key}: ${value}`);
});

// 迭代器
for (let entry of map) {
  console.info(`${entry[0]}: ${entry[1]}`);
}

map.remove('a');

HashMap 访问速度快，但不能自定义排序。需要有序用 TreeMap。

TreeMap

红黑树实现，key 有序存储。

import { TreeMap } from '@kit.ArkTS';

let map: TreeMap<string, number> = new TreeMap();
map.set('banana', 1);
map.set('apple', 2);
map.set('cherry', 3);

console.info(`${map.getFirstKey()}`);  // apple
console.info(`${map.getLastKey()}`);   // cherry

// 遍历是按 key 排序的
map.forEach((value, key) => {
  console.info(`${key}: ${value}`);  // apple, banana, cherry
});

TreeMap 比 HashMap 慢一些（红黑树查找比哈希表慢），但有序。需要按顺序遍历键值对时用 TreeMap。

HashSet 和 TreeSet

Set 容器存不重复的值。HashSet 无序，TreeSet 有序。

import { HashSet } from '@kit.ArkTS';

let set: HashSet<number> = new HashSet();
set.add(1);
set.add(2);
set.add(1);  // 重复，不会添加
console.info(`${set.length}`);  // 2

去重场景用 HashSet。需要有序去重用 TreeSet。

LightWeightMap 和 LightWeightSet

轻量级版本，占用内存更小。底层用 hash + 二分查找，冲突用线性探测。

import { LightWeightMap } from '@kit.ArkTS';

let map: LightWeightMap<string, number> = new LightWeightMap();
map.set('x', 123);
map.set('y', 456);
console.info(`${map.get('x')}`);  // 123

内存敏感场景（比如嵌入式设备、大量小集合）用 LightWeightMap。性能比 HashMap 稍慢，但内存占用小。

PlainArray

PlainArray 是 LightWeightMap 的特化版本，key 固定为 number 类型。

import { PlainArray } from '@kit.ArkTS';

let arr: PlainArray<string> = new PlainArray();
arr.add(1, 'one');
arr.add(2, 'two');
console.info(`${arr.get(1)}`);  // one
console.info(`${arr.getKeyAt(0)}`);  // 1

key 是 number 的键值对场景用 PlainArray，比 HashMap<number, T> 更省内存。

容器选型指南

按场景选容器，别按"我熟悉哪个"选。

线性容器的选型：

场景	选什么
频繁随机读取	ArrayList
频繁中间插入删除	LinkedList
先进先出	Queue
先进后出	Stack
两头增删	Deque
单向链表遍历	List

性能对比

同样是存 10000 个元素然后查找，不同容器表现差异明显：

操作	ArrayList	LinkedList	HashMap	TreeMap
尾部添加	快	快	-	-
头部添加	慢（要移动元素）	快	-	-
中间插入	慢（要移动元素）	快	-	-
随机访问	快（索引）	慢（要遍历）	-	-
按 key 查找	慢（要遍历）	慢（要遍历）	快	中等
遍历	快	快	快	快

具体数字取决于数据量和操作比例，但相对关系基本是这样。

案例：消息队列实现

用一个具体场景把容器选型串起来。需求：实现一个消息处理系统，消息有优先级，同优先级按时间顺序处理。

import { HashMap, ArrayList, Queue } from '@kit.ArkTS';

interface Message {
  id: number;
  priority: number;
  content: string;
}

class MessageQueue {
  // 按优先级分桶，每个优先级一个 Queue（先进先出）
  private queues: HashMap<number, Queue<Message>> = new HashMap();
  // 所有消息 id 索引，快速判重
  private ids: HashSet<number> = new HashSet();
  
  add(msg: Message): boolean {
    // 去重检查
    if (this.ids.hasKey(msg.id)) {
      return false;
    }
    this.ids.add(msg.id);
    
    // 按优先级入队
    let queue = this.queues.get(msg.priority);
    if (!queue) {
      queue = new Queue();
      this.queues.set(msg.priority, queue);
    }
    queue.add(msg);
    return true;
  }
  
  // 取出最高优先级的消息
  poll(): Message | undefined {
    // 找最高优先级（这里简化，实际可以用 TreeMap 维护优先级）
    let maxPriority = -1;
    this.queues.forEach((queue, priority) => {
      if (priority > maxPriority && queue.length > 0) {
        maxPriority = priority;
      }
    });
    
    if (maxPriority === -1) {
      return undefined;
    }
    
    let queue = this.queues.get(maxPriority);
    let msg = queue!.pop();
    this.ids.remove(msg!.id);
    return msg;
  }
}

这里用 HashMap 存优先级到队列的映射（快速查找），用 Queue 实现同优先级的先进先出，用 HashSet 做消息去重。如果优先级范围固定且小，可以用 ArrayList 按优先级索引；如果需要按优先级有序遍历，用 TreeMap 更合适。

小区别

索引访问的边界：list[index] 超出范围返回 undefined，不会报错。但 list.get(index) 超出范围会报 out of range。根据需要选访问方式。

List 的 list[index] = value 有坑：对 List 用索引赋值不会真的修改链表节点，只在对象上加个属性，可能导致状态不一致。修改 List 元素用 set(index, value)。

remove 用 === 比较：list.remove(element) 用严格相等比较。对对象类型，只有传入同一个引用才能删掉，传入值相等的另一个对象删不掉。

HashMap 的 key 类型：key 类型要满足 ECMA 标准。自定义对象做 key 要小心，默认按引用判等。

容量预分配：如果知道大概要存多少元素，构造时可以预分配容量，减少扩容次数。不过 ArkTS 容器的构造函数目前没有直接暴露容量参数，扩容是自动的。

迭代时修改：forEach 或 for-of 遍历时修改容器（增删元素）行为未定义，可能漏元素或重复。要修改就先收集要改的，遍历完再改。

几条经验看看

1. 默认选 ArrayList 和 HashMap：大多数场景这两个就够了。有特殊需求（频繁中间增删、有序、内存敏感）再换。
2. 别用 Vector：已废弃，用 ArrayList。老代码迁移时顺手换掉。
3. 键值对 key 是 number 时考虑 PlainArray：比 HashMap<number, T> 省内存，API 也更直接。
4. 去重用 HashSet：别用 Array + indexOf 判重，性能差很多。
5. 需要有序遍历用 TreeMap/TreeSet：HashMap 的遍历顺序不保证，依赖顺序会出 bug。