마지막 몇 편의 글에서 저는 Udemy에서 자바스크립트 데이터 구조와 알고리즘 과정을 배울 때 배운 지식을 개술했습니다.동시에 나는 my Chrome Extension project의 시간 복잡도를 높이기 위해 더 좋은 구조를 찾고 있다.
현재 나는 주요 데이터를 대상으로 다음과 같은 그룹에 저장하고 있다.

// Result of console.log(MainData)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}

나는 모든 데이터를 효율적으로 삭제/편집하는 기능을 실현하고 싶지만, 이러한 상황에서 이 두 기능은 모두 O(n)의 시간 복잡도를 필요로 한다.
내가 2진 더미 뒤에서 배운 것은 해시표였다.본문에서 나는 그것이 적합한지 아닌지를 고려할 것이다.

무엇이 해시시계입니까?

해시표(해시영사라고도 부른다)는 해시를 바탕으로 한 구조이다.그것은 수조와 유사해 보이지만, 색인을 값에 비추지만, 해시 테이블에 대해서는 색인이 아니라 키를 사용합니다.

수조와 마찬가지로, 해시표는 많은 컴퓨터 언어의 내장 데이터 구조이다.JavaScript에서 객체 및 맵은 매우 효과적인 해시 테이블 구조를 제공합니다.
예를 들어 모든 데이터에 이름과 같은 유일한 값이 있으면 키를 사용할 수 있다.이러한 기능은 우리로 하여금 하나의 항목에 매우 신속하게 접근할 수 있게 한다.
만약 그것이 규칙적인 수조라면, 우리는 모든 항목을 두루 훑어보아서 하나의 항목을 찾아야 한다.따라서 시간 복잡도는 O(n)입니다.

let StudentResidence = [];

class Student {
    constructor(name, age, grade, licenceEnds) {
        this.name        = name;
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence.push(new Student('Tara Joyce', 18, 'A', '11-06-2021'))
StudentResidence.push(new Student('Brian Brown', 19, 'A', '05-06-2020'))
StudentResidence.push(new Student('John Smith', 18, 'B', '07-06-2021'))

// To change Tara's age, we need to look up each item
for (let i=0; i<StudentResidence.length; i++) {
    if(StudentResidence[i].name === 'Tara Joyce') {
        StudentResidence[i].age = 19;
    }
}

그러나 키 값 쌍에 저장되면 데이터에서 순환할 필요가 없습니다.

let StudentResidence = {};

class Student {
    constructor(age, grade, licenceEnds) {
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence['Tara Joyce']  = new Student(18, 'A', '11-06-2021');
StudentResidence['Brian Brown'] = new Student(19, 'A', '05-06-2020');
StudentResidence['John Smith']  = new Student(18, 'B', '07-06-2021');

// To change Tara's age, no need to look up each item
StudentResidence['Tara Joyce'].age = 19;

우리도 맵으로 그것을 실현할 수 있다.

let StudentResidence = new Map();

class Student {
    constructor(age, grade, licenceEnds) {
        this.age         = age;
        this.grade       = grade;
        this.licenceEnds = licenceEnds;
    }
}

StudentResidence.set('Tara Joyce', new Student(18, 'A', '11-06-2021'));
StudentResidence.set('Brian Brown', new Student(19, 'A', '05-06-2020'));
StudentResidence.set('John Smith', new Student(18, 'B', '07-06-2021'));

// To change Tara's age, no need to look up each item
StudentResidence.get('Tara Joyce').age = 19

이것들은 O(1)만 취합니다. 이것은 고정된 시간입니다.

왜 이렇게 빨라?

막후에서 일어난 일은 해시 테이블이 해시 함수를 사용하여 키에서 인덱스를 계산하는 것이다. 이 인덱스는 값을 어느 저장 통수 그룹에 저장해야 하는지 알려준다.따라서 값이 저장된 위치를 찾으려면 해시 함수로 인덱스를 계산하고 필요한 값이 저장된 위치를 찾을 수 있습니다.

이상적인 상황에서 해시 함수는 모든 키를 유일한 버킷에 분배하지만, 우리는 해시 함수가 여러 개의 키를 위해 같은 색인을 생성하는 상황을 고려해야 한다.

충돌 처리

많은 전략들이 충돌을 처리할 수 있지만, 우리는 여기서 두 가지 흔히 볼 수 있는 전략을 연구할 것이다.

메서드 1: 개별 링크

단독 링크를 통해 우리는 그것들을 같은 메모리 통에 저장하고 그 안에 다른 목록을 끼워 넣는다.체인 테이블이나 그룹을 사용하면 검색 시간은 메모리 통당 평균 키 수에 따라 달라집니다.

방법 2: 선형 탐지

선형 탐지는 개방 주소 찾기 정책으로 개방 주소 찾기 정책을 사용하며 메모리 통마다 키 값만 설정할 수 있다.충돌을 발견했을 때, 점용되지 않은 통을 찾을 때까지 진열에서 검색했습니다.

우리는 반드시 자신의 해시 함수를 실현해야 합니까?

우리가 자바스크립트를 사용하고 빠른 경량급을 시도할 때, 우선 일반적인 대상이나 맵을 사용하는 것을 고려해야 한다. 왜냐하면 그것은 이미 효과적으로 처리되었기 때문이다.그러나 우리 자신을 실현하는 해시표는 배후에서 무슨 일이 일어났는지 이해하는 데 도움을 줄 것이다.

실시

우선, 우리는 해시표를 하나의 수조로 정의한다.

class HashTable {
    constructor(size=53) {
        this.keyMap = new Array(size);
    }
    _hash(key) {

    }
    set(key, value) {

    }
    get(key) {

    }
}

해시 함수

이 산열 함수는 키에서 0에서 53 사이의 인덱스를 생성합니다.

_hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
        let char = key[i];
        let value = char.charCodeAt(0) - 96;
        total = (total + WEIRD_PRIME * value) % this.keyMap.length;
    }
    return total;
}

별도의 링크 방법으로 삽입

우리는 모든 버킷에 그룹을 만들기 때문에, 키 값을 버킷에 밀어넣기만 하면 됩니다.

set(key, value) {
    let index = this._hash(key);
    if (this.keyMap[index] === null) {
        this.keyMap[index] = [];
    } 
    this.keyMap[index].push([key, value]);
}

찾다

이것은 O(1)개의 시간으로 버킷을 찾을 수 있고, 게다가 버킷 내의 그룹에서 순환할 수 있다.

get(key) {
    let target = this._hash(key);
    if (this.keyMap[target]) {
        for (let i = 0; i < this.keyMap.length; i++) {
            if (this.keyMap[target][i][0] === key) {
                return this.keyMap[target][i][1];
            }
        }
    }
    return undefined;
}

어쩌면, 해시시계는 내가 찾는 것일지도 몰라!

그러면 테마로 돌아가서 어떤 데이터 구조가 나의 크롬 확장 프로젝트의 주요 데이터에 적합합니까?데이터는 다음과 같은 어휘표입니다.

// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "Machine Learning", id: 4, definition: "the action of explaining the meaning of something", tag: ["noun"], word: "interpretation"}
1: {category: "Book1", id: 3, definition: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"], word: "arbitrary"}
2: {category: "Machine Learning", id: 2, definition: "the quality, condition, or fact of being exact and acurate", tag: ["noun"], word: "precision"}
3: {category: "Book2", id: 1, definition: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"], word: "intuitive"}

독특한 단어만이 받아들여져야 우리는 단어를 관건으로 삼을 수 있다.나는 간단하게 그것을 대상으로 실현할 수 있다.

MainData = {}

class Word {
    constructor(tag, category, definition) {
        this.tag        = tag
        this.category   = category
        this.definition = definition
    }
}

const saveWord = (word, tag, category, definition) => {
    if (MainData[word] == null) {
        MainData[word] = new Word(tag, category, definition)
    } else {
        alert('This word already exists in the list.')
    }
}

이를 통해 주요 데이터는 다음과 같습니다.

// Result of console.log(MainData)
arbitrary: { category: "Book1", meanings: "based on random choice or personal whim, rather than any reason or system.", tag: ["adj"]};
interpretation: { category: "Machine Learning", meanings: "the action of explaining the meaning of something", tag:["noun"]};
intuitive: { category: "Book2", meanings: "using or based on what one feels to be true even without conscious reasoning; instinctive", tag: ["adj"]};
precision: { category: "Machine Learning", meanings: "the quality, condition, or fact of being exact and acurate", tag: ["noun"]};

각 객체를 삭제/편집하려면 O(1)만 필요합니다.

결론

지금까지 나는 몇 가지 데이터 구조를 연구했지만 해시표는 지금까지 주요 데이터에 대해 가장 합리적인 것 같다.그러나 나는 끊임없이 자신에게 이런 말을 일깨워 주어야 한다.

Best Isn't Always Best. We need to be pragmatic about choosing appropriate algorithms -- the fastest one is not always the best for the job. (From The Pragmatic Programmer)

아직 많은 데이터 구조를 배워야 하고, 자바스크립트 대상과 맵에 대한 지식도 더 많이 알아야 한다.시종일관 개선할 공간이 있다고 생각한다. 그러면 우리는 우리의 수공예를 더욱 좋아지게 할 기회를 잃지 않을 것이다.

참고

JavaScript Data Structures and Algorithms Masterclass - Udemy
JavaScript Hashmap Equivalent - StackOverflow
5 WAYS TO USE A JAVASCRIPT HASHMAP - Sunfish Empire LLC
Objects and Hash Tables in Javascript - Medium
Hash table - Wikipedia
Are JS objects hash tables? - Quora
Learn to Code with JavaScript Hashes - Codelikethis.
The Pragmatic Programmer - goodreads.com