패스트캠퍼스 챌린지 04일차

---

[오늘 진도]

Part 1. 자료구조 이론

Ch 09. 자료구조 (해쉬)

- 02. 블록체인에도 쓰이는 해쉬 테이블 2

- 03. 블록체인에도 쓰이는 해쉬 테이블 3

---

오늘은 해쉬 테이블에 대해 배웠다. 강사님은 Dave Lee라는 성함답게 외국물을 드셨는지 영어 발음이 편하신 것 같지만, 나는 링크드 리스트보다 연결 리스트가 편한 것처럼 해쉬 테이블보다 해시 테이블이 더 편하다. 그러니 해시 테이블이라 하겠다. 어제 후기에도 썼던 말이라 재탕하는 것 같지만 전혀 그럴 의도가 없다는 걸 먼저 말해둔다. 부스트 코스에서 들은 지식은 파편처럼 무슨 내용인지 알겠으나 그게 두루뭉술하고 구체적인 형태가 그려지지 않았다면 이번 강의를 통해 구체적으로 그릴 수 있게 되었다. 환급 챌린지를 떠나 듣길 잘한 것 같다. 

 어제 해시 테이블의 기본적인 구조를 공부했다면 오늘은 충돌이 일어난 경우에 대해 공부했다. key값에 해시 함수를 적용해 해시 테이블에 값을 넣는 경우, 서로 다른 키와 값이나 해시함수의 결괏값이 같아 이미 있는 자리에 새로 값을 넣어야 할 수 있다. 이런 경우 충돌이라고 한다. 충돌을 피하는 방법으로 크게 두 가지가 있다. 하나는 개방 해싱/Chaining/Open Hashing이고 다른 하나는 폐쇄 해싱/Linear Probing/Close Hashing이다. 둘 다 부스트 코스 강의에서 들었으나 들으면서 `아, 그렇구먼`하고 넘어갔을 뿐 제대로 연결하지 못했다. 다시 한번 말하지만, 이 강의를 듣게 되어 다행이다. 아무튼 Chaining은 충돌이 발생한 자리에 연결 리스트를 만들어 해당 자리에 새로운 자료구조를 추가하는 것이다. 예를 들어 해시 함수의 결괏값이 4인 자료가 순서대로 사, 넷, 四이 있다면 이 세 값이 4의 자리에 연결 리스트처럼 값을 가리키는 것을 말한다. 다음으로 Linear Probing은 해시 함수 결괏값의 테이블 자리를 보니 이미 데이터가 있을 때, 그다음 자리에 값을 넣는 것이다. 그다음 자리에 데이터가 있다면 또 다음 자리를 봄으로써, 쭉 테이블을 보고 빈자리에 값을 넣는 것이다. Chaining은 새로운 메모리가 필요하지만, 한계가 없고, Linear Probing은 한계가 있는 대신 새로운 메모리가 필요하지 않다. 각각의 장단점이 있다.

 이런 자료구조를 그러니까 해시 테이블을 몇 년 내내 연구하는 사람들도 있다는데 정말 대단한 사람들이다. 덕분에 캐시 메모리도 구현하고 검색 많고 입력 삭제가 빈번한 곳에서도 잘 쓰고 있습니다. 더 힘내주세요,,, 화이팅!

---

https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.