JavaScript의 데이터 구조[해시 테이블]
해시 테이블이란 무엇입니까?
해시 테이블, 해시, 맵, 정렬되지 않은 맵 또는 객체, 이 데이터 구조를 부르는 많은 이름이 있습니다.
JavaScript에서 객체는 해시 테이블의 한 유형입니다.
해시 테이블은 배열처럼 순서를 유지하지 않습니다.
왜 해시 테이블인가?
특정 앱의 활성 사용자 수를 저장하고 싶다고 상상해 보십시오.
배열에서 이 작업을 수행하는 것은 가장 깨끗한 방법이 아닙니다.
따라서 해시 테이블 또는 객체가 필요합니다.
const users = {
activeUsers: 1000,
};
해시 테이블은 어떻게 작동합니까?
해시 테이블에서는 키와 값을 사용합니다.
인덱스 대신 키를 사용하여 메모리에서 데이터를 찾습니다.
이를 위해서는 해시 함수가 필요합니다.
먼저 해시 함수에 키를 전달합니다.
그런 다음 해시 함수는 메모리에 데이터를 저장하기 위해 해시된 출력을 생성합니다.
해시 함수란 무엇입니까?
수학 방정식을 사용하여 모든 길이의 입력을 고정된 크기 문자열로 변환하는 함수입니다.
해시 함수의 출력은 고유해야 합니다.
그리고 동일한 입력은 항상 동일한 해시된 출력을 생성해야 합니다.
그리고 MD2, CRC23, SHA-1 등과 같은 많은 유형의 해시 함수가 있습니다.
당신은 그것을 시도 할 수 있습니다 here
간단한 해시 함수의 예
function hashFunction(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = hash + key.charCodeAt(i);
}
return hash;
}
// Giving it the string "Hello"
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500
// Giving it the string "hello"
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
Big O 표기법을 사용한 해시 테이블
- Access => O(1) || O(n).
- Insert => O(1).
- Delete => O(1).
Later in the article we will know why Accessing might be O(n).
예시
const user = {
firstName: "Youssef",
lastName: "Zidan",
};
// Access // O(1)
console.log(user.firstName); // "Youssef"
// Insert // O(1)
user.job = "Web Developer";
console.log(user.job); // "Web Developer"
// Delete O(1)
delete user.lastName;
console.log(user.lastName); // undefined
해시 테이블 구현
해시 테이블을 사용하여 Big O를 실제로 이해하기 위해 하나를 구현할 것입니다.
class HashTable {
constructor(size) {
this.data = new Array(size);
}
// hash function
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
// O(1)
set(key, value) {
let address = this._hash(key);
if (!this.data[address]) {
this.data[address] = []; // O(1)
this.data[address].push([key, value]); // O(1)
} else {
this.data[address].push([key, value]); // O(1)
}
}
// O(1) || O(n)
get(key) {
let address = this._hash(key); // O(1)
let current = this.data[address]; // O(1)
if (current) {
for (let i = 0; i < current.length; i++) {
// O(n)
// O(1) if current.length === 1
// or the ele is found in the first index
if (current[i][0] === key) {
return current[i][1];
}
}
} else {
// O(1)
return undefined;
}
}
keys() {
if (!this.data.length) {
return undefined;
}
const keys = [];
for (let i = 0; i < this.data.length; i++) {
if (this.data[i]) {
if (this.data[i].length === 1) {
keys.push(this.data[i][0][0]);
}
if (this.data[i].length > 1) {
for (let j = 0; j < this.data[i].length; j++) {
keys.push(this.data[i][j][0]);
}
}
}
}
return keys;
}
}
무너지다
해시 함수
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
이 특정 알고리즘을 사용하여 생성된 요소가 해시 테이블의 길이를 초과하지 않는지 확인합니다.
세트
set(key, value) {
let address = this._hash(key);
if (!this.data[address]) {
this.data[address] = []; // O(1)
this.data[address].push([key, value]); // O(1)
} else {
this.data[address].push([key, value]); // O(1)
}
}
this.data 개체에 없으면 이 주소의 빈 배열을 만듭니다. 가져 오기
get(key) {
let address = this._hash(key); // O(1)
let current = this.data[address]; // O(1)
if (current) {
for (let i = 0; i < current.length; i++) {
// O(n) or
// O(1) if current.length === 1
// or the ele is found in the first index
if (current[i][0] === key) {
return current[i][1];
}
}
} else {
// O(1)
return undefined;
}
}
current[i][0]를 확인하고 값current[i][1]을 반환합니다. 열쇠
keys() {
if (!this.data.length) {
return undefined;
}
const keys = [];
for (let i = 0; i < this.data.length; i++) {
if (this.data[i]) {
if (this.data[i].length === 1) {
keys.push(this.data[i][0][0]);
}
if (this.data[i].length > 1) {
for (let j = 0; j < this.data[i].length; j++) {
keys.push(this.data[i][j][0]);
}
}
}
}
return keys;
}
undefined를 반환합니다. this.data[i][0][0]가 될 키를 누를 것입니다.this.data[i][j][0] . 예시
const ht = new HashTable(10);
ht.set("a", 1);
ht.set("b", 2);
ht.set("c", 3);
ht.set("d", 4);
ht.set("e", 5);
ht.set("f", 6);
ht.set("g", 7);
ht.set("h", 8);
ht.set("i", 9);
ht.set("j", 10);
console.log(ht); /* 0: Array[10]
0: Array[2]
0: "a"
1: 1
1: Array[2]
2: Array[2]
3: Array[2]
4: Array[2]
5: Array[2]
6: Array[2]
7: Array[2]
8: Array[2]
9: Array[2]
1: undefined
2: undefined
3: undefined
4: undefined
5: undefined
6: undefined
7: undefined
8: undefined
9: undefined
*/
console.log(ht.get("g")); // 7
console.log(ht.keys()); // ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
Reference
이 문제에 관하여(JavaScript의 데이터 구조[해시 테이블]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/youssefzidan/data-structures-in-javascript-hash-tables-258n텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
