[IT_Infra] HashTable - Array, LinkedList

Array, LinkedList

- 모두 순차적으로 데이터를 처리하는 구조

- 성능 측면에서 특징이 다르다

- 탐색알고리즘(해시/트리) 에서 사용하는 경우가 있다

1. 배열(Array)

- 데이터를 빈틈없이 순서대로 나열한 구조

- 탐색이 빠르다

- 데이터 추가 삭제가 느리다

2. 연결리스트(LinkedList)

- 데이터를 선으로 연결

- 탐색이 느리다

- 데이터 추가 삭제가 빠르다

3. 사용되는 곳

1) 해시 테이블

- 연결리스트 + 배열로 구성

예) 오라클 DB에서 SQL을 실행하면 SQL을 파스한 후 실행결과 반환

- 한번 실행된 SQL 관련 정보는 메모리에 저장(재사용하기위함)

- 재사용하기 위한 SQL 정보를 관리 할때 해시 테이블 사용

2) 오라클 SQL 재사용을 위한 해시테이블 구조

a. 처음 실행된 SQL 은 파스를 거쳐 실행된 후에도 메모리에 남는다(캐시)

b. 똑같은 SQL이 실행되면 메모리에 있는것 재사용

- 탐색이 빠른 배열 사용

- 배열은 고정 길이 데이터 구조라 제각각의 길이인 SQL을 관리할 수 없다

- 해시 함수를 이용하여 SQL을 고정길이 해시 값을 변환, 이 해시 값 배열로부터 연결 리스트를 찾아가면서 빠르게 탐색

c. 메모리가 부족하면 실행되고 있지 않은 SQL 해제한다

- SQL이 이곳 저곳에 산재하기 때문에 추가 삭제가 용이하려면 연결 리스트 사용