Hash Table

데이터를 해시함수를 거쳐 테이블에 정렬하는 방식.

 

해시함수는 +,-,*,/,% 등등 사용됨. 해시함수로 인덱스를 구분함.

 

이런 일련의 과정을 Hasing이라고 지칭한다.

 

이런식으로 하다보면 발생하는 문제가 생기는데, 대부분의 문제가 해시충돌 현상이 발생한다.(인덱스가 겹치는 현상)

 

해시충돌값을 해결하기 위한 방법으로는 Chaining, Linear Probing, Resizing 방법이 있다.

 

1. Chaining 방법은 분리연결법? 해석은 참 거지 같다. 눈에 들어오지도 않는 어려운 용어...

 

값부분에 Linked List로 구현하는 방식이다.

 

이런식으로 저장을 해서 충돌을 피하는 방식이다. 값찾으려면 인덱스 값 타고 들어가서 Linked List의 값을 찾는 방법을 써야한다.

 

2번째는 Linear Probing, 개방주소법이라고 불리는데, 비어있는 인덱스에 값을 저장해서 충돌을 방지한다.

 

40하고 47의 인덱스값이 겹친다. 47을 비어있는 인덱스값에 일단 할당하고 나머지를 진행한다.

이렇게 충돌을 피했다.

 

이렇게 하다보면 공간이 없어지는데, 이때 Resizing을 한다.

 

크기를 두배로 늘리고, 값을 할당한 후 테이블을 정렬한다.