hash table (해시 테이블)

: key(키)와 value(값)을 쌍으로 가진 구조

hash function(해시 함수)를 통해 데이터를 저장, 검색할 수 있음.

저장: 키 입력 받음 → 키를 해시 함수에 넣어 인덱스 계산 → 인덱스 위치에 값 저장

검색: 키 입력 → 키에 해당하는 인덱스 계산 → 그 인덱스 위치의 값 찾음

충돌(collision) 발생 가능성 있음.

충돌이란, 다른 키가 같은 인덱스(해시 값)를 가지는 것임.

→ chaining, open addressing 등의 방법으로 해결할 수 있음.

https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg/330px-Hash_table_3_1_1_0_1_0_0_SP.svg.png

장점

검색, 삽입, 삭제가 빠름.

큰 데이터를 저장하고 관리하기 좋음.

단점

충돌이 발생하면 속도 느려짐.

메모리를 많이 사용할 수 있음.

→ 키와 값의 쌍으로 데이터를 관리할 때, 빠른 검색/삽입/삭제가 필요할 때 주로 사용됨.