Dia 53/2019 - Estruturas de dados em JS: mapas e tabelas de hash

Desafio #92daysofcode que fiz no final de 2019. Nesse artigo temos o dia 53, mostrando o uso de mapas e tabelas de hash.

Código

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class ValuePair {
constructor(key, value) {
this.key = key;
this.value = value;
}

toString() {
return `[#${this.key}: ${this.value}]`;
}
}

class ValuePairLazy extends ValuePair {
constructor(key, value, isDeleted = false) {
super(key, value);
this.key = key;
this.value = value;
this.isDeleted = isDeleted;
}
}

const defaultToString = item => {
if (item === null) {
return 'NULL';
} if (item === undefined) {
return 'UNDEFINED';
} if (typeof item === 'string' || item instanceof String) {
return `${item}`;
}
return item.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Map {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}

set(key, value) {
if (key != null && value != null) {
const tableKey = this.toStrFn(key);
this.table[tableKey] = new ValuePair(key, value);
return true;
}
return false;
}

get(key) {
const valuePair = this.table[this.toStrFn(key)];
return valuePair == null ? undefined : valuePair.value;
}

hasKey(key) {
return this.table[this.toStrFn(key)] != null;
}

remove(key) {
if (this.hasKey(key)) {
delete this.table[this.toStrFn(key)];
return true;
}
return false;
}

values() {
return this.keyValues().map(valuePair => valuePair.value);
}

keys() {
return this.keyValues().map(valuePair => valuePair.key);
}

keyValues() {
return Object.values(this.table);
}

forEach(callbackFn) {
const valuePairs = this.keyValues();
for (let i = 0; i < valuePairs.length; i++) {
const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
if (result === false) {
break;
}
}
}

isEmpty() {
return this.size() === 0;
}

size() {
return Object.keys(this.table).length;
}

clear() {
this.table = {};
}

toString() {
if (this.isEmpty()) {
return '';
}
const valuePairs = this.keyValues();
let objString = `${valuePairs[0].toString()}`;
for (let i = 1; i < valuePairs.length; i++) {
objString = `${objString},${valuePairs[i].toString()}`;
}
return objString;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class HashTable {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}

hashCode(key) {
if (typeof key === 'number') {
return key;
}
const tableKey = this.toStrFn(key);
const max = tableKey.length * 2;
let hash = 0;

if (!tableKey.length) return hash;
for (let i = 0; i < tableKey.length; i++) {
hash += hash + tableKey.charCodeAt(i);
}
return hash % max;
}

put(key, value) {
if (key != null && value != null) {
const position = this.hashCode(key);
this.table[position] = new ValuePair(key, value);
return true;
}
return false;
}

get(key) {
const valuePair = this.table[this.hashCode(key)];
return valuePair == null ? undefined : valuePair.value;
}

remove(key) {
const hash = this.hashCode(key);
const valuePair = this.table[hash];
if (valuePair != null) {
delete this.table[hash];
return true;
}
return false;
}

getTable() {
return this.table;
}

isEmpty() {
return this.size() === 0;
}

size() {
return Object.keys(this.table).length;
}

clear() {
this.table = {};
}

toString() {
if (this.isEmpty()) {
return '';
}
const keys = Object.keys(this.table);
let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
for (let i = 1; i < keys.length; i++) {
objString = `${objString},{${keys[i]} => ${this.table[keys[i]].toString()}}`;
}
return objString;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class LinkedList {
constructor(equalsFn = defaultEquals) {
this.equalsFn = equalsFn;
this.count = 0;
this.head = undefined;
}

push(element) {
const node = new Node(element);
let current;
if (this.head == null) {
// catches null && undefined
this.head = node;
} else {
current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = node;
}
this.count++;
}

getElementAt(index) {
if (index >= 0 && index <= this.count) {
let node = this.head;
for (let i = 0; i < index && node != null; i++) {
node = node.next;
}
return node;
}
return undefined;
}

insert(element, index) {
if (index >= 0 && index <= this.count) {
const node = new Node(element);
if (index === 0) {
const current = this.head;
node.next = current;
this.head = node;
} else {
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count++;
return true;
}
return false;
}

removeAt(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
if (index === 0) {
this.head = current.next;
} else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}

remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}

indexOf(element) {
let current = this.head;
for (let i = 0; i < this.size() && current != null; i++) {
if (this.equalsFn(element, current.element)) {
return i;
}
current = current.next;
}
return -1;
}

isEmpty() {
return this.size() === 0;
}

size() {
return this.count;
}

getHead() {
return this.head;
}

clear() {
this.head = undefined;
this.count = 0;
}

toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
for (let i = 1; i < this.size() && current != null; i++) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class HashTableSeparateChaining {
constructor(toStrFn = defaultToString) {
this.toStrFn = toStrFn;
this.table = {};
}

loseloseHashCode(key) {
if (typeof key === 'number') {
return key;
}
const tableKey = this.toStrFn(key);
let hash = 0;
for (let i = 0; i < tableKey.length; i++) {
hash += tableKey.charCodeAt(i);
}
return hash % 37;
}

hashCode(key) {
return this.loseloseHashCode(key);
}

put(key, value) {
if (key != null && value != null) {
const position = this.hashCode(key);
if (this.table[position] == null) {
this.table[position] = new LinkedList();
}
this.table[position].push(new ValuePair(key, value));
return true;
}
return false;
}

get(key) {
const position = this.hashCode(key);
const linkedList = this.table[position];
if (linkedList != null && !linkedList.isEmpty()) {
let current = linkedList.getHead();
while (current != null) {
if (current.element.key === key) {
return current.element.value;
}
current = current.next;
}
}
return undefined;
}

remove(key) {
const position = this.hashCode(key);
const linkedList = this.table[position];
if (linkedList != null && !linkedList.isEmpty()) {
let current = linkedList.getHead();
while (current != null) {
if (current.element.key === key) {
linkedList.remove(current.element);
if (linkedList.isEmpty()) {
delete this.table[position];
}
return true;
}
current = current.next;
}
}
return false;
}

isEmpty() {
return this.size() === 0;
}

size() {
let count = 0;
Object.values(this.table).forEach(linkedList => {
count += linkedList.size();
});
return count;
}

clear() {
this.table = {};
}

getTable() {
return this.table;
}

toString() {
if (this.isEmpty()) {
return '';
}
const keys = Object.keys(this.table);
let objString = `{${keys[0]} => ${this.table[keys[0]].toString()}}`;
for (let i = 1; i < keys.length; i++) {
objString = `${objString},{${keys[i]} => ${this.table[
keys[i]
].toString()}}`;
}
return objString;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
* Map
***********************************/
const map = new Map();

map.set('Hemerson', 'hemerson@gmail.com');
map.set('Nerd', 'nerd@gmail.com');
map.set('Calistênico', 'calistenico@gmail.com');

console.log(map.hasKey('Nerd'));
// true
console.log(map.size());
// 3

console.log(map.keys());
// ["Hemerson", "Nerd", "Calistênico"]
console.log(map.values());
// ["hemerson@gmail.com", "nerd@gmail.com", "calistenico@gmail.com"]
console.log(map.get('Calistênico'));
// calistenico@gmail.com

map.remove('Nerd');

console.log(map.keys());
// ["Hemerson", "Calistênico"]
console.log(map.values());
// ["hemerson@gmail.com", "calistenico@gmail.com"]

console.log(map.keyValues());
// [{key: "Hemerson", value: "hemerson@gmail.com"}, {key: "Calistênico", value: "calistenico@gmail.com"}]
console.log(map.toString());
// [#Hemerson: hemerson@gmail.com],[#Calistênico: calistenico@gmail.com]

map.forEach((k, v) => console.log(`key: ${k}, value: ${v}`));
// key: Hemerson, value: hemerson@gmail.com
// key: Calistênico, value: calistenico@gmail.com

/*
* Hash Table
***********************************/
const hashTable = new HashTable();

console.log(`${hashTable.hashCode('Hemerson')} - Hemerson`);
// 8 - Hemerson
console.log(`${hashTable.hashCode('Nerd')} - Nerd`);
// 4 - Nerd
console.log(`${hashTable.hashCode('Calistênico')} - Calistênico`);
// 5 - Calistênico
console.log(`${hashTable.hashCode('Unknown')} - Unknown`);
// 10 - Unknown
console.log(`${hashTable.hashCode('Developer')} - Developer`);
// 4 - Developer

hashTable.put('Hemerson', 'hemerson@gmail.com');
hashTable.put('Nerd', 'nerd@gmail.com');
hashTable.put('Calistênico', 'calistenico@gmail.com');
hashTable.put('Unknown', 'unknown@gmail.com');
hashTable.put('Developer', 'developer@gmail.com');

console.log(hashTable.toString());
// {4 => [#Developer: developer@gmail.com]},{5 => [#Calistênico: calistenico@gmail.com]},{8 => [#Hemerson: hemerson@gmail.com]},{10 => [#Unknown: unknown@gmail.com]}

console.log(hashTable.get('Calistênico'));
// calistenico@gmail.com

hashTable.remove('Calistênico');

console.log(hashTable.get('Calistênico'));
// undefined
console.log(hashTable.get('Developer'));
// developer@gmail.com

console.log(hashTable.toString());
// {4 => [#Developer: developer@gmail.com]},{8 => [#Hemerson: hemerson@gmail.com]},{10 => [#Unknown: unknown@gmail.com]}

Conclusão

A postagem original pode ser vista no meu Instagram e o código está acessível no meu Github.

Relacionados

Ao fechar este aviso ou continuar navegando no site Nerd Calistênico, você aceita o uso de cookies.

Este site usa cookies para assegurar a melhor experiência para os nossos usuários. Consulte nossa política de privacidade.

Uma nova versão está disponível. Clique aqui para atualizar.