본문 바로가기

자료구조7

HashMap 동작원리 HashMap은 Key와 Value가 짝 지어진 자료구조입니다. HashMap 동작원리HashMap은 key의 HashCode을 이용해서 시간복잡도 O(1)으로 value를 찾아낸다. HashCode를 인덱스로 삼는 배열 자료구조이다. 실제 계산은 HashCod % size 이다.나머지 연산을 하는 이유는 배열의 인덱스 중 하나로 매핑시키기 위함이다.특정 값에 대한 해시값  만약 3288449라는 값을 배열의 인덱스로 사용한다면 최소 3288449 크기의 배열을 생성해야한다. 메모리를 많이 차지할것이다. 때문에 이 값을 배열의 Size로 나눈 나머지를 구하고 이를 Index로 사용하는 것이다. 만약 HashMap 내부 배열 Size가 10이라면 3288449 % 10 = 9. 즉 9라는 인덱스를 갖게 된.. 2024. 5. 23.
Iterator에 대하여 Iterator 자바의 컬렉션에 존재하는 값들을 읽어오기 위한 방법으로 'iterator'라는 클래스가 존재한다. 이 iterator는 해당 컬렉션의 주소값을 기반으로 하나씩 값을 조회하는 클래스이다. 따라서, 대표적으로 다음과 같은 두 개의 함수가 존재한다. hasNext() : 다음 값을 갖고 있는지 true/false 반환 next() : 다음 값으로 이동 및 반환 자바에서는 각각의 컬렉션별로 Iterator를 반환하는 함수를 갖고 있고, 이 함수는 컬렉션의 첫 번째 주소 값을 반환하는 형식으로 되어있습니다. Iterator를 이용해 컬렉션을 추출하는 방법은 '첫 번째 주소를 담은 Iterator 생성 -> 반복문을 통해 하나씩 이동하며 저장된 값 반환' 입니다. 이를 코드로 나타내면 다음과 같습니.. 2024. 4. 16.
Set에 대하여 Set은 중복을 없애기 위해 사용한다. Set의 구현체로는 HashSet, LikedHashSet, TreeSet이 있다. HashSet: 순서x, 중복x LikedHashSet: 순서o, 중복x TreeSet: 오름차순, 중복x HashSet intHashSet = new HashSet(); LinkedHashSet intLinkedHashSet = new LinkedHashSet(); TreeSet intTreeSet = new TreeSet(); for (int i : new int[] { 3, 1, 8, 5, 4, 7, 2, 9, 6}) { intHashSet.add(i); intLinkedHashSet.add(i); intTreeSet.add(i); } Set strHashSet = new Ha.. 2024. 4. 16.
Queue에 대해서 Queue의 구조는 한쪽에서는 삽입만 일어나고 한쪽에서는 삭제만 하는 자료구조 입니다. 즉, 먼저 들어간 것이 먼저 나오는 FIFO 구조입니다. Queue 인터페이스를 구현하는 대표적인 두 가지 클래스는 LinkedList와 ArrayDeque입니다. 큐를 배열이 아닌 LinkedList로 구현한 이유 요소의 추가 및 제거 시 기존 배열을 재구성할 필요 없이 노드의 연결만 변경하면 됩니다. 이로 인해 요소의 추가 및 제거(특히, 앞/뒤)가 상수 시간(O(1))에 이루어집니다. 이유가 뭔가하면 배열로 구현한 큐의 경우 내부에서 Object[] 배열을 담고있고, 요소가 배열에 들어있는 양에 따라 용적(배열 크기)을 줄이거나 늘려주어야 하고, 큐를 선형적인 큐로 구현했을 경우 요소들이 뒤로 쏠리기 때문에 이러.. 2024. 4. 15.
List <-> 배열 변환하는 법 배열을 List로 1. Arrays.asList() String[] arr = { "A", "B", "C" }; List list = Arrays.asList(arr); 배열의 요소를 수정하든 List의 요소를 수정하든 서로의 영향을 받는다 ex) 배열에서 "A"를 "D"로 바꾸면 List에서도 "A"가 "D"로 바뀜 얕은 복사(Shallow Copy)로 생각하시면 됩니다. 2. new ArrayList( Arrays.asList()) String[] arr = { "A", "B", "C" }; List list = new ArrayList(Arrays.asList(arr)) 그래서 new 생성자로 새로운 List를 만든 후 거기에 복사해줍니다. 깊은 복사(Deep Copy)로 생각하시면 됩니다. 그런데.. 2024. 3. 29.
HashMap 사용법 HashMap은 Key와 Value의 묶음모음으로 이루어져 있는 자료구조입니다. HashMap 생성법 HashMap h1 = new HashMap( ); // 기본 capacity:16, load factor:0.75 HashMap h2 = new HashMap(20); // capacity:20으로 설정 HashMap h3 = new HashMap(20, 0.8); // capacity:20, load factor:0.8로 설정 HashMap h4 = new HashMap(h1); // 다른 Map(h1)의 데이터로 초기화 c capacity는 데이터 저장 용량, load factor는 데이터 저장공간을 추가로 확보해야 하는 시점을 지정합니다. load factor 0.8 은 저장공간이 80% 채워져 .. 2024. 3. 28.
자료구조 참조 사이트(내가 보기 위해 만든 것) ArrayList와 LinkedList 차이 Today-I-Learn/Java/Collection/List/ArrayList vs LinkedList.md at master · wjdrbs96/Today-I-Learn :octocat: Today I Learned. 그날 그날 모든 활동들을 정리. Contribute to wjdrbs96/Today-I-Learn development by creating an account on GitHub. github.com 2024. 3. 26.

티스토리툴바