Data structures (with python) - 7. Hash Table

Data structures (with python) - 7. Hash Table

 

💡 Hash Table, Map, HashMap, Dictionary or Associative are all the names of the same data structure. It is one of the most commonly used data structures.

해시 테이블, 맵, 해시맵, 사전 또는 연관 데이터 구조는 모두 같은 데이터 구조의 이름입니다. 가장 일반적으로 사용되는 데이터 구조 중 하나입니다.

 

위키피디아

 

해쉬 테이블(Hash Table)은 키(Key)를 값(Value)에 연결하여, 하나의 키가 0 또는 1개의 값과 연관될 수 있는 구조 입니다.

이런 구조는 데이터의 저장, 검색, 삭제를 매우 빠르게 수행할 수 있도록 해준다.

 

해시 테이블의 핵심 요소는 해시 함수(Hash Function)입니다. 해시 함수는 임의의 길이의 데이터를 받아서 고정된 길이의 데이터로 반환합니다. 이를 통해 키를 해시 테이블의 인덱스로 변환하고, 해당 인덱스에 값을 저장하거나 조회 합니다.

 

In Python

 

Python 에서는 딕셔너리(Dictionary)를 사용하여 해시 테이블을 구현할 수 있습니다.

딕셔너리는 키-값 쌍을 저장하는 데이터 구조로, 내부적으로는 해시 테이블을 사용하여 데이터를 관리합니다.

 

# 딕셔너리 생성
hash_table = {}

# 값 추가
hash_table['apple'] = '사과'
hash_table['banana'] = '바나나'
hash_table['orange'] = '오렌지'

# 값 조회
print(hash_table['apple'])  # '사과' 출력
print(hash_table['banana'])  # '바나나' 출력

# 값 변경
hash_table['apple'] = '애플'
print(hash_table['apple'])  # '애플' 출력

# 값 삭제
del hash_table['orange']
print(hash_table)  # {'apple': '애플', 'banana': '바나나'} 출력

 

평균적으로 O(1)의 시간 복잡도르 가진다.

즉, 해시 테이블의 크기와 상관없이 거으 ㅣ일정한 시간 내에 수행 될 수 있습니다.

이것이, 해시 테이블이 많은 양의 데이터를 효율 관리할 수 있는 이유 중 하나입니다.

 

하지만 해시테이블에는 

"해시 충돌" 이라는 문제가 있습니다.

이는 서로 다른 키가 같은 해시 값을 가질 때 발생합니다.

이는 서로 다른 키가 같은 해시 값을 가질 때 발생하는데, 이를 해결하기 위한 여러 가지 방법(오픈 해싱, 체이닝 등) 이 있습니다.

다행히도 Python의 딕셔너리는 내부적으로 이러한 해시 충돌을 관리해주므로 사용자가 따로 처리할 필요는 없다.

 

(appendix

java 의 HashMap, JavaScript의 객체, Ruby의 해시 등도 내부적으로 해시 테이블을 사용하고, 대부분 해시 충돌을 자동으로 처리해준다.

C++의 std::unordered_map 이나 Java의 HashMap 처럼 해시 충돌을 처리하는데 커스터마이징을 유저가 할수 있다.

더 낮은 수준의 언어( 임베디드 시스템, 커스텀 하드웨어 등등) 에서는 직접 해시 함수를 선택하고 충돌을 처리하는 로직을 작성해야 한다.)