23.03.16

2023. 03. 16 목요일

 

- 해시 테이블이란? 해시 테이블의 구조? 해싱이란?

: 키, 값을 대응시켜 저장하는 데이터 구조. 키를 통해 데이터에 빠르게 접근 가능.

 

구조는 키, 해시값 외에 해시 함수와 해시 테이블로 구성되어 있다.

해시 테이블은 해시값을 저장하는 메모리고, 보통 해시값은 키의 값을 해시 함수를 통하여 변형시켜 정하는데, 해시 함수는 개발자의 역량과 목적에 따른 것이며 좋은 해시 함수란 겹침을 최소화하는 해시값을 만드는 함수이다.

 

해싱이란 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정.

 

 

- 해시 충돌이란 무엇이며 해시 충돌 해결 방법 2가지? 설명?

: 다른 키가 해시 함수를 통해 같은 값을 내어 같은 주소의 테이블에 접근하는 것을 해시 충돌이라 한다. 이미 저장된 값이 있는 주소에 접근하여 데이터를 바꿔버리는 것.

 

개방 주소법 (Open Address)

// 충돌 시 테이블의 비어 있는 공간의 hash를 찾아 데이터를 저장.

이렇게 되면 키와 값이 1:1 관계가 유지가 된다.

선형 탐사법, 제곱 탐사법, 이중 해싱이 있다.

 

1-1. 선형 탐사법 (Linear Probing)

// 충돌 발생 지점 이후의 빈 공간을 순차적으로 탐사한다.

이는 반복된 충돌 시에 해당 지점 주변에 데이터가 몰리는 ‘일차 군집화 문제’를 발생시킨다.

(메모리에 골고루 분포가 안 됨.)

 

1-2. 제곱 탐사법 (Quadratic Probing)

// 선형 탐사법을 보완한 방법. 빈 공간을 탐색하는 건 맞지만, 충돌 지점에서 n의 제곱만큼 이동하여 빈 공간을 탐사한다. 예를 들어 n이 2라면, 처음 충돌이 일어났을 때 2^0인 1칸 후를 찾아보고, 그곳도 차 있다면 다시 그곳에서 2^1인 2칸 후, 다시 2^2인 4칸 후..를 탐색하는 방법이다.

하지만 다시 한번 제곱된 위치들에서 군집화가 일어나는 ‘이차 군집화 문제’의 우려가 있다.

 

1-3. 이중 해싱 (Double Hashing)

// 해시 함수를 두 개 사용. 하나는 원래 기능의 해시 함수와, 다른 하나는 충돌이 발생했을 때 그 값을 이용하여 또 해싱하는 함수.

앞선 두 방법보다 데이터가 골고루 분포된다.

 

2. 분리 연결법 (Seperatie Chaining)

// 해시 테이블을 연결 리스트로 구현하여, 충돌 발생 시 다른 곳을 찾는 것이 아닌 연결 리스트로 해당 테이블에 데이터를 연결한다.

다만 연결이 되어 있다 보니, 원하는 값을 찾으려면 시간이 더 걸림.

 

 

- 제너릭과 Obj 형태 리턴과 매개변수를 만드는 것의 차이는?

: Obj는 모든 형태의 클래스를 받을 순 있지만, 해당 객체를 꺼내올 때 매번 형변환을 시켜주어야 한다. 이런 번거로움을 해결하기 위함.

 

 

- 스프링에서 웰컴 페이지를 컨테이너로 만드는 방법? 정적 파일로 만드는 것과 차이점?

: container 내부의 controller에서 @Controller를 선언하고, @GetMapping(“/”) 어노테이션 설정 후 문자열을 반환하는 함수를 만들면, 해당 문자열 동일 파일명의 파일을 templates에서 실행한다. / 문자는 아무것도 없다는 뜻으로, url에서 첫 화면을 의미한다.

 

해당 방법은 정적 파일보다 실행 우선순위가 있으며, 스프링은 먼저 톰캣을 지나 스프링 컨테이너에서 해당 관련 컨트롤러가 없다면 그제서야 resources 내부의 static/동일 파일명을 실행하게 된다.

 

 

- cmd에서 현재 폴더의 상위 폴더로 가는 명령어?

: cd ..

 

 

- git에서 파일을 작성하고 add, 복사하는 과정까지 git에서 일어나는 일은?

: vim f1.txt처럼 파일을 만드는 과정에선 아무런 일도 일어나지 않지만,

git add f1.txt하는 순간 index라는 폴더에 해당 파일이 저장된 주소와 파일명이 적히고,

그 주소를 누르면 object라는 폴더에 파일의 내용이 적힌다. (객체, object) 이 주소는 내용이 같으면 컴퓨터가 다르건, 위치가 다르건 항상 같은 주소를 가리킨다.

 

만약 cp f1.txt f3.txt의 명령어로 f3의 파일으로 f1을 복사해서 넣으면 index가 두 파일을 서로 다르게 가리키지 않고, 같은 주소로 가리킨다. 즉, git은 파일명이 달라도 내용이 같다면 같은 객체를 가리킨다. 이는 git의 어마어마한 중복을 제거하는 메커니즘을 설명한다.