갑자기 자료구조를 정리해보기로 생각하게 된 배경
프로그래머스 코딩 테스트 고득점 Kit에 있는 문제들을 풀어보기 위해!
앞으로 여기에 나와있는 자료구조를 하나씩 정리하고 문제풀이를 진행하려고 한다.
자료구조란?
자료구조(Data Structure)는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다.
자료구조는 여러 종류(대표적으로 위의 사진 참고)가 있고 각각의 연산/목적에 맞추어져 있다.
프로그램을 설계할 때 어떤 자료구조를 선택할지 가장 우선적으로 고려하여야 하고, 적절한 자료구조의 선택은 필수적이라고 한다.
적절한 자료구조의 선택은 메모리를 최소화하고 시간, 공간 복잡도를 줄여 효율성을 높일 수 있다.
참고. 위키백과 : 자료구조
자료 구조 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.[1][2][3] 더 정확히 말해, ��
ko.wikipedia.org
해시란?
해시(Hash)는 Key-value쌍으로 데이터를 저장하는 자료구조이다.
해시는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 가진다.
그래서 해시 자료구조의 대표적인 해시 테이블은 O(1)의 시간 복잡도(Big-O)를 가진다.
하지만 충돌(Collisions)이 일어나서 데이터가 같은 공간에 리스트로 연결이 된다면, 최악의 경우 모든 리스트를 찾아봐야 하기 때문에 O(n)의 시간 복잡도를 가진다.
앞으로 진행할 문제풀이는 Java를 이용해서 할 것이기 때문에 Java에서의 해시를 정리해보자.
자바(Java)에서의 해시(Hash)
HashMap <Key, Value> map
자바에서 많이 사용하는 해시 맵(HashMap)이다 Hash의 성능을 통해 key값에 해당하는 Value를 즉시 검색할 수 있다.
그러므로 O(1)의 시간 복잡도를 가진다.
key값은 중복이 불가하고 value값은 중복이 가능하다. value에는 null도 사용이 가능하다.
멀티스레드에서는 HashMap에 동시 접근하게 되면 문제가 될 수 있기 때문에 HashTable을 사용해야 한다.
자주 사용하는 HashMap의 함수
HashMap.put(key, value)
HashMap에 키와 값을 저장
HashMap.containsKey(key)
HashMap에 지정된 키(key)가 포함되어 있는지 알려준다. (true/false)
HashMap.containsValue(value)
HashMap에 지정된 값(value)이 포함되어 있는지 알려준다. (true/false)
HashMap.get(key)
HashMap에서 지정된 key의 값(value)을 반환한다.
HashMap.remove(key)
HashMap에서 지정된 key와 쌍인 값(value)을 제거한다.
HashMap.clear()
HashMap에 저장된 모든 객체를 제거한다.
HashMap.replace(key, value)
HashMap에서 지정된 key의 값(value)을 인자로 전달된 값(value)으로 바꿔준다.
교체되어 삭제되는 값(value)은 리턴된다. 존재하지 않는 key가 인자로 전달되면 null을 리턴한다.
HashMap.KeySet()
HashMap에 저장된 key들을 Set 객체로 리턴해준다.
HashMap.values()
HashMap에 저장된 value들을 Collection 객체로 리턴해준다.
HashMap.getOrDefault(key, default value)
HashMap에서 지정된 key의 값(value)을 가져오는데 만약에 존재하지 않는다면 default 값(value)을 반환한다.
댓글