해쉬테이블

해쉬 테이블은 Key,Value로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조

Key값을 통해서 Value값을 공부하면 매우매우 빠르게 동작한다.

• Key에 Value를 저장하는 데이터 구조
• Key를 통해 바로 데이터르 받아볼 수 있으므로, 검색 속도가 획기적으로 빨라짐
• 파이션 dic 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄
• 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용
• 파이썬에서는 해쉬를 별도로 구현할 필요가 없다.
• C에서 구현해보자.

기본 용어

• 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블(Hash Table) : 키값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value) or 해쉬 주소(Hash Address) : key를 해싱 함수로 연산해서 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음.ㅎ
• 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음.