DataStructure
-
Bloom Filter 알아보기DataStructure 2024. 10. 24. 17:49
- 목차 Bloom Filter 란 ? Bloom Filter 는 특정 값의 존재 유무를 빠르게 판단할 수 있는 기능을 제공하는 자료구조입니다. Bloom Filter 는 내부적으로 BitSet 이나 HashSet 같은 집합 형태의 자료구조를 사용하는데요. 집합 자료구조의 특성 상, 값의 존재 유무를 빠르게 판단할 수 있습니다. 또한 Bloom Filter 의 또 다른 특징은 확률적인 자료구조의 형태를 취한다는 사실입니다. 이는 Bloom Filter 의 해시 변환과 효율성과 관련이 있는 내용인데, 이어지는 내용에서 상세히 설명해보도록 하겠습니다. Bloom Filter 의 Index 추가 과정. Bloom Filter 는 아래의 이미지와 같은 방식으로 동작합니다. Bloom Filter 내부에는 ..
-
B-tree 자료구조 알아보기DataStructure 2023. 10. 30. 21:18
- 목차 B-tree 자료구조 알아보기.B-tree 자료구조는 Balanced Tree 의 약자인 균형이 잡힌 트리 자료구조입니다. 여기서 Balance 라는 의미는 B-tree 에게 있어서 가장 중요한 특징인데요. 빠른 조회 속도와 데이터의 효율적인 저장을 위해서 고안된 방식입니다. 몇가지 사례를 들어 B-tree 의 Balance 를 설명해보겠습니다. 먼저 B-tree 자료구조는 최소한의 Depth (Height) 를 지향합니다.즉, B-tree 자료구조는 일반적인 트리 자료구조에 비해서 높이가 짧습니다. 이는 조회시에 빠른 속도로 데이터를 조회할 수 있게 합니다. 이를 구현하기 위해서 하나의 노드가 지닐 수 있는 데이터의 갯수를 최대한 늘립니다. 하나의 노드가 하나의 데이터를 가지는 것보다 하나 이..
-
Java BitSet 자료구조 알아보기DataStructure 2023. 8. 8. 07:52
- 목차 들어가며.Java 에서 집합을 표현할 수 있는 다양한 방법들 중에서 BitSet 클래스에 대해서 알아봅니다. BitSet 이란 ? BitSet class 는 외관상으로는 Int, Long 과 같은 정수 타입의 저장할 수 있는 집합(Set) 입니다. 하지만 내부적으로 비트 단위로 상태의 On/Off 여부를 간편히 판단할 수 있는 자료구조이며, 비트 연산자를 사용하여 특정 Bit 의 값의 존재 유무를 판별하고, 값을 저장/삭제할 수 있습니다. BitSet.set 와 BitSet.get간단히 BitSet 클래스의 set 함수에 대해서 알아봅니다. BitSet 의 set 함수는 일반적인 집합 자료구조의 구조체들이 제공하는 값을 추가하는 연산입니다. cat ./BitSetTest.javaimport..