배열과 해시테이블(Array and HashTable)

◎ 배열

     - 배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조이다.

     - 배열을 선언하게 되면 메모리에서 주소와 공간을 할당하여 시작주소를 index 0에 매핑된다.

     - 배열은 자료 구조 중 선형 구조에 해당한다.

     - 배열의 논리적인 순서(인덱스)는 메모리에 저장되는 원소값의 물리적인 순서(메모리 주소)와 동일하다.

     

  ○ 배열 읽기(Reading)

      - 임의의 위치에 있는 원소를 확인하거나 변경하는 연산은 O(1)의 시간 복잡도가 걸림.

      - 아래표에서 특정 인덱스의 값을 알고 싶은데 그 인덱스에서 접근해서 값을 읽으면 된다.

      - 특정 인덱스의 값 수정도 마찬가지로 그 인덱스에 접근해서 값을 수정하면 된다.

  ○ 배열 검색(Searching)

     - 특정한 값을 검색을 하는 경우는 그 배열의 0번 인덱스부터 차례대로 검색을 시작해서 찾는 값이 나올 때까지 실행을 한다.

 

  ○ 배열 삭제 및 삽입(Searching)

     - 처음에 배열을 선언할 때 배열은 주소와 배열의 크기를 선언을 하게 되는데 만약 삽입을 할 때 배열의 크기가 모자르게 된다면 그 배열을 복사해서 다른 주소에 연속된 메모리 공간을 확보하여 삽입을 하게 된다.

     - 또한 삽입의 경우 중간에 삽입을 하는 경우는 그 인덱스 이후에 값들을 옮겨서 저장을 한다.

     - 삭제의 경우는 중간에 빈 공간이 있으면 그 부분을 채워준다.(아래 그림 참고하기)

 

<배열에서 값 삽입시>

<배열에서 값 삭제시>

 

 

◎ 해시 테이블

     - 해시 테이블은 해시함수를 통해 키를 해시값으로 매핑하고, 이 해시값을 인덱스 혹은 주소로 해서 데이터의 값을 키와 저장하는 자료구조이다.

 

내일 이어서..