어떻게 해시 맵을 실현합니까

메모리의 모든 요소가 연속적이기 때문에 O(1) 또는 정해진 시간에 찾을 수 있기 때문에 수조가 특정 색인에서 원소를 찾는 기능은 매우 놀랍다.그러나, 우리는 통상적으로 색인을 통해 찾을 수 없거나 실행할 수 없습니다.해시영사와 해시표는 이 문제를 해결하는 방법의 하나로 우리가 keys 를 통해 찾을 수 있도록 한다.
너는 처음부터 Map류를 실현할 수 있니?두 가지 방법get과set만 필요합니다.많은 프로그래밍 언어는 내장된 해시나 사전 원어 (예: Javascript Object s와 {} 기호) 를 가지고 있지만, 우리는 이 연습에서 그것을 사용하고 싶지 않다.
이 과정은 https://algodaily.com에 처음 발표되었고 저는 그곳에서 기술 면접 과정을 개설했고 웅대한 개발자를 위해 사고문을 썼습니다.

참고: 일반 Javascript 객체와 Map 클래스는 간단한 키 값 해시 테이블/연관 그룹으로 몇 가지 관건적인 차이가 있습니다.Map 객체는 삽입 순서대로 요소를 누를 수 있지만 JavaScript의 Object 객체는 순서를 보장할 수 없습니다.또한 Object 원형 때문에 기본 키가 있고 Map 기본 키가 없습니다.Here's a good breakdown.본 연습의 목적에서 우리는 둘이 같은 기능을 가지고 있다고 가정합시다.
이 두 가지 방법에 대해 다음과 같이 정의합니다.

get(key: string) 키를 지정하고 해당 키의 값을 반환해야 합니다.

set(key: string, val: string) 키와 값을 매개 변수로 하고 쌍을 저장해야 합니다.

그 밖에 우리는 다음과 같은 해시 함수hashStr를 제공했다.그것은 충돌을 피하려고 시도했지만 완벽하지는 않았다.문자열 값을 받아들이고 정수를 되돌려줍니다.

function hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
        const charCode = str.charCodeAt(i);
        finalHash += charCode;
    }
    return finalHash;
}

console.log(hashStr('testKey'))

새로운 클래스를 Hashmap 클래스라고 부르고 사용합니다.

const m = new Hashmap();
m.set('name', 'Jake');
console.log(m.get('name'));

우선 일반적인 해시표가 어떻게 작동하는지 되돌아보자. 이론은 우리Hashmapdata structure의 기초이다.우리가 주의한 바와 같이 많은 프로그래밍 언어 중 하나Hashmap류는 유류Hashtable를 바탕으로 한다.우리가 건의한 이 코드의 실현을 점차적으로 이해하자.

그래서 우리는 해시표가 데이터를 통에 저장해서 일하는 것을 안다.이 저장소에 접근하기 위해서는 key 을 저장소 번호로 바꾸는 방법이 필요합니다.(수조와 나무로 통을 모델링할 수 있지만 간단하고 속도를 최대한 높이기 위해 우리는 수조를 계속 사용할 것이다.)
키를 사용하면 데이터가 그룹에 있는 위치를 알 필요가 없습니다.따라서 우리의 data structure 는 산열 함수가 필요합니다. 이 예에서 hashStr 로 제공하여 index 를 buckets 로 계산하여 원하는 값을 저장합니다.우리는 본질적으로 key 산열 함수를 통해 hashStr 을 그룹 인덱스에 비추는 것이다.

hashStr('r')
// 114

// array = [  _  ,  X  ,  _  ,  _ ]
// index     113   114   115   116

보시다시피 hashStr 의 작업은 key 에서 제공한 set() 만 취하고 위치를 계산해 줍니다.따라서 실제 저장과 방치 값에 사용할 다른 data structure 저장소가 필요합니다.물론, 너는 이미 이것이 수조라는 것을 알고 있다.

기입하다

해시 테이블의 간격이나 스토리지 통은 일반적으로 __________ 및 해당 인덱스에 저장됩니다.
솔루션: 스토리지
이 클래스를 작성하는 좋은 시작은 스토리지 어레이만 초기화하는 것입니다.

class Hashmap {
  constructor() {
    this._storage = [];
  }
}

우리는 입력 값이 hashStr 에 놓여야 할 위치를 결정하기 위해 되돌아오는 인덱스 this._storage 를 사용할 것이다.
충돌의 단어: collisions 해시 함수가 여러 개의 키로 같은 색인을 되돌려 주고 이 문제의 범위에 있지 않다는 것을 가리킨다.그러나 이런 문제를 처리하기 위해 추가 데이터 구조를 사용할 수 있는 방법이 있다.

다중 선택

다음 중 충돌을 해결하는 해시표는 무엇입니까?

좋은 충돌 해결 방안이 없으면 해시 함수가 유일해야 한다

단독 링크를 사용하고 체인 테이블을 사용하는데 그 중에서 수조의 인덱스는 값 체인으로 구성된다

trie를 사용하여 색인당 값 저장

모든 값을 이 저장소

에 연결하는 단일 문자열
해결 방안: 단독 링크를 사용하여 체인 테이블과 함께 사용하는데 그 중에서 수조의 인덱스는 값 체인으로 구성된다
이제 우리는 구축 블록이 생겼기 때문에 set 방법을 계속 실현합시다.이 메서드는 다음을 수행합니다.

취key통과

해시 함수를 통해 실행하고

특정 색인

에 우리storage의 값을 설정합니다
우리가 그것을 저장하는 방식에 주의하십시오. this._storage this._storage[idx] 의 모든 인덱스는 하나의 수조이기 때문에 기본적으로 충돌 문제를 해결했습니다.

set(key, val) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    this._storage[idx] = [];
  }

  this._storage[idx].push([key, val]);
}

set 방법은 지금 보기에 매우 간단해 보인다. 그렇지?
이것은 우리의 get 방법의 개념과 같다.우리가 그곳에서 한 것은 key 방법을 통해 전달된 hashStr 을 실행하는 것이지만, 우리는 설정이 아니라 결과 인덱스로 돌아가 값을 검색할 것이다.

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }

우리가 주의해야 할 점은 존재하지 않거나 존재하지 않는 키를 전달하는 것이 가능하다는 것이다. 따라서 이런 상황이라면 되돌아오는 것을 통해 처리해야 한다.

get(key) {
  let idx = this.hashStr(key);

  if (!this._storage[idx]) {
    return undefined;
  }

  for (let keyVal of this._storage[idx]) {
    if (keyVal[0] === key) {
      return keyVal[1];
    }
  }
}

그럼 얼마 안 남았을 거야!한번 해볼게요.

class Hashmap {
  constructor() {
    this._storage = [];
  }

  hashStr(str) {
    let finalHash = 0;
    for (let i = 0; i < str.length; i++) {
      const charCode = str.charCodeAt(i);
      finalHash += charCode;
    }
    return finalHash;
  }

  set(key, val) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      this._storage[idx] = [];
    }

    this._storage[idx].push([key, val]);
  }

  get(key) {
    let idx = this.hashStr(key);

    if (!this._storage[idx]) {
      return undefined;
    }

    for (let keyVal of this._storage[idx]) {
      if (keyVal[0] === key) {
        return keyVal[1];
      }
    }
  }
}

이 과정은 https://algodaily.com에 처음 발표되었고 저는 그곳에서 기술 면접 과정을 개설했고 웅대한 개발자를 위해 사고문을 썼습니다.