[11일차 과제] 자료구조(해시 테이블)

1. 해시 테이블(Hash Table)이란?

• 정의
• 해시함수
• 해시테이블을 사용하는 이유
• 장단점
• 사례

2. 충돌(Collision)이 발생하는 경우 및 해결 방법

• Chaining
• Open Addressing

3. 파이썬의 dictionary와 해시 테이블의 관계

 

4. 해시 테이블 구현

 

5. 해시 충돌 예제 만들어보기

---

1. 해시테이블(HashTable)이란?

1. 해시테이블의 정의

• (Key, Value)로 데이터를 저장하는 자료구조
  ex. Python-Dictionay, Java-HashMap, JavaScript-Map객체, 데이터베이스 인덱싱, 로그인 비밀번호 저장(비밀번호를 해시값으로 변환하여 저장), 캐싱(브라우저가 URL을 키로, 페이지 데이터를 값으로 저장하여 재방문시 즉시 로딩)
  • key(키) : 값을 찾기 위한 고유 식별자. 중복값 불가능. 이 키가 해시 함수에 입력되어 데이터가 실제 저장될 메모리 위치(인덱스) 결정
  • value(값) : 키와 매핑되어 실제 저장되는 데이터. 중복값 가능. 키를 통해 해시테이블에 접근하면 최종 반환되는 결과값
• 내부적으로 배열(버킷)을 사용하여 데이터를 저장 (실제 값이 저장되는 장소를 버킷 또는 슬롯)
• 해시 테이블은 각각의  Key값에 해시함수를 적용해 배열의 고유한 인덱스를 생성하고,
  이 인덱스를 활용해 값을 저장하거나 검색

2. 해시함수

• 고유한 인덱스 값을 설정⭐
• 해시테이블에 사용되는 대표적인 해시함수
  1. Division Method : 입력값을 테이블의 크기로 나누어 계산 (주소 = 입력값 % 테이블 크기)
  2. Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용
  3. Multiplication Method : 숫자로 된 Key값 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산
     h(k) = (kAmod1) x m
  4. Univeral Hashing : 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값 생성

3. 시간 복잡도

연산	평균	최악
검색/삽입/삭제	O(1)	O(n)

 

4.해시테이블 장단점

• 장점 : 
  • 빠른 검색 속도 : 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문
  • 빠른 삽입/삭제 속도
• 단점 : 
  • 순서 보장 x
  • 메모리 많이 사용 : 빠른 검색을 위해 공간을 미리 할당
  • 해시 충돌 : 서로 다른 키가 같은 해시값을 가질 수 있음
  • 범위 검색 느림 : 10~20 사이 값 찾기 같은 연속 범위 탐색은 비효율적
• 위 같은 장단점 때문에 단건 검색에서는 최강이지만, 순서/범위가 필요하게되면 비효율적
  그래서 범위 검색이 많은 경우, 해시테이블대신 B-Tree구조(DB인덱스 등) 사용

---

2. 충돌(Collision)이 발생하는 경우 및 해결 방법

• 만약, 두 문자열을 해시 함수를 돌려 나온 결과 값이 동일하다면 어떻게 해야 할까?
• 해시 값이 충돌하는 경우 크게 2가지 방법으로 해결 가능

1. 분리 연결법(Seperate Chaining)

chaining

• 동일한 버킷의 데이터에 대해 자료구조(연결 리스트 등)를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장
  ex. Java8의 해시테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현
  ex. 만약 KeyA와 KeyB가 같은 인덱스에 할당되면, 버킷에 연결된 리스트에 두 데이터를 나란히 추가
• 장점 : 해시 테이블의 확장이 필요없고, 간단하게 구현 가능하며 손쉽게 삭제 가능
• 단점 : 데이터 수가 많아지면 동일한 버킷에 Chaining 되는 데이터가 많아지며, 그에 따라 캐시 효율성이 감소
• 성능 개선 방법 : 데이터 수가 많아져 연결 리스트가 길어지면
  1. 레드-블랙 트리로 구조를 변경하여 성능을 방어(Java등에서 채택)
  2. 동적 크기 조절 : 테이블의 적재율(Load Factor, 전체 데이터 수/버킷 수)이 일정 비율 이상 높아지면 테이블의 크기를 늘리고 해시 함수를 재구성

 

2. 개방 주소법(Open Addressing)

open addressing

• 추가적인 메모리를 사용하는 Chaining과 다르게 해시 테이블의 빈 공간을 활용
• 이를 구현하기 위해 대표적으로 3가지 방식이 존재
  1. 선형 탐사(Linear Probing) : 현재 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터 저장
  2. 제곱 탐사(Quadratic probing) : 해시 저장순서 폭을 제곱으로 저장
  3. 이중 해싱(Double Hashing Probing) : 해시된 값을 한 번 더 해싱하여 규칙성을 없앰. 한 번 더 해싱하여 새로운 주소로 할당하기 때문에 많은 연산을 하게 됨

* 간단하게 chaining은 충돌나면 같은 자리에 이어붙이고, open addressing은 충돌나면 다른 빈자리로

---

3. 파이썬의 dictionary와 해시테이블의 관계

• 파이썬의 딕셔너리는 내부적으로 해시테이블로 구현
• 충돌 해결 방식으로 개방 주소법(open addressing) 사용
• 파이썬 3.7부터 삽입 순서 보장(일반 해시테이블은 순서 미보장)
• 키는 반드시 해싱 가능한(hashable) 객체여야함

---

4. 해시 테이블 구현

• 충돌 해결 방식은 '분리 연결법'으로 구현해보자

1. class HashTable 구현

• init 생성자 : 
  • 매개변수로 버킷의 크기를 담아옴 (기본값은 10)
  • 버킷의 크기와 chaining을 사용하기 위해 빈 리스트를 함께 만듦
• _hash() :
  • 키를 받아서 버킷 인덱스를 반환하는 메서드
  • 앞에 _가 붙는 이유 : 내부에서만 사용하는 메서드라는 관례
  • hash() 내장 함수로 해시값을 구함
  • 버킷 인덱스로 변환 (기본값이 10이니 현재는 0~9값만 존재)
  • size를 크게 설정할수록:
    • 충돌 가능성 낮아짐
    • 메모리 사용 늘어남
    반대로 size가 작으면:
    • 충돌 가능성 높아짐
    • 메모리 사용 줄어남
• set() :
  • 키와 값을 받아서 저장하거나 업데이트하는 메서드
  • 1. _hash() 로 인덱스를 구한다
  • 2. 해당 버킷 리스트를 순회하며 인덱스, 키, 값을 꺼낸다
  • 3. 같은 key가 존재하면 새 값으로 교체하고 바로 종료
  • 4. 같은 key가 존재하지 않으면 해당 버킷에 (튜플 형식으로 저장)
• get() :
  • 키를 받아서 키에 해당하는 값을 조회하는 메서드
  • 1. _hash() 로 인덱스를 구한다
  • 2. 해당 버킷 리스트를 순회하며 인덱스, 키, 값을 꺼낸다
  • 3. 같은 key가 존재하면 해당 값을 리턴
  • 4. 없으면 None 리턴

# 해시테이블 구현
# 1. 클래스
class HashTable:
    def __init__(self, size = 10):
        self.size = size        # 버킷의 크기
        self.table = [[] for _ in range(self.size)]     # Chaining 사용하기 위해 빈 리스트
    
    # 키를 버킷 인덱스로 변환하는 메서드
    def _hash(self, key):       
        hash_value = hash(key)          # 1 해시값 구하기
        return hash_value % self.size   # 2 버킷 인덱스로 변환

    # 저장 및 업데이트 메서드
    def set(self, key, value):
        idx = self._hash(key)        # 1 _hash()로 인덱스를 구한다

        for i, (k, v) in enumerate(self.table[idx]):    # 2 해당 버킷 리스트를 순회하며 인덱스, 키, 값을 꺼낸다
            if k == key:                                # 3 같은 key가 존재하면 
                self.table[idx][i] = (key, value)       # 새로운 (key, value)로 교체하고 바로 종료
                return

        self.table[idx].append((key, value))    # 4 같은 key가 존재하지 않으면 해당 버킷에 (key, value) 저장

    # 키로 값 조회하는 메서드
    def get(self, key):
        idx = self._hash(key)           # 1 _hash()로 인덱스를 구한다

        for i, (k, v) in enumerate(self.table[idx]):    # 2 해당 버킷 리스트를 순회하며 인덱스, 키, 값을 꺼낸다
            if k == key:                                # 3 같은 key가 존재하면 해당 값을 리턴
                return v                                
        return None                                     # 4 없으면 None 리턴

# 2. 해시테이블 생성
ht = HashTable()

# 3. 새로운 데이터 저장
ht.set("name", "철수")
ht.set("subject", "랭체인")
ht.set("age", 25)
ht.set("blood", "A")

# 4. 데이터 조회
print(ht.get("name"))
print(ht.get("subject"))
print(ht.get("age"))
print(ht.get("blood"))

# 5. 데이터 업데이트
ht.set("name", "영희")
print(ht.get("name"))

---

5. 해시 충돌 예제 만들어보기

• 충돌이 잘 나도록 하기위해 size = 5로 실행 (인덱스가 작으면 충돌 확률 up)

ht_crush = HashTable(size = 5)

# 어떤 key에서 충돌이 발생하는지 먼저 테스트
keys = ["name", "age", "blood", "height", "weight", "school"]

# 순회돌면서 버킷 리스트의 인덱스를 출력
for key in keys:
    idx = ht_crush._hash(key)
    print(f"{key} -> 버킷[{idx}]")

# 결과
name -> 버킷[4]
age -> 버킷[1]
blood -> 버킷[2]		# 충돌
height -> 버킷[3]
weight -> 버킷[0]
school -> 버킷[2]		# 충돌

# 충돌난 blood와 school에 값을 넣고 확인
ht_crush.set("blood", "A")
ht_crush.set("school", "서울대")

# ht_crush 해시테이블의 인덱스 2에 들어있는 데이터 출력
print(ht_crush.table[2])

# key에 해당하는 값도 문제없이 출력
print(ht_crush.get("blood"))
print(ht_crush.get("school"))

# 출력 결과
[('blood', 'A'), ('school', '서울대')]
A
서울대

• 분리 연결법(open addressing)으로 충돌이 해결된 것 확인 가능
• blood와 school에 해당하는 값도 제대로 출력

---

[과제 후기]

* 해시테이블이라는 자료구조를 처음 들어보았다. 파이썬의 딕셔너리가 해시테이블을 사용한 구조라는 것을 보니 이해하는데 큰 무리는 없었다. 해시함수라는 것은 보안의 암호화를 공부하면서 봤던 것이다. 파이썬의 해시함수는 빠른 인덱스 계산을 위한 목적을 가지고 역방향으로도 가능하고 충돌도 있어도 큰 문제가 되지 않는다. 하지만 단방향 암호화의 해시는 보안 목적이고, 역방향과 충돌이 불가능하다. 결론은 이름만 같다는 것이다. 이름이 같길래 같은 건줄 알았네

 

* 해시 테이블을 구현하는 과정에서는 생성자, 해싱 과정의 메서드, 해시테이블에 값을 넣는 set, 값을 가져오는 get이 필요하고, 각각의 매개변수와 필요한 과정을 뜯어보며 작성해보았다. 충돌 예제를 만드는 것은 도저히 감이 잡히지 않아 힌트를 받는 방식으로 ai의 도움을 받았다. 지금이야 몇 안되는 데이터로 테스트를 해보았지만 체이닝 충돌 해결 방법은 메모리 효율면에서 좋지 않다는 것을 느낄 수 있었다. 다음에는 개방 주소법으로도 구현해보아야겠다.