해시테이블

해시테이블은 효율적인 탐색을 위한 자료구조로써 키를 값에 대응 간단히 구현하는 경우, 배열과 해시함수(hash functions)만 있으면 가능,

객체와 키를 해시 테이블에 넣게 되면 우선 해시함수가 키를 정수값으로 대응시키는데, 이 정수값이 배열의 첨자로 쓰인다. 객체는 배열의 해당 index postion에 저장된다.

유일성이 보장되지 않기에, 키를 입력할때는 가능한 모든것을 고려해야한다.

그렇게 큰 배열을 할당하고 객체를 hash(key)위치에 저장하는 대신, 배열은 더 작게 만들고 객체는 hash(key)%array_length위치에 연결 리스트형태로 저장하는 방법.

대신 이진 탐색 트리를 사용해 해시테이블을 구현할 수도 있다. 그렇게 하면 O(log n)시간 안에 탐색이 완료되도록 보장할 수 있다.

TODO_ 해시테이블 구현

ArrayList(동적으로 크기가 조정되는 배열)

동적으로 크기가 조정되는 배열로서, 그러면서도 O(1)의 접근시간을 유지한다. 통상적으로는 배열이 가득 차는 경우, 그 크기가 두배 늘어나도록 구현. 크기가 두배 늘리는 시간은 O(n)이지만 자주 일어나는 일이 아니라서 대체적으로 O(1)시간이 유지된다고 보는 것이 옭다.

TODO_ 동적리스트

StringBuffer

StringBuffer를 사용하지 않는다면, 문자열을 연결할 때마다 새로운 문자열 객체가 만들어지고, 연결할 문자열의 값이 문자 단위로 복사된다. 그러므로 첫 루프에서는 x개의 문자가 복사될 것이고, 두번쨰루프는 2x 다음 3x 즉 소요시간은? x+2x+3x``` 해서 최종적으로는 O(x n^2)만큼의 시간이 걸리리라는 결론을 내릴 수 있다.

그러나 StringBuffer를 사용하면 이런 문제를 피할 수 있다. 간단히 말하면, StringBuffer는 모든 문자열의 배열을 만들어 두고, 문자열 객체로의 복사는 필요할 때만 수행한다.

면접문제.

1. 문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라.다른 자료 구조를 사용할 없는 상황이라면 어떻게 하겠는가? 2.