[자료구조] 해시 (Hash)

 해시 (Hash) 

해시는 무엇일까? 또 해시 테이블은 해시랑 같은것일까?

이에 대해 차근차근 살펴보고자 한다.

 

1. 배열 vs 해시 테이블

일반적으로, 데이터를 저장하고 활용하는 방법으로 배열(Array)을 떠올릴 수 있다. 아래의 예시를 보면, menu에 push를 통해 새로운 값을 추가할 수도 있고, for문 등을 통해 특정 값을 찾아볼 수도 있다. 즉, 배열은 특정 값을 찾기 위해 인덱스 0번부터 끝까지 탐색하는  선형 검색(Linear Search)  방식을 사용한다. 따라서 n개의 요소를 가진 배열을 순차적으로 검색하기에  시간 복잡도는 O(n) 이며, 살펴봐야 할 요소가 늘어날수록 시간은 무한히 늘어난다.

 

const menu = [
    { "icecream": 1000 },
    { "coke": 1500 },
    { "hamburger": 3000 }
];

menu.push({ "coffee": 2000 });

// 탐색
for (let i = 0; i < menu.length; i++) {
  const item = menu[i];
  if ("coffee" in item) {
    console.log(item["coffee"]);
  }
}

 

 

이러한 시간 효율 문제를 개선하기 위해 등장한 자료구조가 바로 해시 테이블이다.

 해시 테이블(Hash Table) 은 key와 value 형태로 데이터가 저장된 자료구조이다. 특정 값을 찾기 위해 key만 알고 있으면 되며,  시간 복잡도는 O(1) , 즉 상수 시간(constant time)만큼 걸린다. 데이터를 추가하거나 삭제할 때도 O(1)만큼만 소모되므로 배열에 비해 매우 효율적이다.

 

const menu = {
    icecream: 1000,
    coke: 1500,
    hamburger: 3000
};

menu.coffee = 2000;

// 탐색
console.log(menu["coffee"]);  // 2000

 

반응형

 

---

2. 해시 테이블의 원리

그렇다면 해시 테이블은 어떻게 배열보다 효율적일 수 있을까?

이에 대해 이해하려면 해시와 해시 함수에 대해 알 필요가 있다.

 

먼저,  해시(hash) 는 어떤 데이터를 고정된 크기의 값으로 변환하는 것을 말하며, 이 값은  해시 함수(hash function) 에 의해 생성되며 이 과정을 해싱(hashing)이라고 한다. 이렇게 생성된 값을  해시값(hashcode) 이라 하며, 해시값은 특정 데이터를 저장할 때 인덱스번호로 활용된다.

 

이때 해시값으로 변환해주는 해시 함수에도 여러 종류가 있다.

대표적인 해시 함수에는 다음과 같은 것이 있다.

 

1. Division Hashing

 

• 입력 데이터(key)를 해시 테이블의 크기로 나눈 나머지를 해시값으로 사용하는 방법
  
  
• 단순하고 빠른 방법이지만, 해시값의 분포가 고르지 않을 수 있다(동일한 해시값에 데이터가 치우칠 수 있다).
  
  

2. Multiplication Hashing

 

• 해시값 = Math.floor(((숫자로된 key) * (0과 1 사이의 수) % 1) * (2의 거듭제곱인 해시 데이블 크기))
  
  
• 해시값의 분포를 균동하게 유지하는 특징이 있어 해시 충돌을 줄이는데 도움이 된다.

function multiplicationHash(key, tableSize) {
  const constantA = 0.6180339887; // 예시로 사용하는 상수 A
  const hashValue = Math.floor(tableSize * ((key * constantA) % 1));
  return hashValue;
}

const key = 42; // 예시로 사용하는 입력 데이터
const tableSize = 16; // 해시 테이블의 크기
const hashValue = multiplicationHash(key, tableSize);
console.log(hashValue); // 예시 출력: 10

 

3. Universal Hashing

 

• 여러 개의 해시 함수를 집합에 넣어두고, 무작위로 해시 함수를 선택해 해시값을 만드는 방법
• 해시 충돌을 최소화하고, 무작위로 선택하는 특성 때문에 보안성도 강화된다.
• 여러 개의 해시 함수를 미리 정의해야 하기 때문에 메모리를 조금 더 사용한다는 단점이 있다.

 

 

앞서 살펴본 해시 테이블은 key와 value로 이루어진 자료구조이지만, 내부적으로 살펴보면  배열(Array)의 구조 를 띄고 있다.

먼저, 해시 테이블은 정해진 개수(크기)의 bucket을 가진 배열의 형태다. 그리고 해시 함수를 통해 특정 데이터(key)를 해시값으로 변환하고, 이 해시값이 데이터의 인덱스번호가 된다. 그리고 이 인덱스번호에 있는 버킷(bucket)에 데이터를 저장해주는 식이다.

아래의 예시를 보면, 길이가 16인 배열에 특정 사람들의 전화번호를 저장해주는 해시 테이블이 있다. 해시 함수는 이름을 해시값으로 변환해주고, 그 해시값에 해당하는 bucket에 전화번호를 저장해준다. 그리고 우리는 "John Smith"라는 key값으로 바로 "521-1234"라는 value값을 가져올 수 있다. 이것이 가능한 이유는 인덱스번호인 해시값을 통해 바로 배열에서 값을 찾아냈기 때문에 가능한 것이다. 이처럼 해시 테이블을 사용하면 for문 등을 사용해 배열의 모든 데이터를 살펴볼 필요가 없다.

 

이름(key)으로 버킷에서 전화번호를 찾아오는 해시 테이블

 

728x90

 

---

3. 해시 충돌

그러나 해싱을 하는 과정에서  해시 충돌(Hash Collision) 이라는 문제가 발생할 수 있다.

만약 입력한 데이터의 문자열 길이를 해시 테이블 크기로 나누는 Division Hashing 함수가 있다고 할 때, 문자열 길이가 같은 key들은 특정 인덱스 bucket에 2차원 배열 형태로 저장된다. 만약 n개의 key들이 모두 동일한 인덱스번호를 가진다면, 시간 복잡도는 O(1)에서 O(n)까지 악화될 수 있다. 즉, 특정 배열(bucket) 내의 모든 요소를 for문으로 탐색하는 것과 동일한 현상이 발생하는 것이다. 따라서 모든 배열방에 골고루 데이터가 분배되는 것이 중요하다.

 

해시 충돌 (Hash Collision)

 

---

4. 해결 방법

해시 충돌을 해결하는 대표적 방법에는 체이닝과 개방 주소법이 있다.

 

4-1) 체이닝 (Chaining)

 체이닝(Chaining) 은 충돌이 일어난 bucket에 연결리스트를 이용해 충돌된 데이터를 저장하는 방법니다. 만약 동일한 인덱스값(해시값)을 가진 데이터가 존재한다면, 각 bucket이 헤드가 되어 충돌된 데이터들이 순차적으로 추가된다.

이 방법을 사용하면 인덱스가 변하지 않고 데이터를 추가할 수 있으며, 데이터의 개수 제한 없이 추가할 수 있다.

다만, 각 bucket마다 연결리스트를 유지해야 하므로 충돌이 발생하지 않아도 유지를 위해 메모리 상에서 추가적인 공간을 차지하게 된다.

 

연결리스트에 대해 익숙하지 않다면, 아래 글을 먼저 읽어보길 바란다.

https://valueengine.tistory.com/6

[자료구조] 연결리스트 (Linked List)

 

4-2) 개방 주소법 (Open Addressing)

 개방 주소법 (Open Addressing) 은 충돌이 발생했을 때 다른 빈 bucket을 찾아 데이터를 저장하는 방법이다.

이 방법을 사용하면 추가적인 연결리스트를 유지할 필요가 없어 메모리 사용량이 체이닝에 비해 적고, 연속적으로 데이터가 저장되기 때문에 캐시 효율도 좋아진다.

다만, 다른 데이터가 들어가있으면 원래 그 인덱스번호 bucket에 들어가야 하는 데이터의 인덱스번호가 바뀌게 되고, 로드 팩터(load fact, 부하율)에 따라 성능이 달라질 수 있다. 로드 팩터는 해시 테이블에 저장된 데이터 수와 bucket 수의 비율을 나타내며, 높은 로드 팩터일수록 충돌이 발생할 확률이 높아지고 성능도 저하된다.

 

 

개방 주소법을 활용하기 위해선 어떻게 빈 bucket을 찾을지에 대해서도 알아야 한다.

여기에는 선형 탐색, 제곱 탐색, 더블 해싱 총 3가지 방법이 있다.

 

(1) 선형 탐색

 선형 탐색(Linear Probing) 은 충돌이 발생한 지점에서 고정폭(n)만큼 이동하면서 빈 bucket을 찾는 방법이다.

구현이 간단하지만 primary clustring 문제에 취약하다는 단점이 있다. 아래의 사진을 보면, 최초 충돌이 발생한 bucket 주변에 데이터들이 저장되게 된다. 즉, 데이터의 균등한 분포를 방해할 뿐만 아니라, 선형 탐색 시간을 증가시키고, 캐시 효율성을 떨어트릴 수 있다.

 

선형 탐색 (Linear Probing)

(2) 제곱 탐색

 제곱 탐색 (Quadratic Probing) 은 일정한 간격(제곱수)으로 이동하면서 빈 bucket을 찾는 방법이다.

선형 탐색과 달리 제곱수 간격으로 이동하기 땜에 primary clustering 현상이 발생하는 것을 어느 정도 막을 수 있다. 또한, 일정한 간격으로 이동하기 때문에 충돌 해결 시도 횟수도 선형 탐색에 비해 줄어든다.

그러나 secondary clustering에 취약하다. 이는 같은 해시값을 가진 데이터들이 동일한 간격으로 이동할 때 발생한다. 이로 인해 충돌이 발생한 데이터들이 서로 근접한 위치에 몰릴 가능성이 있다.

 

제곱 탐색 (Quadratic Probing)

(3) 더블 해싱

 더블 해싱(Double Hashing) 은 두 개의 해시 함수를 사용하여 충돌이 발생할 경우 다른 해시 함수로 계산된 값에 따라 빈 bucket을 찾는 방법이다.

이 방법을 사용하면 primary clustering이 발생할 가능성을 낮춰줘 데이터가 더 균형있게 분포할 수 있도록 도와준다. 또, 충돌이 발생한 경우에도 다른 해시 함수로 빈 bucket을 찾기 때문에 선형 탐색이나 제곱 탐색과 같은 순차적인 탐색보다 더 빠른 검색 성능을 제공해줄 수 있다.

다만, 충돌을 최소화하고 균등한 분배를 위해 적절한 2개의 해시 함수를 선택하는 것이 결코 쉽지 않으며, 더블 해싱에서도 2번째 해시 함수의 값에 따라 데이터가 서로 근접한 위치에 저장될 수 있다.

 

---

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://youtu.be/zFL29ydL9D8
• https://youtu.be/HraOg7W3VAM
• https://youtu.be/Vi0hauJemxA
• https://velog.io/@edie_ko/hashtable-with-js
• https://st-lab.tistory.com/240
• https://eunjinii.tistory.com/m/87