100
type HNode<V> = {
200
  key: number,
300
  value: V,
400
  next: HNode<V> | null
500
}
600

700
type Queue<V> = {
800
  length: number,
900
  last: HNode<V> | null
100
}
110

120
export default class HashMap<V> {
130
  private buckets: Queue<V>[];
140
  private size: number;
150

160
  constructor(size = 32) {
170
    this.buckets = new Array(size);
180
    this.size = size;
190
  }
200

210
  // 哈希函数
220
  hash(key: number) {
230
    return (key - 1000) % this.size;
240
  }
250

260
  // 插入键值对
270
  set(key: number, value: V) {
280
    const index = this.hash(key);
290
    const bucket = this.buckets[index]
300

310
    const node: HNode<V> = {
320
      key: key,
330
      value: value,
340
      next: null
350
    }
360
    
370
    // 如果桶是空的，初始化一个链表
380
    if (!bucket) {
390
      node.next = node
400
      this.buckets[index] = {
410
        length: 1,
420
        last: node
430
      };
440
      return
450
    }
460

470
    const last = bucket.last
480

490
    if (!last) {
500
      node.next = node
510
      bucket.last = node
520
      return
530
    }
540

550
    const first = last.next
560

570
    // 检查是否已存在相同的key
580
    let current = last
590
    while(true) {
600
      if (current.key === key) {
610
        current.value = value
620
        break
630
      }
640
      current = current.next!
650
      if (current === bucket.last) {
660
        break
670
      }
680
    }
690

700
    // add the node to last
710
    last.next = node
720
    node.next = first
730
    bucket.last = node
740
    bucket.length += 1
750
  }
760

770
  // 获取值
780
  get(key: number) {
790
    const index = this.hash(key);
800
    const bucket = this.buckets[index];
810
    
820
    if (!bucket) return undefined;
830

840
    if (!bucket.last) {
850
      return undefined
860
    }
870
    
880
    let current: HNode<V> = bucket.last
890
    while(true) {
900
      if (current.key === key) {
910
        return current.value
920
      }
930
      current = current.next as HNode<V>
940
      if (current === bucket.last) {
950
        break
960
      }
970
    }
980
    
990
    return undefined;
100
  }
101

102
  // 删除键值对
103
  delete(key: number) {
104
    const index = this.hash(key);
105
    const bucket = this.buckets[index];
106
    
107
    if (!bucket) return false;
108
    
109
    let prev = bucket.last
110
    let current = bucket.last
111

112
    if (current === null || prev === null) {
113
      return false
114
    }
115

116
    while(true) {
117
      if (current.key === key) {
118
        if (prev === current) {
119
          bucket.last = null
120
        } else {
121
          let next = current.next
122
          prev.next = next
123
        }
124
        return true
125
      }
126
      prev = current
127
      current = current.next as HNode<V>
128
      if (current === bucket.last) {
129
        break
130
      }
131
    }
132
    
133
    return false;
134
  }
135

136
  // 检查是否包含键
137
  has(key: number) {
138
    return this.get(key) !== undefined;
139
  }
140

141
  // 获取所有键
142
  keys() {
143
    const keys = [];
144
    for (const bucket of this.buckets) {
145
      if (bucket && bucket.last) {
146
        let current = bucket.last;
147
        do {
148
          keys.push(current.key);
149
          current = current.next!;
150
        } while (current !== bucket.last);
151
      }
152
    }
153
    return keys;
154
  }
155

156
  // 获取所有值
157
  values() {
158
    const values = [];
159
    for (const bucket of this.buckets) {
160
      if (bucket && bucket.last) {
161
        let current = bucket.last;
162
        do {
163
          values.push(current.value);
164
          current = current.next!;
165
        } while (current !== bucket.last);
166
      }
167
    }
168
    return values;
169
  }
170

171
  // 清空哈希表
172
  clear() {
173
    this.buckets = new Array(this.size);
174
  }
175
}
176