[알고리즘과 자료구조] 해시 테이블에 대해서 알아보자

sangsang·2024년 2월 29일
누구나 자료구조와 알고리즘알고리즘자료구조해시테이블
0

누구나 자료구조와 알고리즘

목록 보기
7/13
post-thumbnail

📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다.

8장 해시 테이블로 매우 빠른 룩업

이번 장에서는 해시테이블(Hash Table)이라는 특수한 자료구조에 대해서 알아보자

8-1. 해시 테이블

해시 테이블(Hash Table) 이란?
: 키(key)와 값(value) 쌍으로 이뤄진 리스트

해시 테이블은 다양한 프로그래밍 언어에서 해시, 맵, 해시 맵 딕셔너리, 연관 배열 등의 이름을 갖는다. 해시 테이블의 값은 Key를 통해 딱 한 단계로 찾을 수 있다. O(1)의 시간 복잡도를 갖는다.

  • menu 해시테이블에서 french fries는 Key, 0.75는 값이다.
menu = { "french fries" => 0.75, "hamburger" => 2.5, "hot dog" => 1.5" }
  • 해시 테이블의 값 찾는 방법
menu["french fries"]

8-2. 해시 함수로 해싱

  • 해싱(Hasing): 문자를 숫자로 변화하는 과정
  • 해시 함수(Hash function): 글자를 특정 숫자로 변환하는 데 사용한 코드

다음 예시를 통해 다양한 '해시 함수'에 대해서 알아보자.

A = 1 
B = 2
C = 3 
D = 4
E = 5
...

위 코드에 따르면 아래와 같이 문자를 숫자로 변환할 수 있다.

1) 단순하게 글자와 숫자 짝짓는 해시 함수

ACE = 135
CAB = 312
DAB = 412

2) 각 문자 해당하는 숫자를 합치는 해시 함수

ACE = 1 + 3 + 5 = 9
CAB = 3 + 1 + 2 = 6
DAB = 4 + 1 + 2 = 7

3) 각 문자 해당하는 숫자를 곱하는 해시 함수

ACE = 1 * 3 * 5 = 15
CAB = 3 * 1 * 2 = 6
DAB = 4 * 1 * 2 = 8

해시 함수가 유효 기준은 해시 함수에 적용할 때마다 동일한 문자열을 항상 동일한 숫자로 변환해야 한다

만약 난수나 시간을 사용하는 경우, 동일한 문자열이 동일한 숫자로 변환되지 않기 때문에 해시함수로 유효하지 않다.

위 예시로 든 곱셈 해시 함수에도 문제가 한가지 있는데, 예를 들어 DAB와 BAD는 다른 문자열이 똑같이 8로 변환된다. 이로 인해 실제로 문제가 발생한다. 이 문제는 나중에 알아보도록 하자.

8-3. 재미와 이익, 특히 이익을 남길 유의어 사전 만들기

유의어 사전 앱 만들기를 예제를 통해 해시 테이블에 대해 알아보자

유의어 사전 앱은 사용자가 특정 단어를 검색하면 유의어를 딱 하나만 반환한다. 해시 테이블로 유의어 사전을 표현할 수 있다.

해시 테이블은 배열과 유사하게 데이터를 한줄로 이뤄진 셀 묶음에 저장한다. 각 셀마다 주소가 있다. '곱셈' 해시함수를 예로 들어 다음과 같이 표시할 수 있다.
( 곱셈 해시 함수는 인덱스 0에 아무 값도 저장되지 않으므로 인덱스 0는 제외 )

12345678910

'곱셈' 해시 함수를 통해 해시 테이블에 값(Value)이 저장되는 과정을 알아보자

  1. "bad"의 유의어가 "evil"일 경우, 해시 테이블에서 "bad"는 Key, "evil"는 Value가 된다. 
- 다음과 같이 해시 테이블에 Key => Value 형태로 저장

{"bad" => "evil"}
  1. Key("bad")에 해시 함수를 적용한다. 다음과 같이 계산된다.
- '곱셈' 해시 함수로 해싱한 결과

BAD = 2 * 1 * 4 = 8
  1. Key("bad")는 8로 해싱되므로 Value("evil")를 인덱스 8에 저장한다.
12345678910
"evil"

8-4. 해시 테이블 룩업

해시 테이블은 키가 값의 위치를 결정하므로 키 해싱해서 값의 위치를 한번에 찾을 수 있다.
O(1)의 시간 복잡도를 갖기 때문에 선형 검색 또는 이진 검색보다 훨씬 빠르게 값을 찾을 수 있다.

단방향 룩업

해시 테이블은 단방향 룩업에서 효율적이다.

키로 값을 찾을 때 O(1)의 시간 복잡도를 갖는다. 반대로 값으로 키를 찾지 못하기 때문에 최악의 상황의 경우 모든 값을 검색해야 한다. 값으로 키를 찾을 때 O(N)의 시간 복잡도가 걸린다.

해시 테이블에서 키(Key)는 어떠한 특징을 가질까?

1. 키는 값 바로 옆에 저장된다.
앞선 내용에서 해시테이블에 값이 저장되는 모습을 보았다. 키는 언어에 따라 다르지만 값 바로 옆에 키를 저장한다.

2. 키는 해시 테이블에 딱 하나만 존재할 수 있다.
키는 중복해서 사용할 수 없지만, 값은 여러 인스턴스가 존재할 수 있다.

3. 이미 존재하는 키에 키/값 쌍을 저장하면 키는 두고 기존 값만 덮어쓴다.

8-5. 충돌 해결

'충돌'이란?
: 해시 테이블의 셀에 데이터를 추가할 때 이미 셀에 값이 존재하는 상황

  • 충돌 상황을 다음 예시로 설명한다.
1. 키("dab")에 값("pat")을 저장하려고 한다.

{"dab" => "pat"}

2. 키를 해싱하여 값을 저장할 인덱스를 구한다.

DAB = 4 * 1 * 2 = 8

3. 이미 인덱스 8번에 값이 저장되어 있다. => 충돌(Collision)

4. 충돌을 어떻게 해결해야 할까???????

분리 연결법(Separate Chaining)
: 충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법

위 충돌 상황에서 인덱스 8에 이미 값이 존재한다면, 인덱스 8에 배열 형태로 키/값을 저장한다. 이런 상태에서 키("dab")의 값을 찾으려고 한다면 어떻게 될까?

1. 키("dab") 값("pat")을 찾으려고 한다.

{"dab" => "pat"}

2. 키를 해싱하여 값이 저장된 인덱스를 구한다.

DAB = 4 * 1 * 2 = 8

3. 인덱스 8에 하나의 값이 아닌 이중 배열 형태로 저장되어 있다.

[["bad","evil"],["dab","pat"]]

4. 해당 배열의 인덱스 0부터 키("dab")를 찾을 때까지 차례대로 검색한다.

5. 배열에서 키("dab")가 저장된 인덱스 1의 하위 배열 값을 반환한다.

하나의 인덱스(셀)에 여러 개의 키/값이 저장돼 있는 경우, 배열을 참조하기 때문에 값을 찾기 위해 선형 검색을 해야 한다. 만약 하나의 셀에 모든 데이터가 저장돼 있다면, 해시 테이블은 배열보다 나은 게 없다. 이러한 최악의 경우, O(N)의 시간 복잡도를 갖게 될 것이다.

해시 테이블 검색에서 O(1)의 시간 복잡도를 유지할 수 있도록 충돌을 최소화해야 한다. 어떻게 해시 테이블에서 충돌을 최소화할 수 있을까?

8-6. 효율적인 해시 테이블 만들기

해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.

  1. 해시 테이블에 얼마나 많은 데이터를 저장하는가
  2. 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
  3. 어떤 해시 함수를 사용하는가

1, 2번째 요인은 적은 셀에 많은 데이터를 저장하려면 충돌이 많이 발생하고, 해시 테이블의 효율성이 떨어지기 때문이다. 3번째 요인의 경우, 해시 함수가 효율성과 어떠한 관계가 있는지 알아보자.

해시함수에 따라 효율성에 어떠한 영향을 줄까?

항상 1과 9 사이에 값만 반환하는 해시 함수를 사용한다고 가정하자.

1) 키("PUT")를 해싱한다.

PUT = 16 + 21 + 20 = 57

2) 57는 1과 9 사이에 값이 아니기 때문에 숫자를 쪼갠다.

5 + 7 = 12

3) 12 또한 1과 9 사이에 값이 아니기 때문에 숫자를 쪼갠다.

1 + 2 = 3

4) 3는 1과 9 사이에 값이기 때문에 PUT는 3으로 해싱된다.

만약 해시 테이블의 셀 개수가 16개라면, 10부터 16번째 셀은 사용되지 않는다.
모든 데이터는 1번째 셀부터 9번째 셀까지만 채워진다. 이러한 경우 충돌이 발생할 가능성이 높기 때문에 효율성에도 안 좋은 영향을 미친다.

훌륭한 충돌 조정

좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 충돌을 최소화한다.

충돌을 피하기 위해서 데이터보다 너무 많은 셀을 만든다면 불필요한 메모리를 사용하게 된다. 좋은 해시 테이블은 메모리 낭비하지 않는 선에서 충돌을 피하도록 설계한 것이다. 그럼 데이터와 셀의 어느 정도의 비율 가지는 것이 좋은 해시 테이블일까?

부하율(Load Factor)
: 데이터와 셀의 비율

훌륭한 충돌 조정을 위해 이상적인 부하율은 0.7(데이터 7개 / 셀 10개)라고 한다. 프로그래밍 언어는 최고의 성능을 내도록 데이터에 따라 셀을 설계하며 해시 테이블을 확장할 것이다.

8-7. 해시 테이블로 데이터 조직

데이터 구조 관점에서 해시 테이블의 다양한 유스 케이스를 살펴보자.

해시 테이블이 데이터를 키/값 쌍으로 데이터를 조직하는 특징을 다음 상황에서 찾아볼 수 있다.

  • 패스트 푸드 메뉴와 유의어 사전 시나리오

  • 정치 후보자와 각 득표수

  • 품목의 재고를 기록 하는 재고 관리 시스템

  • HTTP 상태 코드 번호와 그 의미를 반환하는 것

  • 다양한 속성을 갖는 객체

8-8. 해시 테이블로 속도 올리기

해시 테이블은 쌍이 아닌 데이터에서도 쓰일 수 있다.

배열 [16 30, 91, 11, 54, 38, 72]

위 수 배열을 선형 검색할 경우 O(N)의 시간 복잡도를 갖는다. 하지만 이 배열을 해시 테이블로 변환한다면 어떻게 될까?

해시 테이블로 만들기 위해서 각 수를 키로 저장하고 값엔 true를 할당한다.

hash_table = {
61 => true, 30 => true, 91 =>true, 
11 => true, 54 => true, 38 => true, 72 => true
}

만약 위 해시테이블에서 찾는 수가 있다면 true를, 없다면 null를 반환한다.
해시 테이블에서 수를 키로 한번에 찾을 수 있기 때문에 O(1) 시간 복잡도를 갖게 된다.

해시 테이블이 인덱스 역할을 해서 해당하는 값에 한번에 접근할 수 있다. 이 기법을 사용해서 실제 알고리즘의 속도를 올려보자.

배열 부분 집합

두 배열을 비교해서 부분 집합을 알려주는 함수를 작성해보자

  • 중첩 for 문 사용한 알고리즘
    길이가 더 작은 배열의 원소에 대해 길이 더 큰 배열의 각 원소를 순회한다. 작은 배열의 원소가 큰 배열에 없으면 false를 반환하고, 있다면 true를 반환한다.
function isSubset(array1, array2) {
	let largerArray;
  	let smallerArray;
  
  // 어느 배열이 더 작은지 알아낸다.
  if (array1.length > array2.length) {
    largeArray = array1;
    smallerArray = array2;
  } else {
  	largeArray = array2;
    smllerArray = array1;
  }
  
  // 작은 배열부터 순회한다.
  for (let i = 0; i < smallerArray.length; i++) {
  	//작은 배열의 현재 값이 우선은 큰 배열에 없다고 임시로 가정
    let foundMatch = false;
    
    //작은 배열의 각 값에 대해 큰 배열을 순회한다.
    for (let j = 0; j < largerArray.length; j++) {
    	// 두 값이 같으면 작은 배열의 현재 값이 큰 배열에 있다는 뜻
      if (smallerArray[i] === largerArray[j]) {
        foundMatch = true;
        break;
    }
  }
    // 작은 배열의 현재 값이 큰 배열에 없으면 false를 반환
    if (foundMatch === false) return false;
 }
  // 루프 끝에 도달하면 작은 배열의 모든 값이 큰 배열에 있다는 뜻
  return true;
  
}

위 알고리즘의 효율성을 분석하면, O(N * M)이다. 이제 해시 테이블을 활용해 알고리즘의 효율성을 개선해 보자.

  • 해시 테이블을 사용한 알고리즘
    1) 어느 배열이 더 큰지 알아낸 후 큰 배열을 순회하는 루프 하나만 실행해서 해시 테이블에 각 값을 저장한다.
let hashTable = {};

for (const value of largerArray) {
	hashTable[value] = true;
}

위 코드는 hashTable 변수에 빈 해시 테이블을 생성한다. 이어서 largerArray의 각 값을 순회하며 배열의 항목을 해시 테이블에 추가한다. 항목 자체를 키로, true를 값으로 추가한다. 

{"a": true, "b": true, "c": true, "d": true, "e": true, "f": true}

2) 첫 번째 for 문 종료 후 해시 테이블 생성되면 두 번째 for 문으로 작은 배열을 순회한다.

for (const value of smallerArray) {
	if (!hashTable[value]) return false;
}

위 루프는 smallerArray 내 각 항목이 hashTable에 키로 존재하는지 확인한다. 키가 없으면 큰 배열의 부분 집합이 아니므로 false를 반환한다. 반대로 루프를 그대로 통과하면 작은 배열이 큰 배열의 부분 집합이라는 뜻이다.

해시테이블 전체 코드

function isSubset(array1, array2) {
	let largerArray;
	let smallerArray;
  	let hashTable = {};
  
   // 어느 배열이 더 큰지 알아낸다.
  if (array1.length > array2.length) {
    largeArray = array1;
    smallerArray = array2;
  } else {
  	largeArray = array2;
    smllerArray = array1;
  }
  
  // largerArray의 모든 항목을 hashTable에 저장한다.
  for (const value of largerArray) {
	hashTable[value] = true;
}
  
  // smllerArray의 각 항목을 순회하며 
  // hashTable에 없는 항목이면 false를 반환한다.
  for (const value of smallerArray) {
	if (!hashTable[value]) return false;
}
  
 // false를 반환하지 않았다면 smallerArray는 largerArray의 부분집합
   return true;
}

위 해시 테이블로 구현한 알고리즘은 O(N)이다. 두 배열의 총 원소 개수가 N일 때, 각 항목을 한 번씩 순회하기 때문이다. 중첩 for 문으로 구현한 알고리즘에 비해 효율성이 많이 개선되었다.

이러한 해시 테이블의 효율성 덕분에 배열을 여러 번 검색해야 하는 알고리즘에서 해시테이블을 많이 사용한다.

연습문제

  1. 두 배열의 교집합을 반환하는 함수를 작성하라. 예를 들어, [1,2,3,4,5]와 [0,2,4,6,8]의 교집합은 [2,4]이다. (단, 함수의 시간 복잡도는 O(N))
function getIntersection (array1, array2) {
	let intersection = [];
	let smallerArray = [];
    let largerArray = [];
    let hash_table = {}
    
    // 두 배열의 길이 비교
    if (array1.length < array2.length) {
    	smallerArray = array1
        largerArray = array2
    } else {
    	smallerArray = array2
        largerArray = array1
    }
    
    // 긴 배열을 해시테이블에 키/값 형태로 저장
    for (let value of largerArray) {
    	hash_table[value] = true
    }
    
    // 짧은 배열의 값이 해시테이블에 있는지 확인
    for (let value of smallerArray) {
    	if (hash_table[value]) {
        	intersection.push(value)
        }
    }
    
	return intersection
}
  1. 문자열 배열을 받아 첫 번째 중복 값을 찾아 반환하는 함수를 작성하라. 예를 들어, 배열 ["a","b","c","d","e","f"]면 함수는 배열에서 중복인 "c"를 반환해야 한다. (단, 함수의 시간 복잡도는 O(N))
function getDuplication(array) {
  let hash_table = {};

  // for of 문을 통해 array를 순회하면서 중복 값을 찾으면 값을 반환.
  // 값이 없으면 hash_table에 키/값을 저장한다.
  for (let value of array) {
    if (hash_table[value]) {
      return value; // 첫 번째 중복 값만 반환
    } else {
      hash_table[value] = true;
    }
  }

  return null; // 중복 값이 없을 경우에 대한 처리
}
  1. 알파벳 문자를 한 글자만 제외하고 모두 포함하는 문자열을 받아 빠진 문자 하나를 반환하는 함수를 작성하라. 예를 들어, 문자열 "the quick brown box jumps over a lazy dog"는 문자 "f"를 제외한 모든 알파벳 문자를 포함한다. (단, 함수의 시간 복잡도는 O(N))
function findLetter(string) {
  const alphabet = "abcdefghijklmnopqrstuvwxyz";
  let hash_table = {};

  // 각 글자를 hash_table에 저장
  for (let value of string) {
    hash_table[value] = true;
  }

  // hash_table에 해당하는 값이 없으면 누락된 문자 반환
  for (let value of alphabet) {
    if (!hash_table[value]) return value;
  }
}
  1. 문자열에서 첫 번째 중복되지 않는 문자를 반환하는 함수를 작성하라. 예를 들어, 문자열"minimum"에 한 번만 등장하는 문자가 "n"과 "u" 두 개인데 먼저 나오는 문자인 "n"을 반환해야 한다. (단, 함수의 시간 복잡도는 O(N))
function getNonDuplicate(string) {
  let hash_table = {};

  // for of 문을 사용해서 string 각 글자에 1씩 더해 저장.
  for (let value of string) {
    if (hash_table[value]) {
      hash_table[value] += 1;
    } else {
      hash_table[value] = 1;
    }
  }

  // for in 문을 사용해서 해시 테이블에 값이 1인 key를 반환.
  for (let key in hash_table) {
    if (hash_table[key] === 1) return key;
  }
}

요약

  • 해시 테이블은 키와 값의 쌍으로 이뤄진 리스트이다.
  • 키(Key)를 통해 값(Value)를 한번에 찾을 수 있어 O(1) 시간복잡도다.
  • 해시 테이블에서 충돌(이미 인덱스에 값이 존재하는 상황)이 발생하면 분리 연결법(Separate Chaining)을 사용해서 값을 저장한다.
  • 충돌을 최소화해야 해시 테이블의 장점인 O(1)의 효율성을 유지할 수 있다.
  • 키와 값의 쌍이 아닌 배열도 해시테이블을 사용해 효율성을 높일 수 있다.
profile
sangsang
개발이 너무 좋다. 정말 잘 하고 싶다.
다음 포스트

[알고리즘과 자료구조] 스택과 큐에 대해서 알아보기

0개의 댓글

관련 채용 정보