- HashTable
- 저장할 값 또는 키값을 통해 테이블 내의 주소를 계산하고 그 곳에 값을 저장하는 구조.
1) hashFunction(저장값 또는 키) % 테이블 사이즈 = 저장할 index
- 탐색 시에도 같은 방법으로 index를 찾아 데이터 탐색
- hashFunction을 한번만 호출하면 값의 위치를 찾을 수 있어 빠름
- 값에 따라 index가 충돌할 수 있음(collision)
- collision 처리(index 충돌)
1) separate chaining : 이미 값이 저장된 index에 linkedList를 통해 node에 값 추가.
(JDK 1.8에서는 node가 8개 이상일 경우 트리 구조로 변경)
2) resizing: 테이블 사이즈를 더 크게잡고 재분배
- 충돌되어 chaining된 데이터는 index에 연결된 linkedList를 탐색하여 찾음 - NSHashTable
- NSSet, NSMutableSet의 weak 버젼이라고 생각하면 됨(하는 일은 같음)
- 자체가 mutable이라 크기가 동적임.
- 초기화 시 weak, strong, copy 등의 특성을 적용할 수 있음
'프로그래밍 > iOS' 카테고리의 다른 글
setNeedsLayout VS layoutIfNeeded / setNeedsDisplay VS layoutIfDisplay (1) | 2017.04.14 |
---|---|
Run Loop (0) | 2017.04.12 |
NSAutoreleasePool VS @autorelease block (0) | 2017.04.10 |
iOS 식별자(identifier) (2) | 2017.04.07 |
NSURL의 속성 (0) | 2017.04.07 |