본문 바로가기

전체 글142

Set과 주요 메서드 Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나다.이 인터페이스는 자바에서 다양한 컬렉션을 다루기 위한 메서드를 정의한다.Collection 인터페이스는 List, Set, Queue와 같은 다양한 하위 인터페이스 들과 함께 사용된다. Set 인터페이스는 Collection 인터페이스의 하위 요소다 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부 확인에 최적화 되어있다,Set인터페이스는 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있으며 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 지니고 있다. Set 인터페이스의 주요 메서드메서드 .. 2025. 7. 24.
HashSet 숫자는 해시 알고리즘을 이용해 저장한다문자는 숫자로 변경하고 해시 알고리즘을 이용해 저장한다객체는 Object.hashCode()를 이용해서 저장한다.보통 객체에서 재정의해서 사용한다 재정의 하지 않으면 같은 값이 중복으로 들어간다 같은 객체 인스턴스를 여러개만들었을 때 같은 값이 입력되더라도 같은 해시값이 나오기 때문임equals도 재정의 해야한다 해당 객체의 특정 값을 기준으로 동등성을 비교하도록 해야함 해시란?https://jaeiktech.tistory.com/2 해시코드와 이퀄스 모두 재정의 하지 않으면 같은 값을 두번 넣었을 때셋에 다른 곳에 같은 값이 저장된다 검색도 해시코드가 달라 되지 않는다해시코드만 재정의 한 경우 같은 값을 두번 넣었을 때셋에 같은 곳에 같은 값이 저장된다 해시코드.. 2025. 7. 24.
해시 해시 알고리즘을 쓰면 O(N)의 성능을 O(1)로 끌어올릴 수 있다. O(1)이라는건 인덱스 기반데이터를 인덱스의 값으로 같이 쓰면 중복 검사를 하지 않고 조회 시 빠르게 할 수 있음그런데 그럼 메모리 낭비가 심하다 나머지 연산으로 메모리를 아낀다 하지만 해시 충돌이 일어날 수 있다.해시 충돌은 인정해야한다. 대신 자바에서는 나머지 연산 및 갖가지 수학적 요소로 해시 충돌을 최대한 막고 사실상 충돌이 일어나는 일은 많지 않다.충돌이 일어나면 해시 안의 배열 같은 인덱스에 값이 여러개 들어가야하고 거기서 풀스캔을 해야한다.그래서 해시는 O(1)을 보장하는건 아니고 최악의 경우 O(N)이 될 수도 있다.하지만 그런일은 잘 일어나지 않고 O(1)에 가깝다고 볼 수 있다. 해시 기반 자료 구조를 사용하는 경우.. 2025. 7. 24.
배열리스트 vs 연결리스트 성능 비교 ArrayList vs LinkedList앞에 삽입, 삭제배열 리스트 O(n) - 뒤로 공간 하나씩 땡겨야함연결 리스트 O(1) - 앞에 노드 하나 만들면 됨 중간 삽입, 삭제배열 리스트 O(n) - 중간부터 뒤에 공간 땡겨야함연결 리스트 O(n) - 중간까지 노트 타고 가야함 끝에 삽입, 삭제배열 리스트 O(1) - 바로 추가하면됨연결 리스트 O(1) - 바로 추가하면됨 인덱스로 조회배열 리스트 O(1) - 메모리 주소 복사해서 바로 감연결 리스트 O(n) - 노드를 인덱스 수 만큼 이동 숫자로 조회배열 리스트 O(n) - 배열 숫자나올때 까지 순회연결 리스트 O(n) - 노드 숫자나올때 까지 순회 배열 리스트가 앞에 삽입,삭제 빼고 연결 리스트를 압승함. 같은 O(n)이라도 연결 리스트는 노드가 메모.. 2025. 7. 24.

티스토리툴바