배열과 리스트
•
장점
◦
논리적 순서와 물리적 순서가 일치
◦
순서가 존재하여 특정 원소에 바로 접근이 가능
•
단점
◦
삽입이나 삭제 연산 시에 순서유지를 위한 재배치가 일어나기 때문에 오버헤드가 발생하여 큰 규모의 배열일 경우, 성능상 이슈가 발생할 수 있다.
arraylist와 가변 크기 배열
•
특정 언어에서는 배열의 크기를 동적으로 변화시킬 수 있다. 하지만 자바같은 경우는 그 크기가 정해져있기 떄문에 배열을 만들 때, 아예 크기를 지정해주어야한다.
•
그래서 자바에서는 보통 array list 라는 리스트를 쓰는데, 이 리스트의 경우에도 배열이 꽉찬 경우 요소를 추가할 때에는 배열의 크기를 현재 크기의 2배만큼 큰 새로운 배열을 만든 다음에, 기존 배열 요소를 새로운 배열에 복사하는 식이다. 이 경우에는 O(N)의 시간복잡도가 소요된다. 하지만 이경우가 그렇게 많지는 않기 때문에, 상환입력시간을 계산한다면 여전히 O(1)의 시간복잡도를 가지게 된다.
•
상환입력시간은 왜 O(1)이지?
◦
크기가 N인 배열을 생각해볼 때, 이 배열의 크기를 늘릴 떄마다 얼마나 많은 원소를 복사해야하는가 생각해보면 충분히 상상 가능하다.
◦
배열의 크기를 K로 늘리면, 이전 배열은 N/2 였을 테니까 원소의 개수도 그와 같다.
◦
이것을 반복하면 대략 아래와 같이 이어진다.
▪
마지막 배열 크기 증가 : N/2 개의 원소 복사
▪
이전 배열 크기 증가 : N/4 개의 원소 복사
▪
이전 배열 크기 증가 : N/8 개의 원소 복사
▪
두번째 배열 크기 증가 : 2 개의 원소 복사
▪
첫번째 배열 크기 증가 : 1개의 원소 복사
◦
이것을 다 더한다고 해도 절대로 N을 넘을 수 없다. 따라서 N보다 작은 상수가 된다. → O(1)
해시테이블
•
키-값 구조로써 매우 빠르고 효율적으로 탐색
•
준비물
◦
연결리스트
◦
해시코드 함수
•
과정
◦
키의 해시코드를 계산. 보통 int나 long 을 사용한다. 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다.
◦
hash(key) % array length 와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다.
◦
배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다.
◦
서로 다른 두 개의 해시코드가 같은 인덱스를 가리킬수도 있다.
◦
배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비해서 반드시 연결리스트로 저장해야한다.
▪
충돌이란 서로 다른 두 개의 키가 같은 해시코드를 가리키거나, 서로 다른 두 개의 새시 코드가 같은 인덱스를 가리키는 경우를 말한다.
•
찾는 과정
◦
예를 들어 hi 라는 키가 있다고 해보자.
◦
hi 로부터 해시코드를 계산하여 10320 이라는 코드를 뽑아내고
◦
이 해시 코드를 이용해서 배열의 인덱스를 구한다. → 0
◦
해당 키와 상응하는 값(abc)을 배열에 연결리스트에서 탐색하면 된다.
•
균형이진탐색트리
◦
탐색시간은 O(logN)
◦
배열을 미리 할당하지 않아도 되어서 공간활용도가 좋고
◦
키의 집합을 특정 순서대로 접근가능하다.