TIL | 1.5.목 [CS 기초지식 | 해시 테이블]

- 해시테이블

 

[해시 테이블]

• 연관 배열 구조(key - value 연관)를 이용하여 key에 value를 저장하는 자료구조

 

 

[해시테이블의 특징]

해시 테이블은 적은 자원으로 많은 데이터를 효율적으로 관리할 수 있다.

하드 디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시 값으로 매핑하면 작은 메모리로도 프로세스의 관리가 가능하다.

 

 

[해시 테이블 | 충돌 해소]

해시 충돌이란? 해시 함수가 서로 다른 두 개의 입력 값에 대해 동일한 출력 값을 내는 상황

• 충돌 해소 전략
  • 체이닝 방법 : 충돌 시 연결 리스트를 만들어 값을 할당하고 이어서 연결하는 방식
  • Open Addressing 방법 : 충돌 시 해시 테이블에서 놀고 있는 인덱스에 할당하는 방식'

 

 

 

 

[참고 링크]

https://velog.io/@jangwonyoon/%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94%EC%9D%98-%EC%B6%A9%EB%8F%8C-%ED%95%B4%EA%B2%B0%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%ED%95%A0%EA%B9%8C

해시 테이블의 충돌 해결은 어떻게 할까?