자료구조

TreeSet 구조 TreeSet은 필드로 NavigableMap 인터페이스를 가지고 있으며, TreeMap 클래스가 해당 인터페이스를 구현하는 구조를 가지고 있습니다. TreeSet 생성자가 호출되면 m 필드에 TreeMap 클래스가 할당됩니다. 문제점 발견 TreeSet을 사용하면서 예상한 결과값과 다르게 결과가 나와서 원인을 찾아보기로 했습니다. 예시: x만 비교할 때 Comparator<Point> comparator = Comparator.comparingInt(p -> p.x); TreeSet<Point> treeSet = new TreeSet<>(comparator); treeSet.add(new Point(1, 1)); treeSet.add(new Point(1, 2)); System.out.println(treeSet.size()); // 결과: 1 x만 비교하여 TreeSet 자료구조를 사용했을 때는 1개의 요소밖에 존재하지 않았습니다. HashSet이라면 객체의 hashCode()와 equals()를 비교하여 2라는 결과가 나왔을 텐데… ...

해시 자료구조는 16자리의 번호의 일부분을 index로 사용하는 자료구조입니다. 해시 함수란? 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 왜 일부분만 사용하는가? 모든 해시를 배열로 가지고 있으면 10^16의 배열이 필요합니다. 이는 40페타 바이트를 차지하게 됩니다. 그렇기에 모든 hash 값을 사용하는 게 아닌 일부분만의 값을 사용하여 해시 테이블을 생성합니다. 충돌 회피 방법 1. Chaining Key가 중복된 노드를 LinkedList로 연결하여 관리합니다. Java의 STL 자료구조는 Chaining 방식을 사용합니다. 주의사항: 충돌이 빈번할수록 성능이 안 좋아지고, 해시 충돌이 한 곳으로 몰렸다면 O(N)의 시간 복잡도를 가질 수 있습니다. ...