이숭간 공부기록

HashTable 해시테이블은 (key, Value)로 데이터를 저장하는 자료구조로, 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시테이블이 빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기때문이다. 각각의 key값에 해시함수를 적용해 배열의 고유index를 생성하고 이 index를 활용해 값을 저장,검색한다. 저장과정 1. key가 John Smith일때, 해시함수를 이용해 index를 계산한다. 2. array[index] = "521-1234"를 저장한다. 이렇게 저장하게되면 Key값으로 데이터를 찾을때 해시함수를 한번만 수행하면 바로 키값을 찾을수 있으므로 O(1)시간에 데이터를 저장.삭제,조회할수 있다. 즉, 특정 데이터를 검색하는데 있어 배열을 순차적으로 ..

Array 어레이는 어떤 언어에나 존재하는 가장 기본적인 자료구조로 고정된 크기의 연속된 메모리를 말한다. 순서대로 번호(인덱스)가 붙은 원소들이 연속적인 형태로 구성된 구조를 뜻하며 인덱스를 알면 해당원소에 접근할 수 있다. 원소들이 연속적으로 배치되어 있기때문에 인덱스로 원소에 접근할때 O(1)의 시간복잡도를 가진다. 배열은 참조형 타입으로 변수명 자체가 레퍼런스를 저장하고 있기때문에 변수자체를 포인터로 활용할수 있다. 이때 배열은 연속적인 위치를 보장하므로 (포인터값 + 데이터형의 크기)로 다음요소에 접근할수 있다. 한계점: 고정된 크기 배열 자료구조는 선언시에 할당된 메모리크기가 고정되어있기 때문에 배열의 크기를 늘려야 할때는 크기가 큰 새로운 배열을 생성하고, 기존 내용을 복사하거나 배열일부를 ..