[2019 동계 모각코] 6차시 - 결과

해시테이블

 

---

1. 자료구조 두가지 접근 패턴

1) 순차접근

: 연결리스트에 의해서 제공된다.

: 한쪽 끝에서 시작해 각 원소를 하나씩 살펴보면서 목표에 도달하거나 다른 끝에 도달할 때까지 탐색을 진행한다.

2) 직접접근

: 배열에 의해서 제공된다.

: 인덱스 i를 이용해서 직접 a[i]원소를 찾는다.

: 하지만 원소의 인덱스에 대해서 알고있어야한다.

​

2. 해시테이블

원소의 인덱스에 대해 사전지식없이 직접 접근할 수 있게한다.

원소의 내용으로부터 원소의 인덱스를 계산하는 해시함수를 이용한다

해시(hash) : 원소들이 아무런 순서없이 마구 뒤섞여 있다는 의미

 

3. 개방주소법

해당원소가 해시값에 의해 인덱스된 슬롯에 항상 배치되지않고 테이블의 임의에 장소에서 끝날수 있다.

1) 선형조사

: 충돌 - 해당 키의 버킷에 이미 다른 키가 있을 경우

: 충돌했을 경우에는 인덱스를 1 증가하여 저장한다.

: 삭제할 경우에는 null로 해버리면 값을 제대로 찾을 수 없기 때문에 원래 값이 있었는데 삭제되었다는 것을 나타내기위해 Nil로 표시한다.

2) 재해싱

: 테이블이 포화상태이기 전에 더 큰 배열을 사용하여 재구축한다.

: 배열을 만들때는 Nil은 자료가 없는 것으로 판단하여 재구축한다.

3) 제곱조사

: 선형조사의 문제점인 충돌이 여러번 일어나는 것을 보완한 방법이다

: 선형조사에서 1씩 증가하는 것 대신 더 큰 폭으로 증가시켜 충돌을 해결한다.- 제곱

: 제곱조사는 선형조사의 충돌횟수를 반으로 줄이지만 2차집중이 발생한다.

: 2차 집중 - 동일한 값으로 해시되는 2개의 다른 키가 동일한 조사순서를 가지게 되는 것

​

3. 폐쇠주소법

1) 이중해싱

: 조사순서를 결정해주는 독립적인 해시함수를 사용한다

: 제곱조사처럼 조사순서를 넓게 확대해서 집중을 피한다.

 

---

느낀점

해시테이블의 조사방법이 여러개여서 각각 장단점을 알고 잘 구분하는게 중요하다는 생각이 들었다. 그리고 조사방법들이 이전의 조사방법을 보완하여 나왔기 때문에 그 관계를 잘 알아야겠다고 느꼈다. 목표로 했던 코드를 직접짜는 것까지는 하지 못했지만 모각코 시간동안 각각 조사방법에 해당하는 코드를 이해 했기 때문에 이후에 직접 코드를 작성해봐야겠다.

​