[자료구조] Hash Table

Hash Table이란

 해쉬테이블은 데이터를 저장하고 검색하기 위한 자료구조입니다. 효율적인 탐색(빠른검색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. 해시 테이블은 효율적인 데이터 접근을 위해 해시 함수(Hash Function)를 사용하여, key 값으로 해시 값으로 변환하고, 이 해시 값을 인덱스로 사용하여 데이터를 저장하고 검색합니다. 데이터의 삽입, 검색, 삭제 등의 연산의 시간복잡도는 평균적으로 O(1)에 수행할 수 있습니다.실무에서도 많이 활용되는 자료구조로써 개발자라면 꼭 알아두는 것이 좋습니다.

 

Collision(충돌)

 Collision이란 서로 다른 key 값의 해시 값이 똑같아서 발생하는 문제입니다. Collision이 최대한 적게 발생 하도록 HashFunction을 설계해야합니다. 어쩔수 없이 발생한 경우 Sperate Chaining또는 Open Addressing등의 방법을 사용하여 해결합니다.