1. 배열과 문자열

▶ 해시테이블

효율적인 탐색을 위한 자료구조, 키를 값에 대응시킨다.

간단한 해시테이블을 구현하기 위해서는 연결리스트와 해시 코드 함수만 있으면 된다. 키와 값을 해시테이블에 넣을 때는 다음의 과정을 거친다.

 

1. 키의 해시코드를 계산한다. 키의 자료형은 보통 int 혹은 long이 된다. 키의 개수는 무한한데 반해 int의 개수는 유한하기 때문에 서로 다른 두 개의 키가 같은 해시 코드를 가리킬 수 있다는 사실을 명심하자.

-> database의 키 값을 가져올 때 long을 많이 사용했었다.

 

2. hash(key) % array_length와 같은 방식으로 해시 코드를 이용해 배열의 인덱스를 구한다. 물론 서로 다른 두 개의 해시코드가 같은 인덱스를 가리킬 수도 있다.

 

3. 배열의 각 인덱스에는 키와 값으로 이루어진 연결리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결리스트를 이용해야한다. 여기서 충돌이란 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나 서로 다른 두 개의 해시코드가 같은 인덱스를 가리키는 경우를 말한다.

-> 다른 내용의 데이터가 같은 키를 갖는 상황을 충돌이라 한다.

 

키에 상응하는 값을 찾기 위해서는 다음의 과정을 반복해야 한다.

주어진 키로부터 해시 코드를 계산하고, 이 해시 코드를 이용해 인덱스를 계산한다. 그 다음에 키에 상응하는 값을 연결리스트에서 탐색한다.

▶ ArrayList와 가변 크기 배열

Java의 경우 리스트라고 불릴 수 있지만, 크기를 자동으로 조절 할 수 있는 배열이 있다.데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가한다. 배열의 길이가 고정되어야 할 때에는 만들 때 배열의 크기를 함께 지정해야 한다. 동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때에는 보통 ArrayList를 사용한다.ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서도 접근시간을 유지한다.통상적으로 배열이 가득 차는 순간, 배열의 크기를 두 배로 늘린다.

▶ StringBuilder

아래에 나와 있는 것 처럼, 문자열의 리스트가 주어졌을 때 이 문자열을 이어붙인다고 가정하자.

이 때의 수행시간은 n개의 문자열을 이어붙인다고 했을 때 총 수행시간은 O(xn^2)가 된다.

처음에는 x개, 두 번째는 2x개, 세 번째는 3x개 .. 즉 n번째에는 nx개의 문자를 복사해야 한다.
따라서 총 수행시간은 O(x + 2x + 3x + ... + nx) 인 O(xn^2) 이다.

String joinWords(String[] words) {
    Stirng sentence = "";
    for(String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

 

이와 같은 문제는 StringBuilder가 해결해 줄 수 있다. StringBuilder는 단순하게 가변 크기 배열을 이용하여 필요한 경우에만 문자열을 복사하게끔 해준다. 

String joinWords(String[] words) {
	StringBuilder sentence = new StringBuilder();
    for(String w : words) {
    	sentence.append(w);
    }
    return sentence.toString();
}