자료구조 - Collection, List, Set, Map 등 요약

나는 웹 프로그래머이다. 경력이 짧다.ㅎ

프로그래밍할 때 많이 쓰는 자료구조지만 좀 더 이해하고 쓰면 재밌는 거 같다.

해당 공부 내용은 OneNote에 적혀있는걸 그대로 가져온 거다.(OneNote에서 해당 블로그로 복사할 때 너무 힘들다.. 제대로 복사가 안된다.. 퉷)

누군가에게 도움이 되면 좋겠다.. 주니어 개발자가 면접 때 면접관이 높은 질문으로 물을 수 있다..(이해하면 베스트지만 최소 대답은 잘해야 한다..ㅎ)

이해가 안 된다면 해당 출처로 가서 정독하자..!

 

---

Java 에서 데이터를 저장하는 자료구조들을 한 곳애 모아 편리하게 관리하고 사용하기 위해 제공하는 것 , 크게 List, Set, Map 으로 구분할 수 있다 .

참고한 블로그들이다 감사를 표한다.

• https://joooootopia.tistory.com/13
• https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ppuagirls&logNo=221560996691
• https://st-lab.tistory.com/142

 

---

 

• List : 인터페이스
  • 동일한 데이터의 중복을 허용한다.
  • 데이터 저장 순서가 유지된다.
  • 힙 영역 내에서 List는 객체를 일렬로 늘어놓은 구조를 하고 있다.
  • 객체를 인덱스로 관리하기 때문에 객체를 저장하면 자동으로 인덱스가 부여되고 인덱스로 객체를 검색, 삭제할 수 있다. 이 때 List 컬렉션은 객체 자체를 저장하여 인덱스를 부여하는 게 아니라, 해당하는 인덱스에 객체의 주소값을 참조하여 저장한다.
  • List 컬렉션에서 공통적으로 사용가능한 추가, 검색, 삭제 메소드를 갖고있다.

• ArrayList
  • https://programmers.co.kr/learn/courses/17/lessons/805 
  • List 인터페이스의 구현 클래스로, 객체는 인덱스로 관리된다.
  • 자바에서 배열 초기화 시 크기를 정해줘야하지만정해줘야 하지만, ArrayList는 저장되는 데이터의 갯수에 따라 자동적으로 크기가 변경된다.
  • 내부에 배열이 꽉 찼을때 추가된다면 기존 배열보다 2배 긴 새 배열을 만들어, 기존 데이터를 새로운 배열로 복제한다.
  • 배열의 크기를 키우는 데는 많은 부하가 걸린다.
    • 확장된 크기의 ArrayList를 새로 생성하고, 그 새로 생성된 ArrayList에 기존의 ArrayList 값들을 복사해준다. 
    • 기존의 ArrayList는 가비지 컬렉션에 의해 메모리에 제거
• ᅟLinkedList
  • https://psychoria.tistory.com/767 
  • List 인터페이스의 구현 클래스, 양방향 포인터 구조로, 각각의 데이터가 노드로 구성되어 연결이 되는 구조.
  • 특정 인덱스의 객체를 제거하거나 삽입하면, 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않으므로,
  • 중간 삽입/삭제가 빈번할 수록 LinkedList를 쓰는 것이 효율적, 반대로 순차적 삽입/삭제가 빈번하다면 ArrayList를 사용하는게 효율적
•  Set
  • https://st-lab.tistory.com/238
  • 데이터의 저장 순서를 유지하지 않는다.(LinkedHashSet 제외)
  • 같은 데이터의 저장을 허용하지 않는다. 따라서 null도 하나의 null만 저장할 수 있다.
  • Set 컬렉션은 List 컬렉션처럼 인덱스로 개게를 검색해서 가져오는 메소드가 없다. 대신 전체 객체를 대상으로 한번씩 다 가져오는 반복자, Iterator을 제공한다.
  • Set 인터페이스를 구현한 주요 클래스 3가지
    • HashSet - 순서가 필요없는 데이터를 hash table에 저장, Set 중에 가장 성능이 좋음
    • TreeSet - 저장된 데이터의 값에 따라 정렬됨, red-black tree 타입으로 값이 저장됨.HashSet보다 성능이 느림.(중복되지 않으면서 특정 규칙에 의해ᅟ정렬된 형태의 집합을 쓰고 싶을 때)
    • LinkedHashSet - 연결된 목록 타입으로 구현된 hash table에 데이터 저장.저장된 순서에 따라 값이 정렬되나 셋 중 가장 느림.(중복은 허용하지 않으면서 순서를 보장받고 싶은경우)
• HashSet
  • https://st-lab.tistory.com/240?category=856997 
  • Hash란
    • 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 변환(매핑)하는 것
    • 이러한 과정을 해싱 한다고 하며, 해시함수에 얻어진 값을 보통 다이제스트(digest)라고 한다.
      
      • 우리가 그동안 구현해온 ArrayList, LinkedList 등 수많은 자료구조에서 '특정 값'이 있는지 찾아내기 위해서 어떻게 하였는가?
        배열 혹은 노드를 순회해보면서 특정값이 있는지 찾아냈었어야 한다. 
        하지만 해시함수를 이용한다면 굳이 순회할 필요가 없다.
        왜냐, 동일한 메시지(값)에 대해서는 동일한 다이제스트를 갖기 때문이다.
        
      • Set은 '중복 원소'를 허용하지 않는다. 즉 원소를 추가해야 할 때 마다 해당 원소가 중복되는 원소인지 아닌지를 검사해야한다는 것인데, 매번 원소를 검사해간다면 매우 비 효율적이다.
      • 그렇기에 고안한 방법이 Hash함수를 통해 특정 값에 대한 고유의 다이제스트를 얻고 그 값에 대응하는 index를 찾아서 해당 인덱스에 있는 요소만 검사하면 되는것.
    • 중복을 걸러내는 과정
      • https://coding-factory.tistory.com/554 
      • HashSet은 객체를 저장하기 전에 먼저 객체의 hashcode() 메소드를 호출해서 해시 코드를 얻어낸 다음 저장되어 있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 비교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.
        문자열을 HashSet에 저장할 경우, 같은 문자열을 갖는 String객체는 동일한 객체로 간주되고 다른 문자열을 갖는 String객체는 다른 객체로 간주되는데, 그 이유는 String클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열일 경우 hashCode()의 리턴 값을 같게, equals()의 리턴 값은 true가 나오도록 했기 때문입니다.
    • 저장공간보다 값이 추가로 들어오면 List처럼 약 두배의 저장공간을 늘린다.그렇기에 초기에 저장할 데이터 갯수를 알고 있다면 Set의 초기용량을 지정해주는 것이 좋다.

• Map
  • https://velog.io/@foeverna/Java-%EC% BD% 9C% EB% A0%89% EC%85%98% ED%94%84% EB% A0%88% EC% 9E%84% EC% 9B% 8C% ED%81% AC-Map-%EC% 9D% B8% ED%84% B0% ED% 8E%98% EC% 9D% B4% EC% 8A% A4 
  • ey, value으로 구성된 Entry 객체를 저장하는 구조, 여기서 키와 값은 모두 객체이다.
  • 값은 중복저장이 가능, 키는 불가능.
  • 검색을 위한 자료 구조
  • key를 이용하여 값을 저장하거나 검색, 삭제 할때 사용하면 편리함
    • 내부적으로는 hash 방식으로 구현됨
• HashMap
• https://coding-factory.tistory.com/556
  • Map 인터페이스 구현을 위해 해시테이블을 사용한 클래스
  • 값은 중복 저장될 수 있지마 키는 중복 저장될 수 없다.
  • 기존에 저장된 키와 동일한 키로 값을 저장하면 기존의 값은 없어지고 새로운 값으로 대치된다.
  • HashTable과 다르게 HashMap은 키와 값으로 null값이 허용된다.
    • hashTable은 예전에 많이쓴 클래스 앞으로 hashMap 쓰면된다.
  • 저장공간보다 값이 추가로 들어오면 List처럼 저장공간을 약 두배로 늘린다.