Hash / Hash Table

Hash

• 데이터를 효율적으로 관리하기 위해 임의의 크기를 가진 데이터(key)를 고정된 크기의 데이터(value)로 변화시켜 저장하는 것
• 키에 대한 Hash 값을 사용하여 값을 저장하고 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 연괸배열
• 키에 대한 Hash 값을 구하는 과정을 Hashing 이라고 하며 이때 사용하는 알고리즘을 해시함수 라고 함
• Hash 값 자체를 index 로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠름

 

해시함수

• 키에 대한 Hash 값을 만드는 함수
• 계산이 단순하고 키값에 대해 중복이 없이 해시값을 고르게 만들어 내는 함수가 좋음
• 충돌이 일어나지 않을수록 좋음
• 나눗셈법(Division Method)과 곱셈법(Multiplication Method)이 대표적

 

---

 

Hash Table

• (Key, Value) 의 형태로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있음
• 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문에 빠른 검색속도를 제공할 수 있음
• 각각의 키값에 해시함수를 적용해 배열의 고유한 index를 생성하고 이를 활용해서 값을 저장하거나 검색하는데 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 함