자료구조 Hash Table

 1. 해시 구조

• Hash Table : Key에 데이터 Value를 저장하는 구조
• Key를 통해 바로 데이터를 받아온 수 있으므로, 속도가 획기적으로 빠름
• Python Dictionary Type이 Hash Table의  ex : Key를 가지고 바로 Data Value를 꺼냄
• 보통 Array로 미리 Hash Table Size만큼 생성 후에 사용(공간과 탐색 시간을 맞바꾸는 기법)
• 단, Python에서 Hash를 별도로 구현할 이유가 없음 => Dictionary Type을 사용하면 됨

2. 알아둘 용어

• Hash : 임의 값을 고정 길이로 변환하는 것
• Hash Table : Key Value의 연산에 의해 직접 접근이 가능한 데이터 구조
• Hashing Function : Key에 대해 산술 연산을 이용해 Data 위치를 찾을 수 있는 함수
• Hash Value or Hash Address : Key를 Hashing Function으로 연산하여, Hash 값을 알아내고, 이를 기반으로 Hash Table에서 해당 Key에 대한 Data를 찾을 수 있음
• Slot : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 Data에 의해 Key를 추출할 수 있는 별도 Function도 존재할 수 있음

3.1 Hash Table 만들기

3.2 초간단 Hash Function 만들기