[자료구조] 선형 자료구조 - 1. 랜덤 접근 가능

✅ 자료구조 : 데이터를 저장하는 방식

✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조

랜덤 접근 가능?

모든 자료에 O(1)의 시작복잡도로 접근이 보장되는 자료구조들

1. 배열

배열(array) : 같은 타입의 변수들로 이루어진 유한 집합

배열 요소(element) : 배열을 구성하는 각각의 값

인덱스(index) : 배열의 위치를 가리키는 숫자. 0에서 시작

1차원 배열, 2차원 배열 등이 있음

배열이 차지하는 메모리의 크기 = 배열의 길이 X sizeof(타입);

int[] array1; //배열 선언
int[] array2 = new int[10]; //heap 메모리에 할당
int[] array3 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //선언과 동시에 초기화

2. 해시

해시(hash) : 해시 함수로 구현.

해시함수(hash function) : 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다.

종류 : 해시테이블, 해시셋, 블룸 필터

예시 : 파이썬의 해시는 딕셔너리이다. 

O(1)을 보장하지 않는 예외가 있다.