集合(Set)

也叫做字典，键值对的匹配，两个元素的集之间元素相互“对应”的关系。

• 可以利用 Map 储存键，值只储存 null 实现。

常用映射

• HashMap
  • 底层使用哈希表
• ListMap
  • 底层使用链表
• TreeMap
  • 底层使用树形结构

核心代码

export interface Set<T> {
  size: number;
  empty: boolean;
  clear: () => void;
  contains: (val: T) => boolean;
  add: (val: T) => void;
  remove: (val: T) => void;
}

核心代码

import { TreeMap } from './treeMap';
import { Set } from './set';
export class TreeSet<T> implements Set<T> {
  private map = new TreeMap<T, null>((t1, t2) => this.compare(t1, t2));
  get size() {
    return this.map.size;
  }
  get empty() {
    return this.size === 0;
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  clear() {
    this.map.clear();
  }
  contains(val: T) {
    return this.map.contains(val);
  }
  add(val: T) {
    this.map.set(val, null);
  }
  remove(val: T) {
    this.map.remove(val);
  }
}

核心代码

import { HashMap } from './hashMap';
import { Set } from './set';
export class HashSet<T> implements Set<T> {
  private map = new HashMap<T, null>((t1, t2) => this.compare(t1, t2));
  get size() {
    return this.map.size;
  }
  get empty() {
    return this.size === 0;
  }
  constructor(private compare: (t1: T, t2: T) => number) {}
  clear() {
    this.map.clear();
  }
  contains(val: T) {
    return this.map.contains(val);
  }
  add(val: T) {
    this.map.set(val, null);
  }
  remove(val: T) {
    this.map.remove(val);
  }
}