해쉬 테이블

해쉬 테이블이란

키와 값으로 구성된 자료구조

순회로 값을 찾는 리스트 구조와 달리 키값을 해싱한 것만으로 값을 찾아낼 수 있어 효율적

 

 

 

원리

1. array형태의 버킷을 생성하고

2. 키값을 해싱하여 인덱스로 결정

3. 버킷의 인덱스에 값을 넣는다.

 

 

 

 

 

특징

1.

vector의 경우 연속된 메모리 공간이 필요하기 때문에 capacity가 늘어나면 메모리 공간을 다시 잡는다.

vector : capacity가 늘어나면 메모리 공간을 다시 잡음

hash table의 capacity는 thumb of rule에 따름 (임의 설정이 가능한지는 아직 모름)

hash table을 사용한 map 또한 해쉬 충돌이 잦을 경우 다시 메모리 공간을 잡는다. 

 

2.

키값에 따라 주소값이 정해지기 때문에 같은 키값에 다른 값을 넣을 수 없다.

 

 

 

 

 

단점 - 해쉬 충돌

해쉬 함수에 다른 키값을 넣었는데 같은 인덱스가 나온다면 해싱충돌이 일어난다. 

키-값 1대1 규칙이 깨지기 때문에 이와 같은 경우 연결리스트 자료 구조로 다른 값에 연결 시켜준다.

해쉬 버킷이 잡은 메모리 공간이 작을 경우 해싱충돌이 많이 일어나기 때문에 성능이 저하된다. 이럴 경우 해쉬테이블에서는 공간을 재할당한다.