6. 해시 테이블(Hash Table)

1. 해시 테이블(Hash Table)

데이터 관리 및 검색을 효율적으로 수행하기 위해 사용되는 기술이다.

해시는 주로 해시 테이블이라는 데이터 구조와 결합하여 사용된다. 

 

1-1. 해시 함수

임의의 길이를 가진 데이터(키)를 고정된 데이터로 매핑한다. 매핑된 값은 해시 값 또는 해시 코드라 부르며, 해시 테이블 내에서 해당 데이터의 위치(인덱스)를 결정하는 데 사용된다.

 

1-1-1. 해시 테이블 작동 원리

1. 데이터 저장 : 키를 해시 함수에 입력하여 해시 값을 계산한다. 해시 값은 해시 테이블 내의 인덱스로 사용되어 해당 인덱스에 값이 저장된다.

2. 데이터 검색 : 검색하려는 키를 해시 함수에 입력하여 해시 값을 계산한다. 이 값은 해시 테이블에서 해당 데이터가 저장된 위치를 가리키므로 효율적인 검색이 가능하다.

 

1-1-2. 해시 충돌

다른 키들이 같은 해시 값을 가지게 되는 상황이다. 이는 해시 테이블의 효율성을 저하시키며 해결 기법이 필요하다.

 

1) 분리 연결법(Separate Chaining)

 * 각 해시 버킷에 대해 연결 리스트를 사용한다.

 * 충돌이 발생하면, 해당 버킷의 리스트에 새 항목을 추가한다.

 * 리스트를 탐색하여 필요한 항목을 찾는다.

분리 연결법(Separate Chaining)

 

2) 개방 주소법(Open Addressing)

 * 모든 항목을 해시 테이블 내에 직접 저장한다.

 * 충돌이 발생하면, 다른 버킷을 탐색하여 빈 공간을 찾는다.

 * 선형 조사, 이차 조사, 이중 해싱 등 다양한 조사 방법이 있다.

개방 주소법(Open Addressing)

해시 테이블의 장점

• 빠른 데이터 접근: 평균적으로 상수 시간(O(1))에 데이터를 검색, 저장, 삭제할 수 있다.
• 데이터 관리 효율성: 키를 통해 직접 데이터에 접근할 수 있어서, 복잡한 검색 알고리즘이 필요 없다.

해시 테이블의 단점

• 충돌 관리 필요: 효율적인 충돌 해결 기법이 필요하다.
• 메모리 사용: 키의 분포에 따라 해시 테이블의 크기가 커질 수 있다.

1-2. 해시 테이블 구현 설명

1. 클래스 정의

HashTable클래스는 해시 테이블의 크기(size)와 해당 크기의 빈 리스트(table)로 초기화된다.

2. 해시 함수

get_hash메서드는 주어진 키를 해시 함수에 넣어 해시 값을 계산하고 테이블 크기로 나눈 나머지를 반환한다.

값은 테이블에서 해당 키에 대한 인덱스로 사용된다.

3. 데이터 저장 (set 메서드)

 - 주어진 키에 대한 해시 인덱스를 계산한다.

 - 해당 인덱스에 아무 값도 없으면 새로운 리스트를 할당한다.

 - 키와 값을 튜플 형태로 해당 인덱스의 리스트에 추가한다.

4. 데이터 검색 (get 메서드)

 - 주어진 키에 대한 해시 인덱스를 계산한다.

 - 해당 인덱스의 리스트를 순회하면서, 키와 일치하는 요소를 찾으면 그 값을 반환한다.

 - 키가 존재하지 않으면 None를 반환한다.

해시 테이블 생성 및 사용 예