소개

• 해시 테이블이라고도 알려진 해시 맵은 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 데이터 유형을 구현하는 데이터 구조입니다.

• 해시 함수를 사용하여 원하는 값을 찾을 수 있는 버킷 또는 슬롯 배열에 대한 인덱스를 계산합니다.

• 해시 맵의 가장 큰 장점은 효율성입니다. 새 키-값 쌍 삽입, 키-값 쌍 삭제, 키에 제공된 값 조회 등의 작업은 모두 매우 빠르며 평균적으로 일정한 시간이 걸리는 경우가 많습니다.

JavaScript로 간단한 해시 맵 구현

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

충돌 처리

• 충돌 처리는 해시 맵 구현의 중요한 측면입니다. 두 개의 서로 다른 키가 동일한 해시를 생성하면 충돌이 발생합니다. 충돌을 처리하는 전략에는 여러 가지가 있지만 가장 일반적인 두 가지 전략은 별도 연결과 선형 탐색입니다.

별도의 연결: 별도의 연결에서는 해시 테이블 배열의 각 슬롯에 연결된 목록(또는 여러 항목을 담을 수 있는 다른 데이터 구조)이 포함됩니다. 충돌이 발생하면 새로운 키-값 쌍이 해당 인덱스의 연결 리스트 끝에 추가됩니다.

다음은 JavaScript에서 별도의 연결을 사용하여 해시 맵을 간단하게 구현한 것입니다.

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



선형 탐색: 선형 탐색에서 충돌이 발생하면 해시 맵은 배열의 다음 슬롯을 확인합니다(또한 가득 차면 다음 슬롯으로 계속 진행합니다). 새로운 키-값 쌍을 저장할 수 있는 빈 슬롯.

다음은 JavaScript에서 선형 조사를 사용하여 해시 맵을 간단하게 구현한 것입니다.


class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index   1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index   1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i 



두 예제 모두에서 해시 메서드는 키를 배열의 인덱스로 사용되는 정수로 변환하는 간단한 해시 함수입니다. 실제 시나리오에서는 충돌 가능성을 줄이기 위해 더 복잡한 해시 함수를 사용할 가능성이 높습니다.