데크 deque
- 양쪽에서 삽입과 삭제가 모두 가능한 자료 구조
- deque: Doubly-ended Queue
- Stack과 Queue를 합친 상태
- 데크의 기본 구조는 양방향에서 삽입&삭제 가능한 구조
- 입력 제한 데크(Scroll): 한쪽의 입력을 제한한 데크
- 출력 제한 데크(Shelf): 한쪽의 출력을 제한한 데크
해시테이블(=해시맵, 해시표)
- 키(key), 값(value)을 대응시켜 저장하는 데이터 구조
- 키를 통해 해당 데이터에 빠르게 접근 가능
- 해싱: 키를 특정 계산식에 넣어 나온 결과를 사용하여 값에 접근하는 과정
해시테이블 구조
- 키: 해시 테이블 접근을 위한 입력 값
- 해시 함수: 키를 해시 값으로 매핑하는 연산
- 해시 값: 해시 테이블의 인덱스
- 해시 테이블: 키-값을 연관시켜 저장하는 데이터 구조
해시 충돌
- 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우
- 서로 다른 키의 해시 함수를통한 해시 값이 동일한 경우
- 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있음
개방 주소법(open address)
- 충돌시 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장
- hash와 value가 1:1 관계유지
- 비어 있는 공간 탐색 방법에 따라 분류:선형탐사법, 제곱 탐사법, 이중 해싱
선형 탐사법(linear probing)
- 빈 공간을 순차적으로 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 순서대로 탐사
- 일차 군집화 문제 발생
- 반복된 충돌 발생 시 해당 지점 주변에 데이터가 몰리는 경우 발생
제곱 탐사법(quadratic probing)
- 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법
- 충돌 발생 지점부터 이후의 빈 공간을 n제곱 간격으로 탐사
- 일차 군집화 문제 일부 보완
- 이차 군집화 문제 발생 가능성
이중 해싱(double hashing)
- 해싱 함수를 이중으로 사용
- 해시 함수1: 최초 해시를 구할 때 사용
- 해시 함수2: 충돌 발생 시 탐사 이동 간격을 구할 때 사용
- 선형 탐사, 제곱 탐사에 비해 데이터가 골고루 분포됨
분리 연결법(seperate chaining)
- 해시 테이블을연결 리스트로구성
- 충돌 발생 시 테이블내의 다른 위치를 탐색하는 것이 아닌 연결 리스트를 이용하여 해당 테이블에 데이터를연결
'오공완' 카테고리의 다른 글
자바스크립트: 문서 객체 모델(DOM) (0) | 2024.02.20 |
---|---|
스프링 부트3 시작하기 (0) | 2024.02.05 |
231120 오공완 (0) | 2023.11.21 |
231115 오공완 (0) | 2023.11.16 |
231105 오공완 (0) | 2023.11.05 |