Skip to content

Commit ac90a0f

Browse files
krahetskrahets
authored
Merge pull request krahets#136 from danielsss/typescript
Add the TypeScript code and docs for Chapter of Hash Map krahets#113
2 parents 18c4356 + f628fe2 commit ac90a0f

File tree

4 files changed

+297
-2
lines changed

4 files changed

+297
-2
lines changed

‎.gitignore

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,3 +13,6 @@ docs/overrides/
1313

1414
# python files
1515
__pycache__
16+
17+
# iml
18+
hello-algo.iml

‎codes/typescript/chapter_hashing/array_hash_map.ts

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
/*
2+
* File: array_hash_map.ts
3+
* Created Time: 2022-12-20
4+
* Author: Daniel (better.sunjian@gmail.com)
5+
*/
6+
7+
/* 键值对 Number -> String */
8+
class Entry {
9+
public key: number;
10+
public val: string;
11+
12+
constructor(key: number, val: string) {
13+
this.key = key;
14+
this.val = val;
15+
}
16+
}
17+
18+
/* 基于数组简易实现的哈希表 */
19+
class ArrayHashMap {
20+
21+
private readonly bucket: (Entry | null)[];
22+
23+
constructor() {
24+
// 初始化一个长度为 100 的桶（数组）
25+
this.bucket = (new Array(100)).fill(null);
26+
}
27+
28+
/* 哈希函数 */
29+
private hashFunc(key: number): number {
30+
return key % 100;
31+
}
32+
33+
/* 查询操作 */
34+
public get(key: number): string | null {
35+
let index = this.hashFunc(key);
36+
let entry = this.bucket[index];
37+
if (entry === null) return null;
38+
return entry.val;
39+
}
40+
41+
/* 添加操作 */
42+
public set(key: number, val: string) {
43+
let index = this.hashFunc(key);
44+
this.bucket[index] = new Entry(key, val);
45+
}
46+
47+
/* 删除操作 */
48+
public delete(key: number) {
49+
let index = this.hashFunc(key);
50+
// 置为 null ，代表删除
51+
this.bucket[index] = null;
52+
}
53+
54+
/* 获取所有键值对 */
55+
public entries(): (Entry | null)[] {
56+
let arr: (Entry | null)[] = [];
57+
for (let i = 0; i < this.bucket.length; i++) {
58+
if (this.bucket[i]) {
59+
arr.push(this.bucket[i]);
60+
}
61+
}
62+
return arr;
63+
}
64+
65+
/* 获取所有键 */
66+
public keys(): (number | undefined)[] {
67+
let arr: (number | undefined)[] = [];
68+
for (let i = 0; i < this.bucket.length; i++) {
69+
if (this.bucket[i]) {
70+
arr.push(this.bucket[i]?.key);
71+
}
72+
}
73+
return arr;
74+
}
75+
76+
/* 获取所有值 */
77+
public values(): (string | undefined)[] {
78+
let arr: (string | undefined)[] = [];
79+
for (let i = 0; i < this.bucket.length; i++) {
80+
if (this.bucket[i]) {
81+
arr.push(this.bucket[i]?.val);
82+
}
83+
}
84+
return arr;
85+
}
86+
87+
/* 打印哈希表 */
88+
public print() {
89+
let entrySet = this.entries();
90+
for (const entry of entrySet) {
91+
if (!entry) continue;
92+
console.info(`${entry.key} -> ${entry.val}`);
93+
}
94+
}
95+
}
96+
97+
/* Driver Code */
98+
/* 初始化哈希表 */
99+
const map = new ArrayHashMap();
100+
/* 添加操作 */
101+
// 在哈希表中添加键值对 (key, value)
102+
map.set(12836, '小哈');
103+
map.set(15937, '小啰');
104+
map.set(16750, '小算');
105+
map.set(13276, '小法');
106+
map.set(10583, '小鸭');
107+
console.info('\n添加完成后，哈希表为\nKey -> Value');
108+
map.print();
109+
110+
/* 查询操作 */
111+
// 向哈希表输入键 key ，得到值 value
112+
let name = map.get(15937);
113+
console.info('\n输入学号 15937 ，查询到姓名 ' + name);
114+
115+
/* 删除操作 */
116+
// 在哈希表中删除键值对 (key, value)
117+
map.delete(10583);
118+
console.info('\n删除 10583 后，哈希表为\nKey -> Value');
119+
map.print();
120+
121+
/* 遍历哈希表 */
122+
console.info('\n遍历键值对 Key->Value');
123+
for (const entry of map.entries()) {
124+
if (!entry) continue;
125+
console.info(entry.key + ' -> ' + entry.val);
126+
}
127+
console.info('\n单独遍历键 Key');
128+
for (const key of map.keys()) {
129+
console.info(key);
130+
}
131+
console.info('\n单独遍历值 Value');
132+
for (const val of map.values()) {
133+
console.info(val);
134+
}
135+
136+
export {};

‎codes/typescript/chapter_hashing/hash_map.ts

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
* File: hash_map.ts
3+
* Created Time: 2022-12-20
4+
* Author: Daniel (better.sunjian@gmail.com)
5+
*/
6+
7+
/* Driver Code */
8+
/* 初始化哈希表 */
9+
const map = new Map<number, string>();
10+
11+
/* 添加操作 */
12+
// 在哈希表中添加键值对 (key, value)
13+
map.set(12836, '小哈');
14+
map.set(15937, '小啰');
15+
map.set(16750, '小算');
16+
map.set(13276, '小法');
17+
map.set(10583, '小鸭');
18+
console.info('\n添加完成后，哈希表为\nKey -> Value');
19+
console.info(map);
20+
21+
/* 查询操作 */
22+
// 向哈希表输入键 key ，得到值 value
23+
let name = map.get(15937);
24+
console.info('\n输入学号 15937 ，查询到姓名 ' + name);
25+
26+
/* 删除操作 */
27+
// 在哈希表中删除键值对 (key, value)
28+
map.delete(10583);
29+
console.info('\n删除 10583 后，哈希表为\nKey -> Value');
30+
console.info(map);
31+
32+
/* 遍历哈希表 */
33+
console.info('\n遍历键值对 Key->Value');
34+
for (const [k, v] of map.entries()) {
35+
console.info(k + ' -> ' + v);
36+
}
37+
console.info('\n单独遍历键 Key');
38+
for (const k of map.keys()) {
39+
console.info(k);
40+
}
41+
console.info('\n单独遍历值 Value');
42+
for (const v of map.values()) {
43+
console.info(v);
44+
}

‎docs/chapter_hashing/hash_map.md

Lines changed: 114 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -138,7 +138,28 @@ comments: true
138138
=== "TypeScript"
139139

140140
```typescript title="hash_map.ts"
141+
/* 初始化哈希表 */
142+
const map = new Map<number, string>();
143+
/* 添加操作 */
144+
// 在哈希表中添加键值对 (key, value)
145+
map.set(12836, '小哈');
146+
map.set(15937, '小啰');
147+
map.set(16750, '小算');
148+
map.set(13276, '小法');
149+
map.set(10583, '小鸭');
150+
console.info('\n添加完成后，哈希表为\nKey -> Value');
151+
console.info(map);
141152

153+
/* 查询操作 */
154+
// 向哈希表输入键 key ，得到值 value
155+
let name = map.get(15937);
156+
console.info('\n输入学号 15937 ，查询到姓名 ' + name);
157+
158+
/* 删除操作 */
159+
// 在哈希表中删除键值对 (key, value)
160+
map.delete(10583);
161+
console.info('\n删除 10583 后，哈希表为\nKey -> Value');
162+
console.info(map);
142163
```
143164

144165
=== "C"
@@ -250,7 +271,19 @@ comments: true
250271
=== "TypeScript"
251272

252273
```typescript title="hash_map.ts"
253-
274+
/* 遍历哈希表 */
275+
console.info('\n遍历键值对 Key->Value');
276+
for (const [k, v] of map.entries()) {
277+
console.info(k + ' -> ' + v);
278+
}
279+
console.info('\n单独遍历键 Key');
280+
for (const k of map.keys()) {
281+
console.info(k);
282+
}
283+
console.info('\n单独遍历值 Value');
284+
for (const v of map.values()) {
285+
console.info(v);
286+
}
254287
```
255288

256289
=== "C"
@@ -506,7 +539,86 @@ $$
506539
=== "TypeScript"
507540

508541
```typescript title="array_hash_map.ts"
509-
542+
/* 键值对 Number -> String */
543+
class Entry {
544+
public key: number;
545+
public val: string;
546+
547+
constructor(key: number, val: string) {
548+
this.key = key;
549+
this.val = val;
550+
}
551+
}
552+
553+
/* 基于数组简易实现的哈希表 */
554+
class ArrayHashMap {
555+
556+
private readonly bucket: (Entry | null)[];
557+
558+
constructor() {
559+
// 初始化一个长度为 100 的桶（数组）
560+
this.bucket = (new Array(100)).fill(null);
561+
}
562+
563+
/* 哈希函数 */
564+
private hashFunc(key: number): number {
565+
return key % 100;
566+
}
567+
568+
/* 查询操作 */
569+
public get(key: number): string | null {
570+
let index = this.hashFunc(key);
571+
let entry = this.bucket[index];
572+
if (entry === null) return null;
573+
return entry.val;
574+
}
575+
576+
/* 添加操作 */
577+
public set(key: number, val: string) {
578+
let index = this.hashFunc(key);
579+
this.bucket[index] = new Entry(index, val);
580+
}
581+
582+
/* 删除操作 */
583+
public delete(key: number) {
584+
let index = this.hashFunc(key);
585+
// 置为 null ，代表删除
586+
this.bucket[index] = null;
587+
}
588+
589+
/* 获取所有键值对 */
590+
public entries(): (Entry | null)[] {
591+
let arr: (Entry | null)[] = [];
592+
for (let i = 0; i < this.bucket.length; i++) {
593+
if (this.bucket[i]) {
594+
arr.push(this.bucket[i]);
595+
}
596+
}
597+
return arr;
598+
}
599+
600+
/* 获取所有键 */
601+
public keys(): (number | undefined)[] {
602+
let arr: (number | undefined)[] = [];
603+
for (let i = 0; i < this.bucket.length; i++) {
604+
if (this.bucket[i]) {
605+
arr.push(this.bucket[i]?.key);
606+
}
607+
}
608+
return arr;
609+
}
610+
611+
/* 获取所有值 */
612+
public values(): (string | undefined)[] {
613+
let arr: (string | undefined)[] = [];
614+
for (let i = 0; i < this.bucket.length; i++) {
615+
if (this.bucket[i]) {
616+
arr.push(this.bucket[i]?.val);
617+
}
618+
}
619+
return arr;
620+
}
621+
}
510622
```
511623

512624
=== "C"

0 commit comments

Comments
 (0)