임의 길이의 데이터(키값)를 고정된 데이터(해시값, Value)로 매핑하는 것
해시함수를 사용하여 해시값으로 매핑한다.
→ 데이터가 많아지면 다른데이터가 같은 해시값으로 충돌(Collision)나는 현상이 생김
(무한한 개수의 데이터를 유한한 길이의 수로 출력하기 때문)
Chaining : 연결리스트로 노드를 계속 추가
장 : 제한없이 연결가능, 클러스터링(군집화)에 대한 고민이 필요없음
단 : 메모리가 많이 사용됨(하지만 낭비는 없음) , 동적할당으로 속도가 떨어짐
검색 : 해당 인덱스의 연결리스트를 선형적으로 검사
OpenAddressing : 함수로 얻은 주소가 아닌 다른 주소에 저장할 수 있게 허용
단 : 삭제시 더미데이터가 쌓일 수 있어 재해시(Rehash) 필요
선형 탐색
빈공간이 나올 때까지 바로 다음버킷을 순회한다.
장 : 간단한 구조
단 : 해시테이블 전체를 순회하는 경우가 생긴다, 제1밀집의 문제(테이블이 비어있어도 한곳에 데이터 밀집)
2차 검색법
떨어진 영역을 차례대로 검사 (1,4,9,16)
단: 제2밀집의 문제
이중해싱
충돌발생시 2차 해싱함수 이용하여 이동거리 얻음
단: 연산이 많음
무작위 검색
랜덤함수로 빈공간 찾을 떄까지 탐색
*load factor 컬렉션 클래스에 저장공간이 가득차기 전에 미리 저장공간을 확보한다. (기본값0.75)
출처
https://d2.naver.com/helloworld/831311
자바의 정석
node와 edge로 이루어진 비선형 자료구조
데이터베이스, 파일시스템에서 많이 사용됨(인덱스)
이진트리를 확장해 더 많은 수의 자식을 가질 수 있게 한다.
차수(degree)가 m인 B-트리
삭제시 언더플로우 처리 -재분배와 합병
루트노드를 제외하고는 적어도 ceil(m/2)개의 자료를 가지고 있어야 함에 위배되는 경우
항상 리프노드에서 수행
리프 노드가 아닐경우 : 하나더 큰값(후행값)과 자리 교환 후 리프노드를 삭제
삭제대상 : A
재분배 : 최소자료 수( ceil(m/2)개의 자료) 이상을 포함한 A의 형제노드에서 키 한개(B) 차출
부모노드의 키를 A노드로 이동, B는 부모노드로 이동
합병 : 재분배 불가시 사용 (최소키 수 이상을 포함한 A의 형제노드 없을 때)
A와 인접한 형제노드에 있는 키 값과 부모노드 키값을 모음
B-Tree | B+Tree |
---|---|
각노드에 데이터 저장 | index와 leaf로 분리 (leaf에서만 데이터 접근 가능) |
모든 노드에서 add, delete가능 | Leaf에서만 add, delete가능 |