[1.배열/문자열] HashTable, ArrayList(가변배열), StringBuilder

1. 배열과 문자열

 : 둘의 문제풀이는 대체 가능

 

2. 해시테이블(HashTable)

 : 효율적인 탐색을 위한 자료구조

 : 키(Key)를 값(Value)에 대응

<구현방법>	연결리스트(LinkedList) + 해시코드함수(HashCodeFuction)
1	Key의 해시코드를 계산 : 보통 int 또는 long형 산출 (이때 key값은 무한하지만 int는 유한하므로 해시코드의 중복이 발생할 수 있다는 점 유의)
2	해시코드를 이용하여(e.g. hash(key)%array_length) 배열의 인덱스 구현
3	배열의 각 인덱스에 연결리스트(키+값)를 저장 이때, 충돌에 대비하여 반드시 연결리스트를 이용한다.

<값을 찾는 방법>	* 충돌이 자주 발생한다면 O(N), 최적화 된 경우 O(1)
1	주어진 키로부터 해시코드 계산
2	계산한 해시코드로부터 인덱스 계산
3	인덱스 안에 저장된 연결리스트 탐색

 : 균형이진탐색트리로 구현시, 탐색시간 O(logN) - 즉, 크기가 큰 배열을 미리 할당해두지않기에 잠재적으로 적은 공간 사용한다는 장점과 키 집합을 특정순서 차례대로 접근가능한 특징 존재

 

 

3. ArrayList와 가변크기배열

 : 언어에 따라 배열(List)는 자동으로 길이를 조정할 수 있기도하고 없기도 함 - Java는 배열 생성시 크기 지정 필수

 : 동적가변크기기능이 필요한 경우 주로 ArrayList 사용 - 크기 변화 가능 및 접근시간 O(1)유지

 : 배열이 가득차는 순간 배열의 크기를 2배로 증가 (길이를 늘리는 시간은 O(N)이지만, 잦은 일이 아니기때문에 상환입력시간으로 취급하여 계산)

ArrayList merge(String[] words, String[] more) {
	ArrayList sentence=new ArrayList();
	for(String w:words) {
		sentence.add(w);
	}
	for(String m:more) {
		sentence.add(m);
	}
	return sentence;
}

 

4. 상환입력시간은 왜 O(1)이 되는가?

 : 배열의 크기를 늘린다는 것은 배열 안의 원소를 복사한다는 것

  즉, 배열의 크기를 K로 늘리고 싶은 경우 이전 원소의 개수 K/2개 만큼의 원소를 복사해야 함

  이 작업을 반복적으로 생각해보았을때 K/2+K/4+K/8+...+1 이고 즉 K보다 작다는 것을 알 수 있음

  그러므로 N개의 원소를 삽입할때 작업시간은 O(N)만큼 소요되며 각 삽입은 평균적으로 O(1)만큼 소요

 

 

5. StringBuilder

문자열(String)을 이어붙이는 경우 두개의 문자열을 읽어 문자를 하나하나 새로운 문자열에 복사해야함

그러나 StringBuilder는 단순하게 가변크기의 배열을 이용하여 필요한 경우에만 문자열을 복사함

수행시간의 차이가 발생