📅 2025-11-05

➡️ 해시 알고리즘에 대해 새롭게 알게 된 것 또는 헷갈리는 부분 정리

---

🔎 학습 리마인드

📌 해시 (Hash)

💡 Hash

• 임의의 데이터를 고정된 길이의 요약 값으로 바꾼 결과
• 자바스크립에서 이미 Object와 Map이 내부적으로 해시 구조를 사용하고 있음

목적

• 데이터를 비교하지 않고 구분
• 원본보다 짧고 일정한 길이로 표현
• 보안, 탐색, 무결성 검사, 캐싱 등에 활용

💡 해시 함수 (Hash Function)

• 데이터를 일정한 규칙으로 압축하는 함수
• 해시 값을 만들어내는 알고리즘

해시 함수의 결과값은 정수

• 해시 함수는 문자열이나 객체처럼 복잡한 데이터를 배열의 인덱스로 사용하기 위해 항상 정수(숫자, integer) 형태로 반환함

  "name" → hash("name") = 3 → table[3] = "홍길동"

  배열의 인덱스는 반드시 정수여야 하기 때문에 모든 해시 함수는 결국 정수를 반환하도록 설계되어 있음
  

특징

특징	설명
고유한 길이 출력	입력 크기와 관계없이 일정한 길이 정수 반환
빠른 계산	어떤 데이터든 빠르게 해시값 생성
동일 입력 → 동일 출력	같은 데이터는 항상 같은 해시값 반환
작은 변화 → 큰 차이	입력이 조금 달라져도 해시값 완전히 달라짐
충돌 가능성	서로 다른 입력이 같은 해시값을 가질 수 있음

간단 예시

function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) - hash + str.charCodeAt(i);
    hash |= 0; // 32비트 정수 변환
  }
  return hash;
}

console.log(simpleHash("apple")); // 예: 93029210
console.log(simpleHash("APPLE")); // 예: 12382010

💡 해싱 (Hasing)

• 데이터(키)를 해시 함수를 통해 고정된 숫자로 바꾸는 과정
• 복잡한 데이터를 주소처럼 짧게 압축하는 기술
• 예)

  데이터(Key)	해시값(Hash Value)
  “Kim”(75 + 105 + 109)	289
  “Jung” (74+117+110+103)	404
  “Choi”(67+104+111+105)	387
  “Kang”(75+97+110+103)	385

  이렇게 문자열을 숫자로 바꿔서 배열 인덱스처럼 사용할 수 있는것이 해싱(hasing)
  

필요한 이유

• 배열: 숫자 인덱스로만 빠르게 접근 가능
• 객체: 내부적으로 문자열을 숫자로 변환하여 저장 → 빠른 검색

---

📌 해시 충돌 (Collision)

• 서로 다른 키가 같은 해시값을 가지는 경우
• 저장 공간이 한정되어 있기 때문에 발생

💡 해결 방법: 분리 연결법 (Separate Chaining)

• 같은 인덱스에 여러 개를 리스트로 저장
• 예)

  const table = [];
  
  function set(key, value) {
    const index = simpleHash(key, 5);
    if (!table[index]) table[index] = [];
    table[index].push([key, value]);
  }
  
  set("a", 1);
  set("d", 2); // 해시 충돌
  console.log(table);

  같은 주소에 여러 개의 데이터가 생기면 배열 안에 배열로 묶어서 저장
  

💡 해결 방법: 개방 주소법 (Open Addressing)

• 비어있는 인덱스를 찾아 다른 칸에 저장
• 예)

  const table = new Array(5);
  
  function set(key, value) {
    let index = simpleHash(key, 5);
    while (table[index]) {
      index = (index + 1) % table.length; // 다음 칸 탐색
    }
    table[index] = [key, value];
  }

  문이 막혀 있으면 옆으로 한 칸씩 밀어서 저장하는 방식 → 탐색은 느리지만 메모리를 절약할 수 있음

---

📌 해시 테이블

• 해싱을 이용해서 데이터를 저장/검색하는 자료구조

💡 용어 정리

용어	의미
Key	데이터 식별자
Value	저장할 값
Hash Function	키 → 인덱스 변환 함수
Bucket	실제 데이터를 저장하는 칸 (체인)

💡 기본 해시 테이블 구현

class HashTable {
  constructor(size = 10) {
    this.table = new Array(size);
  }

  hash(key) {
    let hash = 0;
    for (let char of key) hash += char.charCodeAt(0);
    return hash % this.table.length;
  }

  set(key, value) {
    const index = this.hash(key);
    this.table[index] = [key, value];
  }

  get(key) {
    const index = this.hash(key);
    return this.table[index]?.[1];
  }
}

const hash = new HashTable();

hash.set('ab', 20);
hash.set('ba', 31);
console.log(h.get('ab')); // 31 -> 해시 충돌

❗ 해시 충돌

'ab' → 97 + 98 = 195
'ba' → 98 + 97 = 195

→ 두 키 모두 인덱스 5번에 저장되어 충돌 발생

- 기본 해시 테이블에서는 나중에 들어온 값이 이전 값을 덮어쓰기 때문에 'ab'를 출력해도 '31'이 나옴

💡 충돌 해결 - 분리 연결법 적용

class HashTable {
    constructor(size = 10) {
        this.table = new Array(size);
    }

    hash(key) {
        let hashCode = 0;

        for (let char of key) hashCode += char.charCodeAt();

        return hashCode % this.table.length;
    }

    // 저장
    set(key, value) {
        const hashIndex = this.hash(key);

        // 인덱스(버킷)에 아무것도 없으면 []을 만들어 초기화 -> 같은 인덱스에 여러 데이터를 담는 체인 역할
        if (!this.table[hashIndex]) {
            this.table[hashIndex] = [];
        }

        const bucket = this.table[hashIndex];

        for (let pair of bucket) {
            if (pair[0] === key) {
                pair[1] = value;
                return;
            }
        }

        bucket.push([key, value]);
    }

    // 가져오기
    get(key) {
        const hashIndex = this.hash(key);
        const bucket = this.table[hashIndex];

        if (!bucket) return;

        for (let pair of bucket) {
            if (pair[0] === key) return pair[1];
        }
    }

    // 삭제
    remove(key) {
        const hashIndex = this.hash(key);
        const bucket = this.table[hashIndex];

        for (let i = 0; i < bucket.length; i++) {
            if (bucket[i][0] === key) {
                bucket.splice(i, 1); // 배열 삭제
                console.log(bucket);
                return true;
            }
        }
        return false;
    }
}

const h = new HashTable();
h.set('ab', 20);
h.set('ba', 31);

console.log(h.table);

console.log(h.get('ab')); // 20

console.log(h.remove('ab'));
console.log(h.table);

---