[10주차] 해시 테이블

[ainochi-kor]

해시 테이블에 대해서 알아보기로 해요!

[hanana1253]

요약

1. 키를 사용한 저장과 탐색

• 정수 값의 효율적인 탐색을 하려면, 있을 수 있는 모든 값에 개별적으로 배열 상자를 만들기? -> 문제가 많다 (무한대로 필요한 상자, 메모리 낭비 등)
• 키는 데이터와 함께 저장되거나, 데이터로부터 유도된 단일 값으로 레코드를 식별할 때 사용된다. -> 여전히 인덱싱 문제가 있다
• 즉, 키에서 인덱스를 생성하는 함수가 필요하다: 해시 함수!

2. 해시 테이블

• 해시 테이블은 수학적인 매핑을 사용해 키 공간을 압축
• 원래의 키(raw key)를 테이블 상 위치(해시 값)로 매핑하는 해시 함수를 사용하여 큰 키 공간을 작은 영역으로 축소
• 키 k개를 b개의 상자가 있는 테이블로 매핑: 상자가 무한대로 필요하지 않고 b개만 있으면 된다. (곧 해시함수는 치역이 [0, b-1])
• 같은 상자에 둘 이상의 서로 다른 값이 매핑되는 경우? -> 해시 값 충돌
  • 해시 테이블 구조가 복잡해진다.
  • 해시 함수는 키를 서로소인 집합들로 분할하고, 같은 집합에 속한 키에 대해서만 충돌을 걱정한다.
• 해시함수는 완벽한 일대일 매핑을 보장하지 않는다.
• 해시 테이블의 크기를 늘리거나, 더 나은 해시 함수를 선택하여 충돌을 완화
• 키 공간이 상자 개수보다 크다면 충돌을 완전히 제거하는 것은 불가능
• 체이닝(chaining)
  • 각 상자 안에 추가 구조를 사용해 해시 테이블의 충돌을 처리
  • 단일 데이터(를 가리키는 포인터) 대신 연결 리스트의 머리를 가리키는 포인터 저장
  • 여전히 순회하긴 하지만 특정 해시값에 해당하는 작은 리스트만 탐색하면 되므로 효율적
• 선형 탐색 (linear probing)
  • 인접한 상자를 사용
  • 다음 상자가 차 있으면 빈 상자를 찾을 때까지 이동해서 사용
  • 장점: 최초 할당한 배열을 더 잘 활용하는 방식
  • 단점: 테이블이 가득 차면 루프 돌면서 더 많은 원소를 살펴보고, 각 원소의 키가 우리가 탐색하려는 대상의 키와 일치하지 않는데도 순회할 수도 있다.

3. 해시 함수

• 조건
  • 결정적일 것: 매번 같은 키를 같은 해시 상자에 매핑해야 한다.
  • 정해진 크기의 치역을 가질 것: 모든 키를 제한된 범위(해시 테이블에 있는 상자의 개수)로 매핑
• 숫자가 아닌 키는, 숫자 값으로 변환하는 함수를 사용
  • 각 글자의 아스키 코드를 더하기
  • 호너의 방법: 첫번째 문자로부터 이 방식을 통해 계산한 누적 합계에 어떤 상수를 곱하고 다음 문자 값 더하기
• 원소의 집합을 추적할 때 특히 유용

4. 해시 테이블이 중요한 이유

• 수학 함수를 사용해 데이터를 조직하는 새로운 방법을 제공
• 키를 축소된 범위로 매핑

느낀점

• �해시 테이블은 그래도 앞의 두 챕터보다 재미있었고 쉽게 읽었다. 예시도 풍부해서 더 좋았던 것 같다.
• 숫자 값으로 키를 변환하는 함수를 어떻게 고안해냈지? 다들 창의력 대장인 듯.
• 내일 결혼기념일 여행을 떠나야 해서 일찍 숙제를 했다. 다들 1년 전 축하해주셨던 것도 생각난다. 다시 한 번 감사합니다. (느낀 점에 TMI 남발)

[ella-yschoi]

1년 전엔 한결님을 몰라서 결혼식에 못 갔지만 (feat. 조세호)
결혼 1주년 축하드립니다 😊

[ella-yschoi]

정리

• 이번 주제는 이미 익숙한 개념이기도 하고, 내용이 길지 않아서 괜찮았네요.
• 저번 9장 공간트리는 살짝 어질했는데... ㅎㅎ 밀당하는 책이네요 하하

[yunseorim1116]

정리

• 익숙한 개념이라 술술 읽혔던것 같아요 !
• 재미도 있는 파트였습니다

[ainochi-kor]

정리

• 아는 용어들이 나와서 쉽게 읽었던 것 같습니다!

[sa02045]

정리

이전 파트보다는 읽기 수월했습니다. 해시 충돌을 처리하는 방법인 체이닝과 선형탐색을 비교할 수 있었습니다. 세부 알고리즘을 좀 더 다시 읽어봐야겠네요

• 정보를 탐색해서 빠르게 읽고 싶은 저장 용도의 경우 해시테이블이 적절
• 배열은 해당 원소의 인덱스를 알 때만 효율적이다.
  • 인덱스가 있으면 상수 시간에 조회 가능
  • 인덱스가 없으면 원소 탐색이 복잡해짐
  • 이진탐색등등
• 탐색하고자하는 목표값을 인덱스로 매핑하는 함수. 해시 테이블의 핵심
• 수학 함수를 이용하여 값의 인덱스를 계산하기 때문에 값을 배열의 상자로 매핑할 수 있음

10.1 키를 사용한 젖아과 탐색

• 정수 값의 효율적인 탐색을 위한 인덱싱 방법을 고민해보기
• 있을 수 있는 모든 값에 대한 개별 배열 상자를 유지하고, 값을 그 상자로 인덱싱하는 방법
• 단점은 모든 키의 배열을 유지하는데 비용이 많이 든다는 점.
  • 16자리 신용카드 번호를 모두 저장하려면 엄청난 메모리가 필요함
  • 더 큰 문제는 실제로 모든 상자를 사용할 가능성이 매우 작다는 것. 낭비되는 상자가 많다는 것

10.2 해시 테이블

• 해시 테이블은 수학적인 매핑을 사용해 키 공간을 압축함
• 원래의 키를 테이블상 위치로 매핑하는 해시 함수를 사용해 큰 공간을 작은 공간으로 압축함
• 해시 값의 충돌로 인해 해시 테이블 구조가 복잡해진다.
• 어떠한 해시 함수도 키를 상자로 완벽하게 일대일로 매핑해주지는 못한다.
  • 완벽한 일대일을 위해서는 엄청난 크기의 배열을 써야하고 메모리가 필요하다.
  • 큰 집합을 더 작은 집합으로 매핑하는 수학함수의 경우 충돌이 발생할 수 밖에 없다.

10.2.2 체이닝

• 해시 테이블에서 충돌을 처리하는 체이닝, 선형 탐색
• 체이닝은 추가 구조를 사용해 해시 테이블 충돌을 처리하는 방법이다.
• 키의 해시값을 계산한다. 상자가 비어있지 않으면 루프를 통해 연결 리스트의 각 원소를 스캔한다. 일치하는 키의 값을 반환한다.
• 의문: 여전히 연결 리스트의 원소들을 스캔해야한다. 해시를 사용해 직접 접근하는 능력을 잃어버렸다. 효율적인가?
  • 이 접근 방식의 장점은 모든 원소에 대해 스캔하지 않는다는 점이다. 해시값이 일치하는 경우의 원소만 스캔한다.

10.2.3 선형 탐색

• 인접한 상자를 이용해 충돌 처리하기. 이미 다른 키가 있는 상자에 데이터를 추가적으로 삽입해야한다면 바로 다음 상자로 넘어가는 방법
• 선형 탐색은 해시 테이블이 최초 할당한 배열을 활용한다는 장점. 연결 리스트 등의 탐색 추가비용이 들지 않는다는 장점
• 단점은 테이블이 점차 가득 참에 따라 루프를 많이 돌며 원소를 봐야한다는 점

10.3 해시 함수

• 키를 균일 하게 매핑하는 것이 좋음. 특정 상자에 키가 몰리면 안됨
• 해시 함수의 핵심 조건
  • 결정적일 것. 항상 같은 키를 같은 해시 상자에 매핑해야한다.
  • 정해진 크기의 치역을 가질 것: 해시 함수는 모든 키를 제한된 범위로 매핑해야한다.

10.3.1 숫자가 아닌 키 다루기

• 문자열 해싱을 하는 더 나은 방식. 호너의 방법
• 해시 함수는 훨씬 더 복잡하다. 우리가 알아야하는 것은 수학 함수를 사용해서 키 공간을 축소할 수 있다는 점이다.

10.3.2 해시 테이블 사용 예

• 원소의 집합을 추적할 때 유용함. 파이썬의 딕셔너리, 집합 자료구조를 구현할 때 해시 테이블을 사용함
• 깊이 우선 탐색, 너비 우선 탐색등에서 이미 방문한 원소의 집합을 다룰 때 해시 테이블을 사용하여 방문 원소에 대해 처리할 수 있다.

10.4 해시 테이블이 중요한 이유

• 수학 함수를 사용해 데이터를 조직하는 방법을 제공함
• 해시 테이블은 키를 축소된 범위로 매핑하는 단계가 있음
• 해시 충돌은 데이터를 해시 함수를 통해 직접 접근할 수 없다는 점을 의믜. 항목을 저장하기 위해서는 연결리스트, 선형탐색과 같은 간접수준의 참조를 추가해야함.

[thgr8ganzi]

정리

• 해시테이블 유용했습니다.

[sunhpark42]

• 해시 오랜만이었다.
• 해시 키가 중요하다는 것에 공감했다. 이전에 데이터베이스 저장 키를 날짜로 지정했다가 로드밸런싱이 잘 안되었던것이 기억나는 챕터였다.

[iborymagic]

• 해시 테이블은 빠르게 읽었읍니다
• 이전 장들이 기억이 안나서, 주중에 시간 나면 다시 읽어야겠읍니다

---

10.1 키를 사용한 저장과 탐색

• 모든 값을 개별 배열 상자로 유지하는 방식은 메모리 낭비가 심함
• 예: 16자리 신용카드 번호를 저장하려면 엄청난 공간이 필요함

10.2 해시 테이블

• 해시 함수를 사용해 키 공간을 작은 크기로 압축
• 하지만 충돌 문제 발생 → 해결 방법 필요

10.2.2 체이닝

• 충돌 시, 연결 리스트를 사용하여 같은 위치에 여러 개의 키 저장
• 같은 해시값을 가진 키만 탐색하면 되므로 탐색 비용 절감
• 하지만 연결 리스트 탐색 비용이 발생함

10.2.3 선형 탐색

• 충돌 시, 다음 빈 상자에 값을 저장하는 방식
• 배열을 재사용하여 추가적인 구조가 필요 없음
• 하지만 테이블이 꽉 차면 탐색 시간이 증가함

10.3 해시 함수

• 키를 균일하게 매핑해야 특정 위치에 데이터가 몰리는 것을 방지
• 결정적(Deterministic)이고, 범위가 정해진 함수여야 함
• 문자열 해싱 시, 호너의 방법 등을 활용

10.3.2 해시 테이블 사용 예

• 파이썬의 딕셔너리(dict), 집합(set) 등의 내부 구현
• 그래프 탐색(DFS, BFS) 시, 방문한 노드 추적에 활용

10.4 해시 테이블이 중요한 이유

• 데이터를 효율적으로 저장하고 검색하는 구조
• 해시 충돌 시, 체이닝 또는 선형 탐색 등의 충돌 해결 기법이 필요함

해시 테이블은 빠른 탐색이 가능하지만, 충돌 문제를 해결하는 방법이 중요함

[ddongule]

왜이렇게 오랜만인지 했떠니 ㅎ...... 저번주에 까먹었네요..... ㅎ......

10.1 키를 사용한 저장과 탐색

키: 데이터 레코드를 식별하는 값
반드시 정수일 필요는 없으나, 배열은 정수 인덱스를 필요로 하므로 바로 사용하기 어려움
키를 해시 함수를 통해 해시 값으로 변환한 후, 이 값을 배열의 인덱스로 사용함
이를 통해 "키 → 해시 함수 → 인덱스 변환 → 값 저장"의 과정을 수행하며, 데이터 저장 및 탐색을 빠르게 함
키를 그대로 저장하는 것이 아니라, 해시 함수를 통해 인덱스로 변환하여 빠른 탐색이 가능하도록 함

10.2 해시 테이블

해시 테이블은 키를 해시 값으로 압축하여, 제한된 크기의 배열 내에서 데이터를 저장하고 검색할 수 있게 해줌
평균적으로 삽입, 삭제, 탐색이 O(1) 시간에 이루어짐

• 충돌(Collision) 문제:
  서로 다른 키가 동일한 해시 값을 반환하는 경우가 발생할 수 있음
  이 문제는 해시 테이블의 크기와 해시 함수의 특성에 기인하며, 완전히 제거하기는 어려움

• 충돌 해결 기법:

  • 체이닝 (Chaining):
    각 배열 슬롯에 연결 리스트나 다른 동적 자료구조를 두어, 동일 해시 값을 가진 여러 데이터를 저장
    장점: 충돌이 발생한 슬롯에 대해서만 추가 자료구조를 탐색

  • 선형 탐색 (Linear Probing):
    충돌 발생 시, 현재 슬롯에서부터 순차적으로 빈 슬롯을 찾아 데이터를 저장
    단점: 테이블이 꽉 차면 여러 슬롯을 순회해야 하므로 성능이 저하될 수 있음

해시 테이블은 키를 직접 저장하지 않고, 해시 함수를 통해 변환한 인덱스를 사용하여 빠른 데이터 접근과 저장 공간 효율성을 동시에 달성

10.3 해시 함수

해시 함수는 임의의 크기의 키를 고정된 크기의 정수(해시 값)로 변환
이 정수는 해시 테이블의 슬롯(배열 인덱스)으로 사용됨

좋은 해시 함수의 조건:

• 결정적(Deterministic):
  동일한 키에 대해 항상 동일한 해시 값을 반환해야함
• 정해진 크기의 치역(Fixed Range):
  해시 값은 해시 테이블의 크기(슬롯 수) 내에 있어야 힘
• 균등 분포(Uniform Distribution):
  입력 키들이 해시 테이블 전체에 고르게 분포되어, 충돌을 최소화해야 함
  문자열 해싱 방법 – 호너 방법

[chloe-codes1]

• 중요한 자료구조라서 재밌게 읽었다
• 추가로 알아본 것
  • kafka의 해시키 생성
    • kafka는 해시키를 파티션 개수 기반 모듈러 연산으로 간단하게 생성하고 있었다
      • 해시값 % 파티션 개수
  • mongoDB 해시 샤딩
    • mongoDB의 해시 샤딩은 샤드키를 직접 사용하지 않고, 해시 함수(MD5 변형)를 사용해서 샤드 키 값을 랜덤하게 변환하여 해시된 값을 기준으로 각 샤드에 데이터를 균등하게 분배한다
    • 샤드 분포가 고르지 않는 경우에 대해 컬렉션 리샤드(샤드키 변경) 및 샤드키 세분화(접미사, 접두사 붙이기)를 지원한다고 한다