해시테이블 이해하기

해시테이블이란?

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.
  • 원래의 데이터 값 = Key
  • 매핑 이후의 데이터 값 = Hash Data
  • 매핑 과정 = Hashing
  • 데이터가 저장되는 곳 = Bucket
• Key 값에 Value를 저장하는 데이터 구조이며, key값을 통해 데이터 접근.

해시테이블 장점

• 데이터 액세스(삽입, 삭제, 탐색)시 O(1)을 지향함. 상수 시간에 접근 가능.

• 색인(Index)를 사용해 모든 데이터를 살피지 않고 빠른 검색 속도를 가지고 있음.

• 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있음.

  (하드디스크나 클라우드에 존재하는 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기위 캐쉬 메모리로도 프로세스를 관리할 수 있음.)

해싱 충돌(Collision)

해쉬함수는 해쉬값의 개수보다 많은 키값을 해쉬로 변환하기 때문에 해쉬함수가 서로 다른 두 키에 대해 동일한 해시값으로 변환해 충돌을 일으킴

충돌 해결 방법

1. Direct-Address Table

2. Chaining

3. Open Addressing

4. Probing

---