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

 ✍🏻 누자알 앞부분은 기본 내용이고, 다시 공부할 필요가 없다고 생각했다. 그래서 정리에 조금 소홀함이 있었다. 그러나 최근 쳤던 코딩 테스트에서 CS 지식 중 선택 정렬과 버블 정렬에 대해 물어보는 문제가 나왔다. 와! 마침 누자알 4장과 5장이 버블 정렬과 선택 정렬에 대해 자세하게 설명하고 있어서 해당 문제를 맞출 수 있었다. 역시 공부는 기본이 중요하다는 것을 다시 깨달았다. 기록하지 않으면 까먹을 것 같아서 느슨해지지 말자는 다짐으로 여기 기록한다.

---

• 배열이 정렬되어 있지 않다면 컴퓨터는 선형 검색을 해야 하므로 특정 값이 배열 내에 존재하는지 검색하기 위해 O(N)의 수행 단계가 필요하다.
• 정렬된 배열이라면 컴퓨터가 이진 검색을 수행할 수 있으므로 O(log N)의 수행 단계가 필요하다.
• 그러나 사실 더 좋아질 수 있다.
• 데이터를 O(1)만에 찾아낼 수 있는 해시 테이블이라는 특수한 자료구조를 알아본다.
• 그리고 해시 테이블을 어디에 사용하면 좋을지에 대해 알아본다.

1. 해시 테이블

• 빠른 읽기
• 해시 테이블은 다양한 프로그래밍 언어에서 서로 다른 이름으로 불린다.
• 해시, 맵, 해시 맵, 딕셔너리, 연관 배열 등등…
• 해시 테이블의 값 룩업은 딱 한 단계만 걸린다. 즉, 평균 효율성이 O(1)이다.

2. 해시 함수로 해싱

• 문자를 숫자로 변환하는 과정을 해싱(Hashing)이라고 부른다.
• 또한, 글자를 특정 숫자로 변환하는 데 사용한 코드를 해시 함수(Hash function)이라고 부른다.
• 해시 함수가 유효하기 위해서는 딱 한 가지 기준을 충족해야 한다. 해시 함수는 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자로 변환해야 한다.
• 즉 난수, 현재 시간을 계산에 넣어 사용하는 해시 함수는 유효하지 않다.

4. 해시 테이블 룩업

• 해시 테이블에서 항목을 룩업할 때는 키를 사용해 연관된 값을 찾는다.
• 컴퓨터는 간단히 두 단계를 실행한다.
  1. 룩업하는 키를 해싱한다.
  2. 해싱 결과에 해당하는 셀을 찾아가서 저장된 값을 반환한다.
• 해시 테이블에서 각 값의 위치는 키로 결정된다.
• 즉 키 자체를 해싱해 키와 연관된 값이 놓여야 하는 인덱스를 계산한다.
• 키가 값의 위치를 결정하므로 이 원리를 사용하면 룩업이 아주 쉬워진다.

4.1 단방향(One - directional) 룩업

• 해시 테이블에서 한 단계만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하다.
• 즉, 키를 모른 채 값을 찾으려면 해시 테이블 내 모든 키/값 쌍을 검색하는 수밖에 없고 이는 O(N)이다.
• 같은 원리로 키를 사용해 값을 찾을 때만 O(1) 룩업이 가능하다.
• 거꾸로 값을 이용해 연관된 키를 찾을 때는 해시 테이블의 빠른 룩업 기능을 활용할 수 없다.
• 값으로는 키의 위치를 알아내지 못하니 전부 훑는 것 외에는 키를 찾을 방법이 없다.
• 그렇다면 키는 어디에 저장될까?
• 언어에 따라 다르지만 어떤 언어는 값 바로 옆에 키를 저장한다.
• 대부분의 언어는 이미 존재하는 키에 키/값 쌍을 저장하려 하면 키는 그대로 두고 기존 값만 덮어쓴다.

5. 충돌 해결

• 해시 테이블은 정말 근사하지만 문제도 있다.
• 이미 채워진 셀에 데이터를 추가하는 것을 충돌(collision)이라고 부른다.
• 충돌을 해결하는 고전적인 방법 중 하나는 분리 연결법(separate chaining)이다.
  • 충돌이 발생했을 때 셀에 하나의 값을 넣는 대신 배열로의 참조를 넣는 방법이다.
• 컴퓨터가 키 해싱을 통해 확인한 셀이 배열을 참조할 경우 다수의 값이 들어 있는 배열을 선형 검색해야 하므로 검색 단계가 더 걸린다.
• 만약 모든 데이터가 해시 테이블의 한 셀에 들어가게 된다면 해시 테이블은 배열보다 나을 게 없다.
• 따라서 최악의 경우 해시 테이블 룩업 성능은 사실상 O(N)이다.
• 그렇기 때문에 해시 테이블에 충돌이 거의 없도록, O(N)이 아닌 O(1) 시간 내에 일반적으로 룩업을 수행하도록 디자인해야 한다.

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

• 궁극적으로 해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.
  1. 해시 테이블에 얼마나 많은 데이터를 저장하는가
  2. 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
  3. 어떤 해시 함수를 사용하는가
• 해시 함수가 왜 효율성을 좌우하는지 알아보자.
  • 예를 들어, 해시 테이블이 사용 가능한 셀이 20개가 있다고 가정하자.
  • 사용하는 해시 함수는 0부터 9까지의 숫자를 반환한다면, 나머지 10개의 셀은 사용되지 않는다.
• 즉, 좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수다.
• 데이터를 넓게 퍼뜨릴수록 충돌이 적다.

6.1 훌륭한 충돌 조정

• 충돌 횟수가 줄어들수록 해시 테이블의 효율성이 높아진다.
• 이론상 충돌을 피하는 최선의 방법은 해시 테이블에 많은 셀을 두는 것이다.
• 하지만 충돌을 피하는 것 외에도 메모리를 많이 잡아먹지 않도록 균형을 맞춰야 한다.
• 좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.
• 충돌 조정을 위해 컴퓨터 과학자들은 다음과 같은 경험에 기반한 규칙을 세웠다.
• 해시 테이블에 저장된 데이터와 해시 테이블의 셀 간의 비율을 부하율(load factor)이라고 부르는데, 이상적인 부하율은 0.7이다.
• 해시 테이블 내부는 대부분 사용자가 쓰고 있는 컴퓨터 언어가 관리한다.
• 컴퓨터 언어는 해시 테이블의 크기, 해시 함수의 종류, 확장 시기를 결정한다.

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

• 해시 테이블은 쌍으로 된 데이터와 잘 맞지만 쌍이 아닌 데이터라도 코드를 빠르게 만들 때 쓰일 수 있다.
• 예를 들어 다음과 같이 정렬되지 않은 배열이 있다고 하자.
• array = [ 61, 30, 90, 11, 54, 38, 72 ]
• 이 배열 내에서 특정 수를 찾기 위해서는 N단계의 선형 검색을 수행해야 한다.
• 그러나 이 배열의 원소를 키로 하는 해시 테이블을 다음과 같이 만들면
• map = (61, true), (30, true), (90, true), (11, true), (54, true), (38, true), (72, true) map[61] = true
• 한 단계만에 숫자 61을 룩업할 수 있다.
• 즉, 배열을 해시 테이블로 변환하면 O(N) 검색이 O(1) 검색으로 바뀐다.
• 해시 테이블을 인덱스로 사용하는 이 기법은 배열을 여러 번 검색해야 하는 알고리즘에 자주 쓰인다.
• 알고리즘에서 배열의 값을 계속 검색해야 한다면 매 검색에만 최대 N단계씩 걸리기 때문이다.
• 키로 해시 테이블을 룩업해서 어떤 임의의 값(초기화된 값)을 받는다면 그 키가 해시 테이블에 존재한다는 뜻이다.

9. 마무리

• 해시 테이블의 O(1) 읽기와 삽입은 쉽게 따라잡을 수 없는 자료구조다.
• 배열과 해시 테이블을 통해 효율성과 속도를 중심으로 자료구조를 분석해 보았다.
• 그러나 속도 외의 장점을 제공하는 자료구조도 있다.
• 다음 장에서는 코드의 간결성과 유지보수성을 향상시킬 수 있는 두 자료구조를 알아본다.