[자료구조]Hash, B-tree, B+tree

해시(Hash)

임의 길이의 데이터(키값)를 고정된 데이터(해시값, Value)로 매핑하는 것

• 키값은 가변길이이기 때문에 그대로 저장소에 저장하게 되면 다양한 길이의 저장소를 구현해야 하기 때문에 효율성이 떨어짐

해시함수를 사용하여 해시값으로 매핑한다.

장점

• 무한히 많은 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로 프로세스 관리가 가능
• 같은 값을 해시함수에 넣으면 항상 같은 값을 리턴하므로 index를 알면 빠른 데이터 검색을 할 수 있음
• 시간복잡도는 O(1) (충돌이 일어나지 않는 경우에)

단점

• hash값을 저장할 별도의 공간이 필요
• 충돌이 일어날 수 있음
• 순차 탐색에는 적합하지 않다.

충돌문제(Collision)

→ 데이터가 많아지면 다른데이터가 같은 해시값으로 충돌(Collision)나는 현상이 생김
(무한한 개수의 데이터를 유한한 길이의 수로 출력하기 때문)

• 해결방법

1. Chaining : 연결리스트로 노드를 계속 추가

   • 장 : 제한없이 연결가능, 클러스터링(군집화)에 대한 고민이 필요없음

   • 단 : 메모리가 많이 사용됨(하지만 낭비는 없음) , 동적할당으로 속도가 떨어짐

   • 검색 : 해당 인덱스의 연결리스트를 선형적으로 검사

     

2. OpenAddressing : 함수로 얻은 주소가 아닌 다른 주소에 저장할 수 있게 허용

   • 단 : 삭제시 더미데이터가 쌓일 수 있어 재해시(Rehash) 필요

     1. 선형 탐색

        

        빈공간이 나올 때까지 바로 다음버킷을 순회한다.
        장 : 간단한 구조
        단 : 해시테이블 전체를 순회하는 경우가 생긴다, 제1밀집의 문제(테이블이 비어있어도 한곳에 데이터 밀집)
        

     2. 2차 검색법

        떨어진 영역을 차례대로 검사 (1,4,9,16)
        단: 제2밀집의 문제

     3. 이중해싱

        충돌발생시 2차 해싱함수 이용하여 이동거리 얻음
        단: 연산이 많음

     4. 무작위 검색

        랜덤함수로 빈공간 찾을 떄까지 탐색

자바에서의 해시

• 충돌 해결법 : SeperateChaining 기본적으로 LinkedList형태로 구현 개수가 8개 이상이 되면 Tree사용 6개 이하로 떨어지면 다시 Linked List로 변환( 2의 차이를 두는 것은 한개의 변화가 생길때 마다 자료구조를 변경하지 않기 위해서다. )
  
• Object클래스의 hashCode() : 객체의 주소를 이용하는 알고리즘→ 모든 객체에 대해 값이 유일함
• String의 hashCode() : 문자열의 내용으로 해시값을 얻는다

*load factor 컬렉션 클래스에 저장공간이 가득차기 전에 미리 저장공간을 확보한다. (기본값0.75)

• HashSet HaspMap을 이용해서 만들어짐
  
• HashMap Entry라는 내부 클래스를 선언하여 key-value를 하나로 관리한다. Key값은 유일, Value는 중복가능
  

출처
https://d2.naver.com/helloworld/831311
자바의 정석

트리

node와 edge로 이루어진 비선형 자료구조

B-트리(B-Tree)

데이터베이스, 파일시스템에서 많이 사용됨(인덱스)

이진트리를 확장해 더 많은 수의 자식을 가질 수 있게 한다.

차수(degree)가 m인 B-트리

• 루트노드는 적어도 2개이상의 자식을 가진다.
• 각 노드는 정렬되어있다. (한 노드안의 키값들은 )
• 특정 키 값의 왼쪽포인터의 서브트리는 그 키값보다 작음, 오른쪽은 큼
• 노드의 자료수가 n이면 자식수는 n+1( 왼,오에 포인터 1개씩있으니까)
• 루트노드를 제외하고는 적어도 ceil(m/2)개의 서브트리를 가지고 있어야 함

• 직접탐색이 빠르다 : logmN(최악)
• 순차탐색은 느리다.
• 삽입시 오버플로우 처리 - 분할
  1. 두 노드로 분열
  2. ceil(m/2) 를 부모노드로(중간값이나 둘중 큰값)
  3. 나머지는 반씩 나눈다.
     
     
     

• 삭제시 언더플로우 처리 -재분배와 합병

  • 루트노드를 제외하고는 적어도 ceil(m/2)개의 자료를 가지고 있어야 함에 위배되는 경우

  • 항상 리프노드에서 수행

    리프 노드가 아닐경우 : 하나더 큰값(후행값)과 자리 교환 후 리프노드를 삭제
    

    삭제대상 : A

    1. 재분배 : 최소자료 수( ceil(m/2)개의 자료) 이상을 포함한 A의 형제노드에서 키 한개(B) 차출

       부모노드의 키를 A노드로 이동, B는 부모노드로 이동
       

    2. 합병 : 재분배 불가시 사용 (최소키 수 이상을 포함한 A의 형제노드 없을 때)

       A와 인접한 형제노드에 있는 키 값과 부모노드 키값을 모음
       

B+트리

• 인덱스세트(데이터 접근을위한 길만 제공, 인덱스에 있는 키값은 길 찾아가는 용으로 실제 값에 대한 포인터는 없음)와 순차세트(리프노드, 링크드리스트, 키값)로 구성
• 장점 : 범위탐색에 유리함
• 단점 : 값을 찾기 위해서는 항상 리프노드까지 내려가야 함
• 직접탐색 : 항상 logmN
  

B, B+의 차이점 정리

B-Tree	B+Tree
각노드에 데이터 저장	index와 leaf로 분리 (leaf에서만 데이터 접근 가능)
모든 노드에서 add, delete가능	Leaf에서만 add, delete가능