[자료구조론] 배열과 문자열 & 해시테이블

Array  

    배열은 논리적 순서와 물리적 순서가 일치한다. 따라서 index 값을 통한 원소 접근이 용이하며 구현이 쉽다. 반면, 삽입/삭제 등에 연산

   에 불필요한 오버헤드(간접적인 처리시간)가 발생한다.

    삭제의 경우 순서를 맞추기 위하여 삭제된 원소 이후의 원소들을 모두 한 칸씩 앞쪽으로 shift 처리하며,

    삽입의 경우 삽입하기 이전에 삽입할 위치 이후의 원소들을 모두 한 칸씩 뒤쪽으로 shift 처리하는 과정을 거친다. 따라서 O(n)이다.

   

    한편, 원하는 n번째 원소에 즉시 접근하는 것은 쉽지만 (O(1)) , 어떤 값을 갖는 원소를 찾고 싶을 때 소요되는 시간은 미리 알  수 없으므

  로 O(n)이 걸린다. 

   

  ArrayUst & Resizable Arrays

    몇 언어에서는, 배열들이 자동적으로 사이즈가 변형된다. 이런 경우 배열 혹은 리스트는 요소를 추가할 때마다 커진다. 

  그러나 자바같은 다른 언어에서는 배열을 만들 때 정의된 사이즈로 고정된 길이를 가진다. 

   

   그래서 만약 동적인 크기조절이 가능한 배열이 필요하다면, ArrayList를 사용할 수 있다. ArrayList로 만들어진 array는 O(1)의 복잡도

  로 스스로 사이즈 변경이 가능하다. 전형적인 예로는, 배열이 가득찰 때 배열의 크기가 두배로 늘어난다. 그 과정에서 O(n)의 복잡도를 가

  지지만, 그런 경우는 매우 드물기 때문에 분할 삽입시간은 대체로 O(1)의 복잡도를 가진다. 

 

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

  

    

Hash Tables(왜 arrays and Strings chapter 에 이게 등장하지?) 

  HashTable은 내부적으로 배열을 사용하며, 충돌을 고려하지 않았을 때 탐색속도(O(1))을 갖는 빠른 자료구조이다. Keyr값을 해시함수를

통하여 인덱스로 변환한 후에, 그 인덱스에 집어 넣는다. 만약 다른 key값을 해시함수를 통과시켰는데 같은 인덱스가 나온다면, 충돌이라고 한다.  

ex) ("key", "value")  --> index = hash_functon("key") % tabe_size

                                          array[index] = "value" 

      이러한 해싱 구조로 데이터를 저장하면 key값으로 데이터를 찾을 때 해시 함수를 1번만 수행하면 되므로 매우 빠르게 데이터를

      저장/삭제/조회할 수 있다. (따라서 해시테이블의 평균 시간복잡도는 O(1)이다) 

 

충돌 해소법에는 두가지 방법이 있다.

  1. Open Address (개방 주소법) : 충돌 발생시, 다른 인덱스를 찾는것으로

     순차적으로 탐색하는 선형 탐사법, 

     2차 함수를 이용해 탐색 위치를 찾는 제곱 탐사법,

     충돌 발생시 새로운 해시함수를 활용하여 주소를 찾는 이중 해싱법이 있다.

     

 2. Separate Chaining (분리 연결법) : 다른 인덱스를 찾는 대신, 그 인덱스에다가 연결하는 방법

      연결 리스트를 이용하여 연결하는 방법과, Tree(RBT)를 이용하여 연결하는 방법이 있다. 두 방식 모두 worst case가 O(M)이다.

      데이터의 크기가 크다면 Separate Chaining 아니라면 Open Adress 방식이 더 낫다. 

 

   * Hashmap의 resize : 일정 개수 이상 크기가 커지면, 해시 버킷의 크기를 두 배로 늘린다. 

 

 

Implementation of Hash Tables

    Linked List and a Hash Code Function

      1. key와 value의 삽입

             1) int 혹은 long일 key의 해시코드 얻기 (*단, int는 유한한데 key가 무한히 많을 경우 다른 키에 같은 해시코드가 부여될 

                                                                                   수 있음) 

             2) 얻은 해시코드를 배열의 인덱스로 이용하기. hash(key) % array_length 의 형태로 이루어지고, 서로 다른 해시코드가                

                  당연히 같은 인덱스로 설정될 수 있다. 

            3) 그 인덱스에  key와 value의 linked list 넣기.  그 인덱스에 키와 값을 넣는 것인데, 충돌 때문에 linked list를 이용한다.

                  (즉, 같은 해시코드를 가진 다른 두 가지의 key 혹은 다른 두 해시코드에 같은 인덱스로 대응되는 해시코드의 경우)

      2. key를 통한 value의 반환 

         key로부터 해시코드를 계산하고, 해시코드로부터 인덱스를 계산한다. 그 후 해당하는 키를 가진 값을 Linked List에서 찾는다.

 

만약 충돌이 매우 많이 발생한다면, the worst case runtime은 O(N)이다. 그러나 충돌이 최소화된 가장 좋은 경우에서는 O(1)이 걸린다. 

 

*다른 방법으로,  균형이진 탐색트리를 가진 해시테이블을 사용할 수 있다. O(log N) 의 복잡도를 가진다. 이러한 해시테이블은 더 이상 큰 배열을 할당하지 않기 때문에 적은 공간을 사용할 수 있다는 장점이 있고 순서가 있는 키를 통해 반복할 수 있다는 점이 도움이 될 때도 있다. 

 

#해시테이블 : key / value / 해시코드 / 효율적 / 충돌 

 

 

 

 

 

 

 

 

 

 

 

+α

StringBuilder 

   String리스트를 연결할 때, running time은 얼마나 걸릴까?

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

하나를 이어붙이는 경우, String의 길이를 x라고 가정하면 x만큼 걸리고, 

두개를 하나로 이어붙이는 경우, 2x만큼 걸린다. 

전체적인 시간은  O(x + 2x + ... + nx ) = O(xn^2) 이 걸린다. 

이때 StringBuilder를 이용하면 편하다. 이 함수는 단순히 크기가 변화할 수 있는 String 배열을 제공해주고, 필요할 때 String으로 바꿀 수 있다.

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