[자료구조]

[blossun]

해쉬(Hash)

• 해쉬함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수
• 충돌 : 해쉬함수에서 두 입력값에 대해 출력값이 동일한 것
• 충돌 회피(Collision Resolution)
  • Open Addressing : 충돌이 발생했을 때 원소를 저장하는 인덱스를 바꾸는 충돌 회피 방법
  • Chaining : 해쉬 테이블에서 각 인덱스에 원소 1개만을 담는 것이 아니라 Linked List 구조로 여러 원소를 담고 있는 방식
• 시간복잡도 : 삽입, 삭제, 검색 모두 (이론적으로는) O(1)
  • 하지만, 충돌이 빈번히 발생할수록 실제 시간복잡도는 나빠진다.
  • 테이블의 크기를 크게 한다거나, 적절한 해쉬 함수를 사용한다거나 하는 방식으로 충돌이 최대한 일어나지 않도록 하는 것이 중요

이진검색 트리

• 시간복잡도 : 삽입, 삭제, 검색 모두 O(lgN)
  • 하지만, 트리가 편향됨에 따라 실제 시간복잡도는 O(N)이 될 수도 있다. 이를 해결하기 위해 자가 균형 트리가 존재

힙(Heap)

• 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 이진 트리. (이진 검색 트리와 다른다.)
• 최대힙 : 부모는 자식보다 커야한다.
• 최소힙 : 부모는 자식보다 작아야한다.
• 루트가 최솟값 혹은 최댓값이 된다.
• 시간복잡도 : 삽입, 최솟(최댓)값 삭제 : O(lg N), 최솟(최댓)값 확인 : O(1)

"힙에서 할 수 있는건 어차피 균형 이진 트리에서도 할 수 있지 않나요? 그러면 균형 이진 트리가 더 제공해주는 기능이 많은데 힙을 쓸 이유가 있나요?"

힙에서 할 수 있는걸 균형 이진 트리에서 할 수 있는 것이 맞고, 자가 균형 트리라는 가정하에 시간복잡도가 O(lg N)으로 동일한 것도 맞습니다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현도 쉽고, 공간도 적게 차지하기에 최소 혹은 최댓값의 확인/삭제만 필요할 때에는 힙을 쓰는 것이 더 좋습니다.

Java - PriorityQueue(우선순위 큐)

        // 우선순위큐 (우선순위 큐는 기본적으로 최대힙)
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        // 최소힙 : 내림차순 정렬
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

TreeMap

• 이진트리를 기반으로 한 Map 컬렉션
• TreeSet과의 차이점
  • TreeSet : 값만 저장
  • TreeMap : 키와 값이 저장된 Map, Etnry를 저장
• TreeMap에 객체를 저장하면 자동으로 정렬
  • 키 : 저장과 동시에 자동 오름차순으로 정렬
    • 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬
  • 정렬 순서 : 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장
• TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어진다.
  • TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래 걸립니다.
• 하지만 정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap을 사용하는 것이 효율성면에서 좋다.

TreeMap 전체 값 출력 코드

EntrySet, KeySet() 사용

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};

//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

TreeMap의 전체요소를 출력하려면 HashMap과 마찬가지로 entrySet()이나 keySet()메소드를 활용하여 Map의 객체를 반환받은 후 출력하면 됩니다. entrySet()은 key와 value 모두가 필요할 경우 사용하며 keySet()은 key 값만 필요할 경우 사용하는데 key값만 받아서 get(key)를 활용하여 value도 출력할 수도 있기에 어떤 메소드를 선택하든지 간에 큰 상관이 없어 대부분 코드가 간단한 keySet을 활용하시던데 key값을 이용해서 value를 찾는 과정에서 시간이 많이 소모되므로 많은 양의 데이터를 가져와야 한다면 entrySet()이 좋습니다.(약 20%~200% 성능 저하가 있음)

Iterator 사용

TreeMap<Integer,String> map = new TreeMap<Integer,String>(){{//초기값 설정
    put(1, "사과");//값 추가
    put(2, "복숭아");
    put(3, "수박");
}};
		
//entrySet().iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박
		
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:복숭아
//[Key]:3 [Value]:수박

TreeMap의 전체출력 시 반복문을 사용하지 않고 Iterator를 사용하여도 됩니다. iterator로 Map안의 전체 요소를 출력하는 방법은 위와 같습니다.

• 참고

[blossun]

참고

• 바킹독 - 0x0D강 - 해쉬, 이진 검색 트리, 힙_구버전