1. javaMap에 관해서
설명
HashMap
- [[해시Table]]로 구성되어 있다.
- 키-쌍 구조로 되었있다.
- 정렬되지 않는다.
Tree Map
- 이진 검색 트리(Red-Black Tree)를 사용한다.
- 키 기준으로 정렬이 수행된다.
LinkedHashMap
- 해시 Table을 이중 연결 리스트로 사용한다.
- 입력 순서를 보장한다.
ConcurrentHashMap
- 해시 Table을 사용한다. (다중 [[세그먼트]]를 이용해서 동시성을 제어한다.)
- 높은 동시성을 위해 설계되었다.
- 정렬되지 않는다.
2. 세그먼트란?
데이터를 여러개의 세그먼트로 저장한다.
각 세그먼트는 독립적인 작은 해쉬Table처럼 작용한다.
동시 접근을 위해서 [[lock]]사용시 독립적으로 락이 걸리게 된다. 따라서 다른 세그먼트에 영향을 끼치지 않는다.
3. 해쉬 Table
키-값 쌍의 저장 검색 자료구조이다.
해쉬함수를 이용해서 키를 해쉬값으로 반환한다.
해시값을 이용해서 Data array특정 위치에 저장한다.
설명
해시 Table 구성 요소
해시함수
- 키를 해시로 반환한다.
- 좋은 해시함수는 서로 다른 키를 고르게 분포해서 충돌을 최소하하는 것이다.
버킷(Bucket)
- 해시값에 대응되는 배열의 각 요소를 의미한다.
- 1개 이상의 키-쌍 value를 가질 수 있다.
충돌(collision)
서로 다른 두 키가 동일해시를 지정해서 발생하는 문제이다.
해쉬 테이블 동작원리
삽입, 삭제, 검색의 과정
1. 키를 해시함수에 입력해 해시값을 계산한다.
2. 해시값을 배열 idx로 사용한다. 해당하는 버킷에 접근한다.
3. 버킷에 키-쌍을 삽입, 삭제, 검색을 수행한다.
4. lock이란?
멀티스레드 환경에서 동시접근 데이터 불일치 문제를 해결하는 기법이다.
락걸린 자원은 한 번에 하나의 해시 스레드에 접근한다.
설명
락 걸기(Acquire lock):
자원 사용을 위해서 락을 거는 과정이다.
작원에 락이 걸리면 다른 쓰레드는 대기해야한다.
락 풀기
자원 사용이 끝난 후 락을 해제한다.
다른 쓰레드가 접근 가능하게 한다.
5. 페어프로그래밍
오늘 처음으로 페어프로그래밍을 해봤다. 내가 얼마나 부족했는지 잘 알수 있었던 시간 ㅋ ㅠ ㅋ ㅠ
6. 알고리즘 풀 때의 순서
설명
1. 문제해석하기
- 제한사항 표시해놓기
- 보면서 시간복잡도 계산해보기
2. 문제의 목표 적기
문제에서 궁극적으로 추출해야하는 값 적어놓기
해당 목표를 위해서 나아갈 세부사항을 적어야 함
3. 자료구조 정하기, 손으로 풀면서 필요한 변수 생각하기
본격적으로 슈도코드를 짜기전에 사용해야할 자료구조를 정한다.
필요한 변수 리스트들을 뽑아낸다.
이 과정에서 변수가 추가될 수도 필요가 없다고 판단되면 삭제될 수도 있다.
중요한건 코드가 아닌 머리로 문제를 풀어보면서 사용해야할 자료구조, 변수에 대해서 생각해야한다.
4. 슈도코드 써가면서 문제의 로직을 완성해나가기
큰 틀에서 작은틀로 줄여가면서 문제를 풀어보기
중간중간 결과는 출력문을 이용해서 확인한다.
참고
내 머릿통
REVIEW
자바로도 문제를 풀어보게 되었다...
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
